

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)].


16



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;
text;
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_{k>=0} k*T(n,k) = binomial(2n2,n3) = A002694(n1).
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 n1 edges with k vertices having a full complement of 2 children.  David Callan, Jul 19 2004
From David Callan, Oct 25 2004: (Start)
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 npaths. For a given ordered tree, traverse the tree in preorder (walkaround 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 DUU's. Then reverse the resulting Dyck npath so that prolific edges correspond to DDU's. (End)
T(n,k) is the number of Łukasiewicz paths of length n having k fall steps (1,1) that start at an even level. A Łukasiewicz 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 ceiling(n/2) terms (n>=1).  Emeric Deutsch, Jan 06 2005
Number of binary trees with n1 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, 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, 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, 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.  Johannes W. Meijer, May 06 2011
The antidiagonal sums equal A152225.  Johannes W. Meijer, Sep 13 2012
This array also counts 231avoiding permutations according to the number of peaks, i.e., positions w[i1] < w[i] > w[i+1]. For example, 123, 213, 312, and 321 have no peaks, while 132 has one peak. Note also T(n,k)=2^(n12k)*A055151(n1,k).  Kyle Petersen, Aug 02 2013


REFERENCES

T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 4.3.


LINKS

Alois P. Heinz, Rows n = 0..200, flattened
A. M. Baxter, Refining enumeration schemes to count according to permutation statistics, arXiv preprint arXiv:1401.0337 [math.CO], 2014.
D. Callan, A variant of Touchard's Catalan number identity, arXiv preprint arXiv:1204.5704 [math.CO], 2012.  N. J. A. Sloane, Oct 10 2012
Colin Defant, Postorder Preimages, arXiv preprint arXiv:1604.01723 [math.CO], 2016.
E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167202 (see pp. 192193)..
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 924.
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Nonleft peaks in Dyck paths: a combinatorial approach, Discrete Math., 337 (2014), 97105.
John Riordan, A Note on Catalan Parentheses, Amer. Math. Monthly, Vol. 80, No. 8 (1973), pp. 904906.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 29092924.
L. W. Shapiro, A short proof of an identity of Touchard's concerning Catalan numbers, J. Combin. Theory Ser. A 20 (1976) 375376.
Guoce Xin and JingFeng Xu, A short approach to Catalan numbers modulo 2^r, Electronic Journal of Combinatorics Vol. 18 Issue 1 (2011), #P177 (see page 2).
Index entries for sequences related to Łukasiewicz


FORMULA

T(n,k) = 2^(n2k1)*binomial(n1,2k)*binomial(2*k,k)/(k+1); T(0,0)=1.
G.f.: G = G(t,z) satisfies: t*z*G^2(12*z+2*t*z)*G+1z+t*z = 0.
With first row zero, the o.g.f. is g(x,t) = [1  2x  sqrt[(12x)^24tx^2]] / (2tx) with the inverse ginv(x,t) = x / (1 + 2x + t x^2), an o.g.f. for shifted A207538 and A133156 mod signs, so A134264 and A125181 can be used to interpret the polynomials of this entry. Cf. A097610.  Tom Copeland, Feb 08 2016
If we delete the first 1 from the data these are the coefficients of the polynomials p(n) = 2^n*hypergeom([(1  n)/2, n/2], [2], x).  Peter Luschny, Jan 23 2018


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^(n2*k1)*binomial(n1, 2*k)*binomial(2*k, k)/(k+1) fi end: 1, seq(seq(a(n, k), k=0..(n1)/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 accidentally on it. Perhaps someone can find a relationship here? Thies Heidecke (theidecke(AT)astrophysik.unikiel.de), Sep 23 2008 *)
Join[{1}, Select[Flatten[Table[2^(n2k1) Binomial[n1, 2k] Binomial[2k, k]/ (k+1), {n, 20}, {k, 0, n}]], #!=0&]] (* Harvey P. Dale, Mar 05 2012 *)
p[n_] := 2^n Hypergeometric2F1[(1  n)/2, n/2, 2, x]; Flatten[Join[{{1}}, Table[CoefficientList[p[n], x], {n, 0, 12}]]] (* Peter Luschny, Jan 23 2018 *)


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), n1  2*k))} /* Michael Somos, Sep 25 2006 */


CROSSREFS

The first few columns equal A011782, A001788, 2*A003472, 5*A002409, 14*A140325 and 42*A172242.  Johannes W. Meijer, Sep 13 2012
Cf. A000108, A002694, A127529, A236406, A097610, A125181, A133156, A134264, A207538.
Sequence in context: A065266 A065260 A257794 * A127151 A193034 A254179
Adjacent sequences: A091891 A091892 A091893 * A091895 A091896 A091897


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Mar 10 2004


STATUS

approved



