login
Number of ordered rooted trees with n non-root nodes and all outdegrees <= three.
44

%I #164 Apr 11 2024 10:50:14

%S 1,1,2,5,13,36,104,309,939,2905,9118,28964,92940,300808,980864,

%T 3219205,10626023,35252867,117485454,393133485,1320357501,4449298136,

%U 15038769672,50973266380,173214422068,589998043276,2014026871496,6889055189032,23608722350440

%N Number of ordered rooted trees with n non-root nodes and all outdegrees <= three.

%C Number of Dyck n-paths that avoid UUUU. For example, a(4)=13 counts all 14 Dyck 4-paths except UUUUDDDD. - _David Callan_, Dec 09 2004

%C Number of restricted growth strings for Dyck paths with at most 2 consecutive rises (this is equivalent to the comment above, see example). - _Joerg Arndt_, Oct 31 2012

%C Let A(x) be the g.f. for the sequence of numbers of Dyck words with at most k consecutive ones (paths with at most k consecutive up-steps 'U', Restricted Growth Strings with at most k-1 consecutive rises), then B(x) := x*A(x) is the series reversion of x/(1+x+x^2+...+x^k). - _Joerg Arndt_, Oct 31 2012

%C a(n) is the number of ordered unlabeled rooted trees on n+1 nodes where each node has no more than 3 children. - _Geoffrey Critzer_, Jan 05 2013

%C a(n) = number of noncrossing partitions of [n] in which all blocks are of size <= 3. - _David Callan_, Aug 27 2014

%H Alois P. Heinz, <a href="/A036765/b036765.txt">Table of n, a(n) for n = 0..1000</a> (first 201 terms from T. D. Noe)

%H C. Banderier and D. Merlini, <a href="http://algo.inria.fr/banderier/Papers/infjumps.ps">Lattice paths with an infinite set of jumps</a>, FPSAC02, Melbourne, 2002.

%H Paul Barry, <a href="http://dx.doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016) 343-385.

%H Paul Barry, <a href="https://arxiv.org/abs/2001.08799">Characterizations of the Borel triangle and Borel polynomials</a>, arXiv:2001.08799 [math.CO], 2020.

%H N. T. Cameron, <a href="https://www.math.hmc.edu/~cameron/dissertation.pdf">Random walks, trees and extensions of Riordan group techniques</a>, Dissertation, Howard University, 2002.

%H Naiomi Cameron and J. E. McLeod, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/McLeod/mcleod3.html">Returns and Hills on Generalized Dyck Paths</a>, Journal of Integer Sequences, Vol. 19, 2016, Article #16.6.1.

%H Colin Defant and Kai Zheng, <a href="https://arxiv.org/abs/2008.12297">Stack-Sorting with Consecutive-Pattern-Avoiding Stacks</a>, arXiv:2008.12297 [math.CO], 2020.

%H Isaac DeJager, Madeleine Naquin, and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.

%H Filippo Disanto and Thomas Wiehe, <a href="http://arxiv.org/abs/1210.6908">Some instances of a sub-permutation problem on pattern avoiding permutations</a>, arXiv preprint arXiv:1210.6908 [math.CO], 2012.

%H M. Dziemianczuk, <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 Petr Gregor, Torsten Mütze, and Namrata, <a href="https://arxiv.org/abs/2306.08420">Combinatorial generation via permutation languages. VI. Binary trees</a>, arXiv:2306.08420 [cs.DM], 2023.

%H Nickolas Hein and Jia Huang, <a href="http://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015.

%H Nickolas Hein and Jia Huang, <a href="https://doi.org/10.1016/j.ejc.2016.11.004">Modular Catalan Numbers</a>, European Journal of Combinatorics 61 (2017), 197-218.

%H JiSun Huh, Sangwook Kim, Seunghyun Seo, and Heesung Shin, <a href="https://arxiv.org/abs/2404.04091">Bijections on pattern avoiding inversion sequences and related objects</a>, arXiv:2404.04091 [math.CO], 2024. See p. 22.

%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a> (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013

%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. Takacs, <a href="https://drive.google.com/file/d/1K7dq0uhgY4aB-oIssyW4ipq16SvyE2Pu/view">Enumeration of rooted trees and forests</a>, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).

