|
%I #133 Apr 11 2024 11:55:10
%S 1,1,2,4,1,8,6,16,24,2,32,80,20,64,240,120,5,128,672,560,70,256,1792,
%T 2240,560,14,512,4608,8064,3360,252,1024,11520,26880,16800,2520,42,
%U 2048,28160,84480,73920,18480,924,4096,67584,253440,295680,110880,11088,132
%N 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)].
%C 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).
%C 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
%C From _David Callan_, Oct 25 2004: (Start)
%C 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.
%C 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)
%C 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
%C 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
%C 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
%C 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
%C 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
%C The antidiagonal sums equal A152225. - _Johannes W. Meijer_, Sep 13 2012
%C 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
%D T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 4.3.
%H Alois P. Heinz, <a href="/A091894/b091894.txt">Rows n = 0..200, flattened</a>
%H Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, <a href="https://arxiv.org/abs/2404.05672">Enumerating runs, valleys, and peaks in Catalan words</a>, arXiv:2404.05672 [math.CO], 2024. See p. 7.
%H Jean-Luc Baril, Sergey Kirgizov, and Vincent Vanjovszki, <a href="https://doi.org/10.1016/j.disc.2018.06.001">Descent distribution on Catalan words avoiding a pattern of length at most three</a>, Disc. Math. 341 (2018) 2608-2615, Table 1.
%H Andrew M. Baxter, <a href="http://arxiv.org/abs/1401.0337">Refining enumeration schemes to count according to permutation statistics</a>, arXiv:1401.0337 [math.CO], 2014.
%H Michael Bukata, Ryan Kulwicki, Nicholas Lewandowski, Lara Pudwell, Jacob Roth, Teresa Wheeland, <a href="https://arxiv.org/abs/1812.07112">Distributions of Statistics over Pattern-Avoiding Permutations</a>, arXiv:1812.07112 [math.CO], 2018.
%H David Callan, <a href="http://arxiv.org/abs/1204.5704">A variant of Touchard's Catalan number identity</a>, arXiv:1204.5704 [math.CO], 2012. - _N. J. A. Sloane_, Oct 10 2012
%H David Callan, <a href="https://arxiv.org/abs/1911.02209">On Ascent, Repetition and Descent Sequences</a>, arXiv:1911.02209 [math.CO], 2019.
%H Colin Defant, <a href="http://arxiv.org/abs/1604.01723">Postorder Preimages</a>, arXiv:1604.01723 [math.CO], 2016.
%H Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-Sorting Preimages of Permutation Classes</a>, arXiv:1809.03123 [math.CO], 2018.
%H Colin Defant, <a href="https://arxiv.org/abs/1903.09138">Counting 3-Stack-Sortable Permutations</a>, arXiv:1903.09138 [math.CO], 2019.
%H Emeric Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00371-9">Dyck path enumeration</a>, Discrete Math., 204, 1999, 167-202 (see pp. 192-193)..
%H M. Dziemiańczuk, <a href="http://dx.doi.org/10.1016/j.disc.2014.07.024">Enumerations of plane trees with multiple edges and Raney lattice paths</a>, Discrete Mathematics 337 (2014): 9-24.
%H K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2014.07.015">Nonleft peaks in Dyck paths: a combinatorial approach</a>, Discrete Math., 337 (2014), 97-105.
%H Lara Pudwell, <a href="http://permutationpatterns.com/slides/Pudwell.pdf">On the distribution of peaks (and other statistics)</a>, 16th International Conference on Permutation Patterns, Dartmouth College, 2018.
%H John Riordan, <a href="http://www.jstor.org/stable/2319398">A Note on Catalan Parentheses</a>, Amer. Math. Monthly, Vol. 80, No. 8 (1973), pp. 904-906.
%H Tom Roberts and Thomas Prellberg, <a href="https://arxiv.org/abs/2401.12201">Improving Convergence of Generalised Rosenbluth Sampling for Branched Polymer Models by Uniform Sampling</a>, arXiv:2401.12201 [cond-mat.stat-mech], 2024. See p. 12.
%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%H L. W. Shapiro, <a href="http://dx.doi.org/10.1016/0097-3165(76)90034-0">A short proof of an identity of Touchard's concerning Catalan numbers</a>, J. Combin. Theory Ser. A 20 (1976) 375-376.
%H Guoce Xin and Jing-Feng Xu, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p177">A short approach to Catalan numbers modulo 2^r</a>, Electronic Journal of Combinatorics Vol. 18 Issue 1 (2011), #P177 (see page 2).
%H Lin Yang and Shengliang Yang, <a href="https://doi.org/10.4208/jms.v56n1.23.01">Protected Branches in Ordered Trees</a>, J. Math. Study (2023) Vol. 56, No. 1, 1-17.
%H <a href="/index/Lu#Lukasiewicz">Index entries for sequences related to Łukasiewicz</a>
%F 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).
%F G.f.: G = G(t,z) satisfies: t*z*G^2 - (1 - 2*z + 2*t*z)*G + 1 - z + t*z = 0.
%F 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
%F 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
%e 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].
%e Triangle begins:
%e 1;
%e 1;
%e 2;
%e 4, 1;
%e 8, 6;
%e 16, 24, 2;
%e 32, 80, 20;
%e 64, 240, 120, 5;
%e 128, 672, 560, 70;
%e 256, 1792, 2240, 560, 14;
%e ...
%p 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);
%t 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 *)
%t 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 *)
%t 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 *)
%o (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 */
%o (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
%o (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
%Y The first few columns equal A011782, A001788, 2*A003472, 5*A002409, 14*A140325 and 42*A172242. - _Johannes W. Meijer_, Sep 13 2012
%Y Cf. A000108, A002694, A127529, A236406, A097610, A125181, A133156, A134264, A207538.
%K nonn,tabf
%O 0,3
%A _Emeric Deutsch_, Mar 10 2004
|
