A036765 - OEIS

A036765

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

1, 1, 2, 5, 13, 36, 104, 309, 939, 2905, 9118, 28964, 92940, 300808, 980864, 3219205, 10626023, 35252867, 117485454, 393133485, 1320357501, 4449298136, 15038769672, 50973266380, 173214422068, 589998043276, 2014026871496, 6889055189032, 23608722350440 (list; graph; refs; listen; history; text; internal format)

	OFFSET	`0,3`
	COMMENTS	`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` `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` `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` `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` `a(n) = number of noncrossing partitions of [n] in which all blocks are of size <= 3. - David Callan, Aug 27 2014`
	LINKS	`Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)` `C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.` `Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.` `Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.` `N. T. Cameron, Random walks, trees and extensions of Riordan group techniques, Dissertation, Howard University, 2002.` `Naiomi Cameron and J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, Article #16.6.1.` `Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.` `Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.` `Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908 [math.CO], 2012.` `M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.` `Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.` `Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015.` `Nickolas Hein and Jia Huang, Modular Catalan Numbers, European Journal of Combinatorics 61 (2017), 197-218.` `JiSun Huh, Sangwook Kim, Seunghyun Seo, and Heesung Shin, Bijections on pattern avoiding inversion sequences and related objects, arXiv:2404.04091 [math.CO], 2024. See p. 22.` `L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From N. J. A. Sloane, Jan 03 2013` `A. Sapounakis, I. Tasoulas, and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.` `L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).` `M. Wallner, Lattice Path Combinatorics, Diplomarbeit, Institut für Diskrete Mathematik und Geometrie der Technischen Universität Wien, 2013.` `Index entries for sequences related to rooted trees`
	FORMULA	`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+zA+(zA)^2+(zA)^3. - Emeric Deutsch, Nov 29 2003` `G.f.: F(x)/x where F(x) is the reversion of x/(1+x+x^2+x^3). - Joerg Arndt, Jun 10 2011` `From Paul D. Hanna, Feb 13 2011: (Start)` `O.g.f.: A(x) = exp( Sum_{n>=1} [Sum_{k=0..n} C(n,k)^2x^kA(x)^k] x^n/n ).` `O.g.f.: A(x) = exp( Sum_{n>=1} [Sum_{k>=0} C(n+k,k)^2x^kA(x)^k](1-xA(x))^(2n+1) x^n/n ). (End)` `From Paul D. Hanna, Feb 24 2011: (Start)` `O.g.f.: A(x) = 1/(1-x)exp( Sum_{n>=1} A(x)^nSum_{k=0..n-1} C(n-1,k)C(n,k)x^k)/(1-x)^(2n) * x^(2n)/n ).` `O.g.f.: A(x) = 1/(1-x)exp( Sum_{n>=1} A(x)^nSum_{k>=0} C(n+k-1,k)C(n+k,k)x^k) x^(2n)/n ). (End)` `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 MV iterates. - Gary W. Adamson, Jun 06 2011` `An infinite square production matrix M for the sequence is:` `1, 1, 0, 0, 0, 0, ...` `1, 0, 1, 0, 0, 0, ...` `2, 1, 0, 1, 0, 0, ...` `3, 2, 1, 0, 1, 0, ...` `4, 3, 2, 1, 0, 1, ...` `5, 4, 3, 2, 1, 0, ...` `..., such that a(n) is the top left term of M^n. - Gary W. Adamson, Feb 21 2012` `D-finite with recurrence: 2(n+1)(2n+3)(13n-1)a(n) = (143n^3 + 132n^2 - 17n - 18)a(n-1) + 4(n-1)(26n^2 + 11n - 6)a(n-2) + 16(n-2)(n-1)(13n + 12)a(n-3). - Vaclav Kotesovec, Sep 09 2013` `a(n) ~ cd^n/n^(3/2), where d = 1/12((6371+624sqrt(78))^(2/3)+11(6371+624sqrt(78))^(1/3)+217)/(6371+624sqrt(78))^(1/3) = 3.610718613276... is the root of the equation -16-8d-11d^2+4d^3=0 and c = sqrt(f/Pi) = 0.9102276936417..., where f = 1/9984(9295 + (13(45085576939 - 795629568sqrt(78)))^(1/3) + (13(45085576939 + 795629568sqrt(78)))^(1/3)) is the root of the equation -128+1696f-9295f^2+3328f^3=0. - Vaclav Kotesovec, Sep 10 2013` `From Peter Bala, Jun 21 2015: (Start)` `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 - 2k) by the Lagrange-Bürmann formula.` `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 - 2k). Cf. A186241, A198951, A200731. (End)` `a(n) = hypergeom([-n-1, (1-n)/2, -n/2], [1, 3/2], -1). - Vladimir Reshetnikov, Oct 15 2018`
	EXAMPLE	`a(4) = 13 since the top row of M^4 = (13, 8, 4, 1, 1).` `From Joerg Arndt, Oct 31 2012: (Start)` `a(5)=36 because there are 36 Dyck words of length 5 that avoid "1111":` `[ #] RGS rises Dyck word` `[ 1] [ . . . . . ] [ . . . . . ] 1.1.1.1.1.` `[ 2] [ . . . . 1 ] [ . . . . 1 ] 1.1.1.11..` `[ 3] [ . . . 1 . ] [ . . . 1 . ] 1.1.11..1.` `[ 4] [ . . . 1 1 ] [ . . . 1 . ] 1.1.11.1..` `[ 5] [ . . . 1 2 ] [ . . . 1 2 ] 1.1.111...` `[ 6] [ . . 1 . . ] [ . . 1 . . ] 1.11..1.1.` `[ 7] [ . . 1 . 1 ] [ . . 1 . 1 ] 1.11..11..` `[ 8] [ . . 1 1 . ] [ . . 1 . . ] 1.11.1..1.` `[ 9] [ . . 1 1 1 ] [ . . 1 . . ] 1.11.1.1..` `[10] [ . . 1 1 2 ] [ . . 1 . 1 ] 1.11.11...` `[11] [ . . 1 2 . ] [ . . 1 2 . ] 1.111...1.` `[12] [ . . 1 2 1 ] [ . . 1 2 . ] 1.111..1..` `[13] [ . . 1 2 2 ] [ . . 1 2 . ] 1.111.1...` `[--] [ . . 1 2 3 ] [ . . 1 2 3 ] 1.1111....` `[14] [ . 1 . . . ] [ . 1 . . . ] 11..1.1.1.` `[15] [ . 1 . . 1 ] [ . 1 . . 1 ] 11..1.11..` `[16] [ . 1 . 1 . ] [ . 1 . 1 . ] 11..11..1.` `[17] [ . 1 . 1 1 ] [ . 1 . 1 . ] 11..11.1..` `[18] [ . 1 . 1 2 ] [ . 1 . 1 2 ] 11..111...` `[19] [ . 1 1 . . ] [ . 1 . . . ] 11.1..1.1.` `[20] [ . 1 1 . 1 ] [ . 1 . . 1 ] 11.1..11..` `[21] [ . 1 1 1 . ] [ . 1 . . . ] 11.1.1..1.` `[22] [ . 1 1 1 1 ] [ . 1 . . . ] 11.1.1.1..` `[23] [ . 1 1 1 2 ] [ . 1 . . 1 ] 11.1.11...` `[24] [ . 1 1 2 . ] [ . 1 . 1 . ] 11.11...1.` `[25] [ . 1 1 2 1 ] [ . 1 . 1 . ] 11.11..1..` `[26] [ . 1 1 2 2 ] [ . 1 . 1 . ] 11.11.1...` `[27] [ . 1 1 2 3 ] [ . 1 . 1 2 ] 11.111....` `[28] [ . 1 2 . . ] [ . 1 2 . . ] 111...1.1.` `[29] [ . 1 2 . 1 ] [ . 1 2 . 1 ] 111...11..` `[30] [ . 1 2 1 . ] [ . 1 2 . . ] 111..1..1.` `[31] [ . 1 2 1 1 ] [ . 1 2 . . ] 111..1.1..` `[32] [ . 1 2 1 2 ] [ . 1 2 . 1 ] 111..11...` `[33] [ . 1 2 2 . ] [ . 1 2 . . ] 111.1...1.` `[34] [ . 1 2 2 1 ] [ . 1 2 . . ] 111.1..1..` `[35] [ . 1 2 2 2 ] [ . 1 2 . . ] 111.1.1...` `[36] [ . 1 2 2 3 ] [ . 1 2 . 1 ] 111.11....` `[--] [ . 1 2 3 . ] [ . 1 2 3 . ] 1111....1.` `[--] [ . 1 2 3 1 ] [ . 1 2 3 . ] 1111...1..` `[--] [ . 1 2 3 2 ] [ . 1 2 3 . ] 1111..1...` `[--] [ . 1 2 3 3 ] [ . 1 2 3 . ] 1111.1....` `[--] [ . 1 2 3 4 ] [ . 1 2 3 4 ] 11111.....` `(Dots are used for zeros for readability.)` `(End)`
	MAPLE	`r := 3; [ seq((1/n)add( (-1)^jbinomial(n, j)binomial(2n-2-j*(r+1), n-1), j=0..floor((n-1)/(r+1))), n=1..30) ];` `# second Maple program:` b:= proc(u, o) option remember; `if`(u+o=0, 1, `add(b(u-j, o+j-1), j=1..min(1, u))+` `add(b(u+j-1, o-j), j=1..min(3, o)))` `end:` `a:= n-> b(0, n):` `seq(a(n), n=0..30); # Alois P. Heinz, Aug 28 2017`
	MATHEMATICA	`InverseSeries[Series[y/(1+y+y^2+y^3), {y, 0, 24}], x] (* then A(x)=y(x)/x ) ( Len Smiley, Apr 11 2000 )` `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]}]];` `a[n_] := b[0, n, 3];` `Table[a[n], {n, 0, 30}] ( Jean-François Alcover, Nov 05 2017, after Alois P. Heinz )` `Table[HypergeometricPFQ[{-n-1, (1-n)/2, -n/2}, {1, 3/2}, -1], {n, 0, 28}] ( Vladimir Reshetnikov, Oct 15 2018 *)`
	PROG	`(PARI) {a(n)=sum(j=0, n\2, binomial(n+1, n-2j)binomial(n+1, j))/(n+1)}` `(PARI) {a(n)=local(A=1+x+xO(x^n)); for(i=1, n, A=1+xA+(xA)^2+(xA)^3); polcoeff(A, n)}` `(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(xA+xO(x^n))^j)x^m/m))); polcoeff(A, n, x)}` `(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(xA+xO(x^n))^j)(1-xA)^(2m+1)x^m/m))); polcoeff(A, n, x)}` `(PARI) {a(n)=local(A=1+x); for(i=1, n, A=1/(1-x+xO(x^n))exp(sum(m=1, n, A^msum(k=0, m-1, binomial(m-1, k)binomial(m, k)x^k)/(1-x)^(2m)x^(2m)/m) +xO(x^n))); polcoeff(A, n)} /* Paul D. Hanna /` `(PARI) {a(n)=local(A=1+x); for(i=1, n, A=1/(1-x+xO(x^n))exp(sum(m=1, n, A^msum(k=0, n, binomial(m+k-1, k)binomial(m+k, k)x^k)x^(2m)/m) +xO(x^n))); polcoeff(A, n)} / Paul D. Hanna /` `(PARI) Vec(serreverse(x/(1+x+x^2+x^3)+O(x^66))/x) / Joerg Arndt, Jun 10 2011 /` `(Magma) [&+[Binomial(n+1, n-2k)*Binomial(n+1, k)/(n+1): k in [0..n]]: n in [0..30]]; // Vincenzo Librandi, Oct 16 2018`
	CROSSREFS	`Right hand column of triangle A064580. The sequence of sequences A000007 (0^n), A000012 (constant 1), A001006 (Motzkin), A036765, A036766, ... tends to A000108 (Catalan).` `Cf. A005725, A186241, A198951, A200731.` `Column k=3 of A288942.` `Sequence in context: A358460 A289453 A339290 * A246555 A366023 A136751` `Adjacent sequences: A036762 A036763 A036764 * A036766 A036767 A036768`
	KEYWORD	`nonn,easy`
	AUTHOR	`N. J. A. Sloane`
	EXTENSIONS	`Name clarified by Andrew Howroyd, Dec 04 2017`
	STATUS	`approved`