%H M. Wallner, <a href="http://dmg.tuwien.ac.at/drmota/Thesis_Wallner.pdf">Lattice Path Combinatorics</a>, Diplomarbeit, Institut für Diskrete Mathematik und Geometrie der Technischen Universität Wien, 2013.

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F a(n) = (1/(n+1))*sum(j=0..floor(n/2), binomial(n+1, n-2j)*binomial(n+1, j) ). G.f. A(z) satisfies A=1+z*A+(z*A)^2+(z*A)^3. - _Emeric Deutsch_, Nov 29 2003

%F G.f.: F(x)/x where F(x) is the reversion of x/(1+x+x^2+x^3). - _Joerg Arndt_, Jun 10 2011

%F From _Paul D. Hanna_, Feb 13 2011: (Start)

%F O.g.f.: A(x) = exp( Sum_{n>=1} [Sum_{k=0..n} C(n,k)^2*x^k*A(x)^k] * x^n/n ).

%F O.g.f.: A(x) = exp( Sum_{n>=1} [Sum_{k>=0} C(n+k,k)^2*x^k*A(x)^k]*(1-x*A(x))^(2*n+1)* x^n/n ). (End)

%F From _Paul D. Hanna_, Feb 24 2011: (Start)

%F O.g.f.: A(x) = 1/(1-x)*exp( Sum_{n>=1} A(x)^n*Sum_{k=0..n-1} C(n-1,k)*C(n,k)*x^k)/(1-x)^(2n) * x^(2*n)/n ).

%F O.g.f.: A(x) = 1/(1-x)*exp( Sum_{n>=1} A(x)^n*Sum_{k>=0} C(n+k-1,k)*C(n+k,k)*x^k) * x^(2n)/n ). (End)

%F Let M = an infinite quadradiagonal matrix with all 1's in every diagonal: (sub, main, super, and super-super), and the rest zeros. V = vector [1,0,0,0,...]. The sequence = left column terms of M*V iterates. - _Gary W. Adamson_, Jun 06 2011

%F An infinite square production matrix M for the sequence is:

%F 1, 1, 0, 0, 0, 0, ...

%F 1, 0, 1, 0, 0, 0, ...

%F 2, 1, 0, 1, 0, 0, ...

%F 3, 2, 1, 0, 1, 0, ...

%F 4, 3, 2, 1, 0, 1, ...

%F 5, 4, 3, 2, 1, 0, ...

%F ..., such that a(n) is the top left term of M^n. - _Gary W. Adamson_, Feb 21 2012

%F D-finite with recurrence: 2*(n+1)*(2*n+3)*(13*n-1)*a(n) = (143*n^3 + 132*n^2 - 17*n - 18)*a(n-1) + 4*(n-1)*(26*n^2 + 11*n - 6)*a(n-2) + 16*(n-2)*(n-1)*(13*n + 12)*a(n-3). - _Vaclav Kotesovec_, Sep 09 2013

%F a(n) ~ c*d^n/n^(3/2), where d = 1/12*((6371+624*sqrt(78))^(2/3)+11*(6371+624*sqrt(78))^(1/3)+217)/(6371+624*sqrt(78))^(1/3) = 3.610718613276... is the root of the equation -16-8*d-11*d^2+4*d^3=0 and c = sqrt(f/Pi) = 0.9102276936417..., where f = 1/9984*(9295 + (13*(45085576939 - 795629568*sqrt(78)))^(1/3) + (13*(45085576939 + 795629568*sqrt(78)))^(1/3)) is the root of the equation -128+1696*f-9295*f^2+3328*f^3=0. - _Vaclav Kotesovec_, Sep 10 2013

%F From _Peter Bala_, Jun 21 2015: (Start)

%F The coefficient of x^n in A(x)^r equals r/(n + r)*Sum_{k = 0..floor(n/2)} binomial(n + r,k)*binomial(n + r,n - 2*k) by the Lagrange-Bürmann formula.

%F O.g.f. A(x) = exp(Sum_{n >= 1} A005725(n)*x^n/n), where A005725(n) = Sum_{k = 0..floor(n/2)} binomial(n,k)*binomial(n,n - 2*k). Cf. A186241, A198951, A200731. (End)

