|
| |
|
|
A091869
|
|
Triangle read by rows: T(n,k)=number of Dyck paths of semilength n having k peaks at even height.
|
|
3
| |
|
|
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
(list; table; graph; refs; listen; history; 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*T(n,k),k=0..n-1) = binom(2n-2,n-2)=A001791(n-1). Mirror image of A091187.
T(n,k)= 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)= 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 (callan(AT)stat.wisc.edu), Jul 15 2004
T(n,k)=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 (callan(AT)stat.wisc.edu), Oct 25 2004
Exponential Riordan array [exp(x)*Bessel_I(1,2x)/x, x]. [From Paul Barry (pbarry(AT)wit.ie), Mar 09 2010]
|
|
|
REFERENCES
| Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords, http://people.brandeis.edu/~gessel/homepage/students/wangthesis.pdf.
|
|
|
LINKS
| A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Yidong Sun, The statistic "number of udu's" in Dyck paths, Discrete Math., 287 (2004), 177-186.
|
|
|
FORMULA
| T(n, k)=binomial(n-1, k)*sum(binomial(n-k, j)*binomial(n-k-j, j-1), j=0..ceil((n-k)/2))/(n-k) for 0<=k<n; T(n, k)=0 for k>=n. G.f.=G=G(t, z) satisfies zG^2-(1+z-tz)G+1+z-tz=0. T(n, k)=M(n-k-1)*binomial(n-1, k), where M(n)=A001006(n) are the Motzkin numbers.
T(n+1, k+1)=n*T(n, k)/(k+1). - David Callan (callan(AT)stat.wisc.edu), Dec 09 2004
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). [From Paul Barry (pbarry(AT)wit.ie), Aug 03 2009]
E.g.f.: exp(x+xy)*Bessel_I(1,2x)/x. [From Paul Barry (pbarry(AT)wit.ie), 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);
|
|
|
CROSSREFS
| Cf. A000108, A001006, A001791, A091187.
Sequence in context: A068957 A119468 A175136 * A112307 A111062 A193597
Adjacent sequences: A091866 A091867 A091868 * A091870 A091871 A091872
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 10 2004
|
| |
|
|
