login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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(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, 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 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 DUU's. Then reverse the resulting Dyck n-path 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 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, 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 231-avoiding permutations according to the number of peaks, i.e., positions w[i-1] < 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^(n-1-2k)*A055151(n-1,k). - Kyle Petersen, Aug 02 2013

REFERENCES

Colin Defant, Postorder Preimages, arXiv preprint arXiv:1604.01723, 2016

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. - From N. J. A. Sloane, Oct 10 2012

E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202 (see pp. 192-193)..

M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.

K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Nonleft peaks in Dyck paths: a combinatorial approach, Discrete Math., 337 (2014), 97-105.

John Riordan, A Note on Catalan Parentheses, Amer. Math. Monthly, Vol. 80, No. 8 (1973), pp. 904-906.

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

L. W. Shapiro, A short proof of an identity of Touchard's concerning Catalan numbers, J. Combin. Theory Ser. A 20 (1976) 375-376.

Guoce Xin and Jing-Feng 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^(n-2k-1)*binomial(n-1,2k)*binomial(2*k,k)/(k+1); T(0,0)=1.

G.f.: G = G(t,z) satisfies: t*z*G^2-(1-2*z+2*t*z)*G+1-z+t*z = 0.

With first row zero, the o.g.f. is g(x,t) = [1 - 2x - sqrt[(1-2x)^2-4tx^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

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 accidentally on it. Perhaps someone can find a relationship here? Thies Heidecke (theidecke(AT)astrophysik.uni-kiel.de), Sep 23 2008 *)

Join[{1}, Select[Flatten[Table[2^(n-2k-1) Binomial[n-1, 2k] Binomial[2k, k]/ (k+1), {n, 20}, {k, 0, n}]], #!=0&]] (* Harvey P. Dale, Mar 05 2012 *)

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, A127529, A236406.

The first few columns equal A011782, A001788, 2*A003472, 5*A002409, 14*A140325 and 42*A172242. - Johannes W. Meijer, Sep 13 2012

Cf. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 24 00:59 EDT 2017. Contains 285338 sequences.