|
| |
|
|
A108838
|
|
Triangle of Dyck paths counted by number of long interior inclines.
|
|
5
|
|
|
|
2, 3, 2, 4, 8, 2, 5, 20, 15, 2, 6, 40, 60, 24, 2, 7, 70, 175, 140, 35, 2, 8, 112, 420, 560, 280, 48, 2, 9, 168, 882, 1764, 1470, 504, 63, 2, 10, 240, 1680, 4704, 5880, 3360, 840, 80, 2, 11, 330, 2970, 11088, 19404, 16632, 6930, 1320, 99, 2
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,1
|
|
|
COMMENTS
|
T(n,k) is the number of Dyck n-paths (A000108) containing k long interior inclines. An incline is an ascent or a descent where an ascent (resp. descent) is a maximal sequence of contiguous upsteps (resp. downsteps). An incline is long if it consists of at least 2 steps and is interior if it does not start or end the path.
T(n,k) is the number of Dyck (n+1)-paths whose last descent has length 2 and which contain n-k peaks. For example T(3,0)=3 counts UUDUDUDD, UDUUDUDD, UDUDUUDD. - David Callan, Jul 03 2006
T(n,k) is the number of parallelogram polyominoes of semiperimeter n+1 having k corners. - Emeric Deutsch, Oct 09 2008
T(n,k) is the number of rooted ordered trees with n non-root nodes and k leaves; see example. - Joerg Arndt, Aug 18 2014
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n, k) = 2*binomial(n+1, k+2)*binomial(n-2, k)/(n+1).
G.f.: G(z, t) = Sum_{n>=1, k>=0} T(n, k)*z^n*t^k satisfies z - ( (1-z)^2 - (2*t-t^2)*z^2 )*G + (t^2*z)*G^2 = 0.
G.f.: 1+z(1+r)^2, where r=r(t,z) is the Narayana function defined by (1+r)*(1+tr)z=r, r(t,0)=0. - Emeric Deutsch, Jul 23 2006
For n >= 0, the row polynomials Sum_{k=0..n} T(n+2,k)*x^k = (2/(n+1))*(1-x)^n*P(n,2,1,(1+x)/(1-x)), where P(n,a,b,x) denotes the Jacobi polynomial. It follows that the row polynomials have negative real zeros. - Peter Bala, Jan 21 2008
The trivariate g.f. G=G(t,s,z) of Dyck paths with respect to number of DUU's (marked by t), number of DDU's (marked by s) and semilength (marked by z) satisfies G = 1 + z*G + z^2*(1+t*(G-1))*(1+s*(G-1))/(1-z*(1+t*s*(G-1))) (the number of long interior inclines is equal to the number of DUU and DDU's). - Emeric Deutsch, Oct 09 2008
Recurrence: T(n, k) = T(n, k-1)*(n-1-k)*(n-k)/(k*(k+2)) for k > 0 and n >= 2. - Werner Schulte, Jan 04 2017
The array can be extended to negative values of n: T(-n,k) = 2*binomial(-n+1, k+2)*binomial(-n-2, k)/(-n+1) = -A145596(n+k,k+1) for n >= 2. - Peter Bala, Apr 26 2022
|
|
|
EXAMPLE
|
Table begins
\ k..0....1....2....3....4....5
n\
2 |..2
3 |..3....2
4 |..4....8....2
5 |..5...20...15....2
6 |..6...40...60...24....2
7 |..7...70..175..140...35....2
The paths UUUDDD, UUDUDD, UDUDUD have no long interior inclines; so T(3,0)=3.
The rooted ordered trees with n=3 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
: 1: [ 0 1 1 1 ] 2
: O--o
: .--o
: .--o
:
: 2: [ 0 1 1 2 ] 2
: O--o
: .--o--o
:
: 3: [ 0 1 2 1 ] 1
: O--o--o
: .--o
:
: 4: [ 0 1 2 2 ] 1
: O--o--o
: .--o
:
: 5: [ 0 1 2 3 ] 1
: O--o--o--o
:
This gives [3, 2], row n=3 of the triangle.
(End)
|
|
|
MAPLE
|
T:=(n, k)->2*binomial(n-1, k)*binomial(n, k+2)/(n-1): for n from 2 to 11 do seq(T(n, k), k=0..n-2) od; # yields sequence in triangular form; Emeric Deutsch, Jul 23 2006
|
|
|
MATHEMATICA
|
T[n_, 0] = n;
T[n_, k_] := T[n, k] = If[k == n-2, 2, T[n, k-1](n-k-1)(n-k)/(k(k+2))];
|
|
|
CROSSREFS
|
Row sums are the Catalan numbers A000108. Column k=1 is A007290, k=2 is A006470. The Narayana numbers A001263 count Dyck paths by number of long nonterminal inclines. A091894 (Touchard distribution) counts Dyck paths by number of long nonterminal descents.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
