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 - 2*k)*A055151(n-1,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
Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, Enumerating runs, valleys, and peaks in Catalan words, arXiv:2404.05672 [math.CO], 2024. See p. 7.
Jean-Luc Baril, Sergey Kirgizov, and Vincent Vanjovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, Disc. Math. 341 (2018) 2608-2615, Table 1.
Andrew M. Baxter, Refining enumeration schemes to count according to permutation statistics, arXiv:1401.0337 [math.CO], 2014.
Michael Bukata, Ryan Kulwicki, Nicholas Lewandowski, Lara Pudwell, Jacob Roth, and Teresa Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv:1812.07112 [math.CO], 2018.
David Callan, A variant of Touchard's Catalan number identity, arXiv:1204.5704 [math.CO], 2012. - N. J. A. Sloane, Oct 10 2012
David Callan, On Ascent, Repetition and Descent Sequences, arXiv:1911.02209 [math.CO], 2019.
Colin Defant, Postorder Preimages, arXiv:1604.01723 [math.CO], 2016.
Colin Defant, Stack-Sorting Preimages of Permutation Classes, arXiv:1809.03123 [math.CO], 2018.
Colin Defant, Counting 3-Stack-Sortable Permutations, arXiv:1903.09138 [math.CO], 2019.
Emeric Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202 (see pp. 192-193)..
M. Dziemiańczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, Counting pattern-avoiding permutations by big descents, arXiv:2408.15111 [math.CO], 2024. See p. 6.
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Nonleft peaks in Dyck paths: a combinatorial approach, Discrete Math., 337 (2014), 97-105.
Lara Pudwell, On the distribution of peaks (and other statistics), 16th International Conference on Permutation Patterns, Dartmouth College, 2018. [Broken link]
John Riordan, A Note on Catalan Parentheses, Amer. Math. Monthly, Vol. 80, No. 8 (1973), pp. 904-906.
Tom Roberts and Thomas Prellberg, Improving Convergence of Generalised Rosenbluth Sampling for Branched Polymer Models by Uniform Sampling, arXiv:2401.12201 [cond-mat.stat-mech], 2024. See p. 12.
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).
Lin Yang and Shengliang Yang, Protected Branches in Ordered Trees, J. Math. Study (2023) Vol. 56, No. 1, 1-17.
FORMULA
T(n,k) = 2^(n - 2*k - 1)*binomial(n-1,2*k)*binomial(2*k,k)/(k + 1), T(0,0) = 1, for 0 <= k <= floor((n-1)/2).
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 - 2*x - sqrt((1 - 2*x)^2 - 4*t*x^2)) / (2*t*x) with the inverse ginv(x,t) = x / (1 + 2*x + 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^(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 *)
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), n-1 - 2*k))} /* Michael Somos, Sep 25 2006 */
(GAP) T:=Concatenation([1], Flat(List([1..13], n->List([0..Int((n-1)/2)], k->2^(n-2*k-1)*Binomial(n-1, 2*k)*Binomial(2*k, k)/(k+1))))); # Muniru A Asiru, Nov 29 2018
(Sage) [1] + [[2^(n-2*k-1)*binomial(n-1, 2*k)*binomial(2*k, k)/(k+1) for k in (0..floor((n-1)/2))] for n in (1..12)] # G. C. Greubel, Nov 30 2018
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Mar 10 2004
STATUS
approved