%F a(n) = hypergeom([-n-1, (1-n)/2, -n/2], [1, 3/2], -1). - _Vladimir Reshetnikov_, Oct 15 2018

%e a(4) = 13 since the top row of M^4 = (13, 8, 4, 1, 1).

%e From _Joerg Arndt_, Oct 31 2012: (Start)

%e a(5)=36 because there are 36 Dyck words of length 5 that avoid "1111":

%e [ #] RGS rises Dyck word

%e [ 1] [ . . . . . ] [ . . . . . ] 1.1.1.1.1.

%e [ 2] [ . . . . 1 ] [ . . . . 1 ] 1.1.1.11..

%e [ 3] [ . . . 1 . ] [ . . . 1 . ] 1.1.11..1.

%e [ 4] [ . . . 1 1 ] [ . . . 1 . ] 1.1.11.1..

%e [ 5] [ . . . 1 2 ] [ . . . 1 2 ] 1.1.111...

%e [ 6] [ . . 1 . . ] [ . . 1 . . ] 1.11..1.1.

%e [ 7] [ . . 1 . 1 ] [ . . 1 . 1 ] 1.11..11..

%e [ 8] [ . . 1 1 . ] [ . . 1 . . ] 1.11.1..1.

%e [ 9] [ . . 1 1 1 ] [ . . 1 . . ] 1.11.1.1..

%e [10] [ . . 1 1 2 ] [ . . 1 . 1 ] 1.11.11...

%e [11] [ . . 1 2 . ] [ . . 1 2 . ] 1.111...1.

%e [12] [ . . 1 2 1 ] [ . . 1 2 . ] 1.111..1..

%e [13] [ . . 1 2 2 ] [ . . 1 2 . ] 1.111.1...

%e [--] [ . . 1 2 3 ] [ . . 1 2 3 ] 1.1111....

%e [14] [ . 1 . . . ] [ . 1 . . . ] 11..1.1.1.

%e [15] [ . 1 . . 1 ] [ . 1 . . 1 ] 11..1.11..

%e [16] [ . 1 . 1 . ] [ . 1 . 1 . ] 11..11..1.

%e [17] [ . 1 . 1 1 ] [ . 1 . 1 . ] 11..11.1..

%e [18] [ . 1 . 1 2 ] [ . 1 . 1 2 ] 11..111...

%e [19] [ . 1 1 . . ] [ . 1 . . . ] 11.1..1.1.

%e [20] [ . 1 1 . 1 ] [ . 1 . . 1 ] 11.1..11..

%e [21] [ . 1 1 1 . ] [ . 1 . . . ] 11.1.1..1.

%e [22] [ . 1 1 1 1 ] [ . 1 . . . ] 11.1.1.1..

%e [23] [ . 1 1 1 2 ] [ . 1 . . 1 ] 11.1.11...

%e [24] [ . 1 1 2 . ] [ . 1 . 1 . ] 11.11...1.

%e [25] [ . 1 1 2 1 ] [ . 1 . 1 . ] 11.11..1..

%e [26] [ . 1 1 2 2 ] [ . 1 . 1 . ] 11.11.1...

%e [27] [ . 1 1 2 3 ] [ . 1 . 1 2 ] 11.111....

%e [28] [ . 1 2 . . ] [ . 1 2 . . ] 111...1.1.

%e [29] [ . 1 2 . 1 ] [ . 1 2 . 1 ] 111...11..

%e [30] [ . 1 2 1 . ] [ . 1 2 . . ] 111..1..1.

%e [31] [ . 1 2 1 1 ] [ . 1 2 . . ] 111..1.1..

%e [32] [ . 1 2 1 2 ] [ . 1 2 . 1 ] 111..11...

%e [33] [ . 1 2 2 . ] [ . 1 2 . . ] 111.1...1.

%e [34] [ . 1 2 2 1 ] [ . 1 2 . . ] 111.1..1..

%e [35] [ . 1 2 2 2 ] [ . 1 2 . . ] 111.1.1...

%e [36] [ . 1 2 2 3 ] [ . 1 2 . 1 ] 111.11....

%e [--] [ . 1 2 3 . ] [ . 1 2 3 . ] 1111....1.

%e [--] [ . 1 2 3 1 ] [ . 1 2 3 . ] 1111...1..

%e [--] [ . 1 2 3 2 ] [ . 1 2 3 . ] 1111..1...

%e [--] [ . 1 2 3 3 ] [ . 1 2 3 . ] 1111.1....

%e [--] [ . 1 2 3 4 ] [ . 1 2 3 4 ] 11111.....

%e (Dots are used for zeros for readability.)

%e (End)

%p r := 3; [ seq((1/n)*add( (-1)^j*binomial(n,j)*binomial(2*n-2-j*(r+1), n-1),j=0..floor((n-1)/(r+1))), n=1..30) ];

%p # second Maple program:

%p b:= proc(u, o) option remember; `if`(u+o=0, 1,

%p add(b(u-j, o+j-1), j=1..min(1, u))+

%p add(b(u+j-1, o-j), j=1..min(3, o)))

%p end:

%p a:= n-> b(0, n):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Aug 28 2017

%t InverseSeries[Series[y/(1+y+y^2+y^3), {y, 0, 24}], x] (* then A(x)=y(x)/x *) (* _Len Smiley_, Apr 11 2000 *)

%t b[u_, o_, k_] := b[u, o, k] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1, k], {j, 1, Min[1, u]}] + Sum[b[u + j - 1, o - j, k], {j, 1, Min[k, o]}]];

