|
|
A091869
|
|
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k peaks at even height.
|
|
9
|
|
|
1, 1, 1, 2, 2, 1, 4, 6, 3, 1, 9, 16, 12, 4, 1, 21, 45, 40, 20, 5, 1, 51, 126, 135, 80, 30, 6, 1, 127, 357, 441, 315, 140, 42, 7, 1, 323, 1016, 1428, 1176, 630, 224, 56, 8, 1, 835, 2907, 4572, 4284, 2646, 1134, 336, 72, 9, 1, 2188, 8350, 14535, 15240, 10710, 5292, 1890, 480, 90, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Number of ordered trees with n edges having k leaves at even height. Row sums are the Catalan numbers (A000108). T(n,0)=A001006(n-1) (the Motzkin numbers). Sum_{k=0..n-1} k*T(n,k) = binomial(2n-2, n-2) = A001791(n-1). Mirror image of A091187.
T(n,k) is the number of Dyck paths of semilength n and having k dud's (here u=(1,1) and d=(1,-1)). Example: T(4,2)=3 because we have uud(du[d)ud], uu(dud)(dud) and uu(du[d)ud]d (the dud's are shown between parentheses).
T(n,k) is the number of Dyck paths of semilength n and containing exactly k double rises whose matching down steps form a doublefall. Example: UUUDUDDD has 2 double rises but only the first has matching Ds - the path's last 2 steps - forming a doublefall. (Travel horizontally east from an up step to encounter its matching down step.) - David Callan, Jul 15 2004
T(n,k) is the number of ordered trees on n edges containing k edges of outdegree 1. (The outdegree of an edge is the outdegree of its child vertex. Thus edges of outdegree 1 correspond to non-root vertices of outdegree 1.) T(3,2)=2 because
/\.../\.
|.....|.
each have one edge of outdegree 1. - David Callan, Oct 25 2004
Exponential Riordan array [exp(x)*Bessel_I(1,2x)/x, x]. - Paul Barry, Mar 09 2010
T(n, k) is the number of Dyck paths of semilength n and having k udu's (here u=(1,1) and d=(1,-1)). Note that reversing a path swaps u and d, thus udu becomes dud and vice versa. - Michael Somos, Feb 26 2020
|
|
LINKS
|
|
|
FORMULA
|
T(n, k) = binomial(n-1, k)*(Sum_{j=0..ceiling((n-k)/2)} binomial(n-k, j)*binomial(n-k-j, j-1))/(n-k) for 0 <= k < n; T(n, k)=0 for k >= n.
G.f.: G = G(t, z) satisfies z*G^2 - (1 + z - t*z)*G + 1 + z - t*z = 0. T(n, k) = M(n-k-1)*binomial(n-1, k), where M(n) = A001006(n) are the Motzkin numbers.
G.f.: 1/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-... (continued fraction). - Paul Barry, Aug 03 2009
E.g.f.: exp(x+xy)*Bessel_I(1,2x)/x. - Paul Barry, Mar 10 2010
|
|
EXAMPLE
|
T(4,1)=6 because we have u(ud)dudud, udu(ud)dud, ududu(ud)d, uuudd(ud)d, u(ud)uuddd and uuu(ud)ddd (here u=(1,1), d=(1,-1) and the peaks at even height are shown between parentheses).
Triangle begins:
1;
1, 1;
2, 2, 1;
4, 6, 3, 1;
9, 16, 12, 4, 1;
21, 45, 40, 20, 5, 1;
51, 126, 135, 80, 30, 6, 1;
...
|
|
MAPLE
|
T := proc(n, k) if k<n then binomial(n-1, k)*sum(binomial(n-k, j)*binomial(n-k-j, j-1), j=0..ceil((n-k)/2))/(n-k) else 0 fi end: seq(seq(T(n, k), k=0..n-1), n=1..11);
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,
`if`(y>0, b(x-1, y-1, 0)*z^irem(t*y+t, 2), 0)+
`if`(y<x-1, b(x-1, y+1, 1), 0)))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
|
|
MATHEMATICA
|
(* m = MotzkinNumber *) m[0] = 1; m[n_] := m[n] = m[n - 1] + Sum[m[k]*m[n - 2 - k], {k, 0, n - 2}]; t[n_, n_] = 1; t[n_, k_] := m[n - k]*Binomial[n - 1, k - 1]; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 10 2013 *)
|
|
PROG
|
(PARI) {T(n, k) = my(y, c, w); if( k<0 || k>=n, 0, w = vector(n); forvec(v=vector(2*n, k, [0, 1]), c=y=0; for(k=1, 2*n, if( 0>(y += (-1)^v[k]), break)); if( y, next); for(i=1, 2*n-2, c += ([0, 1, 0] == v[i..i+2])); w[c+1]++); w[k+1])}; /* Michael Somos, Feb 26 2020 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|