|
| |
|
|
A091894
|
|
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k ddu's [here u=(1,1) and d=(1,-1)].
|
|
10
| |
|
|
1, 1, 2, 4, 1, 8, 6, 16, 24, 2, 32, 80, 20, 64, 240, 120, 5, 128, 672, 560, 70, 256, 1792, 2240, 560, 14, 512, 4608, 8064, 3360, 252, 1024, 11520, 26880, 16800, 2520, 42, 2048, 28160, 84480, 73920, 18480, 924, 4096, 67584, 253440, 295680, 110880, 11088, 132
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Number of Dyck paths of semilength n, having k uu's with midpoint at even height. Example: T(4,1)=6 because we have u(uu)duddd, u(uu)udddd, udu(uu)ddd, u(uu)dddud, u(uu)ddudd and uud(uu)ddd [here u=(1,1), d=(1,-1) and the uu's with midpoint at even height are shown between parentheses]. Row sums are the Catalan numbers (A000108). T(2n+1,n)=A000108(n) (the Catalan numbers). sum(kT(n,k), k>=0) = binomial(2n-2,n-3)=A002694(n-1).
Sometimes called the Touchard distribution (after Touchard's Catalan number identity). T(n,k) = number of full binary trees on 2n edges with k deep interior vertices (deep interior means you have to traverse at least 2 edges to reach a leaf) = number of binary trees on n-1 edges with k vertices having a full complement of 2 children. - David Callan (callan(AT)stat.wisc.edu), Jul 19 2004
Comment from David Callan (callan(AT)stat.wisc.edu), Oct 25 2004: "T(n,k) = number of ordered trees on n edges with k prolific edges. A prolific edge is one whose child vertex has at least two children. For example with n=3, drawing ordered trees down from the root, /|\ has no prolific edge and the only tree with one prolific edge has the shape of an inverted Y, so T(3,1)=1.
"Proof. Consider the following bijection, recorded by Emeric Deutsch, from ordered trees on n edges to Dyck n-paths. For a given ordered tree, traverse the tree in preorder (walk-around from root order). To each node of outdegree r there correspond r upsteps followed by 1 downstep; nothing corresponds to the last leaf. This bijection sends prolific edges to noninitial ascents of length >=2, that is, to DUUs. Then reverse the resulting Dyck n-path so that prolific edges correspond to DDUs."
T(n,k) is the number of Lukasiewicz paths of length n having k fall steps (1,-1) that start at an even level. A Lukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,1)=1 because we have U(2)(D)D, where U(2)=(1,2), D=(1,-1) and the fall steps that start at an even level are shown between parentheses. Row n contains ceil(n/2) terms (n>=1). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 06 2005
Number of binary trees with n-1 edges and k+1 leaves (a binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 31 2006
Number of full binary trees with 2n edges and k+1 vertices both children of which are leaves (n>=1; a full binary tree is a rooted tree in which each vertex has either 0 or two children). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 26 2006
Number of ordered trees with n edges and k jumps. In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 18 2007
It is remarkable that we can generate the coefficients of the right hand columns of triangle A175136 with the aid of the coefficients in the rows of the triangle given above. See A175136 for more information. [From Johannes W. Meijer, May 6 2011]
|
|
|
REFERENCES
| A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
E. Deutsch, Dyck path enumeration, Discrete Math., 204 (1999), 167-202 (see pp. 192-193).
John Riordan, A Note on Catalan Parentheses, Amer. Math. Monthly, Vol. 80, No. 8 (1973), pp. 904-906.
|
|
|
FORMULA
| T(n, k)=2^(n-2k-1)*binomial(n-1, 2k)*binomial(2k, k)/(k+1); T(0, 0)=1. G.f.=G=G(t, z) satisfies tzG^2-(1-2z+2tz)G+1-z+tz=0.
|
|
|
EXAMPLE
| T(4,1)=6 because we have uduu(ddu)d, uu(ddu)dud, uuu(ddu)dd, uu(ddu)udd, uudu(ddu)d and uuud(ddu)d [here u=(1,1), d=(1,-1) and the ddu's are shown between parentheses].
Triangle begins:
[1],
[1],
[2],
[4, 1],
[8, 6],
[16, 24, 2],
[32, 80, 20],
[64, 240, 120, 5],
[128, 672, 560, 70],
[256, 1792, 2240, 560, 14]
|
|
|
MAPLE
| a := proc(n, k) if n=0 and k=0 then 1 elif n=0 then 0 else 2^(n-2*k-1)*binomial(n-1, 2*k)*binomial(2*k, k)/(k+1) fi end: 1, seq(seq(a(n, k), k=0..(n-1)/2), n=1..15);
|
|
|
MATHEMATICA
| A091894[n_] := Prepend[Table[ CoefficientList[ 2^i (1 - z)^((2 i + 3)/2) Hypergeometric2F1[(i + 3)/2, (i + 4)/2, 2, z], z], {i, 0, n}], {1}] (* computes a table of the first n rows. Stumbled accidently on it. Perhaps someone can find a relationship here? *) [From Thies Heidecke (theidecke(AT)astrophysik.uni-kiel.de), Sep 23 2008]
|
|
|
PROG
| (PARI) {T(n, k)=if(n<1, n==0&k==0, polcoeff(polcoeff( serreverse(x/(1+2*x*y+x^2)+x*O(x^n)), n), n-1-2*k))} /* Michael Somos Sep 25 2006 */
|
|
|
CROSSREFS
| Cf. A000108, A002694.
Cf. A127529.
Sequence in context: A065290 A065266 A065260 * A127151 A193034 A057115
Adjacent sequences: A091891 A091892 A091893 * A091895 A091896 A091897
|
|
|
KEYWORD
| nonn,tabf
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 10 2004
|
| |
|
|