%t a[n_] := b[0, n, 3];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 05 2017, after _Alois P. Heinz_ *)

%t Table[HypergeometricPFQ[{-n-1, (1-n)/2, -n/2}, {1, 3/2}, -1], {n, 0, 28}] (* _Vladimir Reshetnikov_, Oct 15 2018 *)

%o (PARI) {a(n)=sum(j=0,n\2,binomial(n+1, n-2*j)*binomial(n+1,j))/(n+1)}

%o (PARI) {a(n)=local(A=1+x+x*O(x^n));for(i=1,n,A=1+x*A+(x*A)^2+(x*A)^3);polcoeff(A,n)}

%o (PARI) {a(n)=local(A=1+x);for(i=1,n,A=exp(sum(m=1, n, sum(j=0, m, binomial(m, j)^2*(x*A+x*O(x^n))^j)*x^m/m)));polcoeff(A, n, x)}

%o (PARI) {a(n)=local(A=1+x);for(i=1,n,A=exp(sum(m=1, n, sum(j=0, n, binomial(m+j, j)^2*(x*A+x*O(x^n))^j)*(1-x*A)^(2*m+1)*x^m/m)));polcoeff(A, n, x)}

%o (PARI) {a(n)=local(A=1+x);for(i=1,n,A=1/(1-x+x*O(x^n))*exp(sum(m=1,n,A^m*sum(k=0,m-1,binomial(m-1,k)*binomial(m,k)*x^k)/(1-x)^(2*m)*x^(2*m)/m) +x*O(x^n)));polcoeff(A,n)} /* _Paul D. Hanna_ */

%o (PARI) {a(n)=local(A=1+x);for(i=1,n,A=1/(1-x+x*O(x^n))*exp(sum(m=1,n,A^m*sum(k=0,n,binomial(m+k-1,k)*binomial(m+k,k)*x^k)*x^(2*m)/m) +x*O(x^n)));polcoeff(A,n)} /* _Paul D. Hanna_ */

%o (PARI) Vec(serreverse(x/(1+x+x^2+x^3)+O(x^66))/x) /* _Joerg Arndt_, Jun 10 2011 */

%o (Magma) [&+[Binomial(n+1, n-2*k)*Binomial(n+1, k)/(n+1): k in [0..n]]: n in [0..30]]; // _Vincenzo Librandi_, Oct 16 2018

%Y Right hand column of triangle A064580. The sequence of sequences A000007 (0^n), A000012 (constant 1), A001006 (Motzkin), A036765, A036766, ... tends to A000108 (Catalan).

%Y Cf. A005725, A186241, A198951, A200731.

%Y Column k=3 of A288942.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_

%E Name clarified by _Andrew Howroyd_, Dec 04 2017