0,3

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

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.

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.

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]

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);

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]

(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 */

Cf. A000108, A002694.

Cf. A127529.

Sequence in context: A065290 A065266 A065260 this_sequence A127151 A057115 A065276

Adjacent sequences: A091891 A091892 A091893 this_sequence A091895 A091896 A091897

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 10 2004