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
Offset: 0
Examples
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)
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.
- Paul Barry, d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths, arXiv:2505.16718 [math.CO], 2025. See p. 25.
- 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
Crossrefs
Programs
-
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
-
Maple
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) ]; # 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 *) -
PARI
{a(n)=sum(j=0,n\2,binomial(n+1, n-2*j)*binomial(n+1,j))/(n+1)} -
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)} -
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)} -
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)} -
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 */ -
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 */ -
PARI
Vec(serreverse(x/(1+x+x^2+x^3)+O(x^66))/x) /* Joerg Arndt, Jun 10 2011 */
Formula
a(n) = (1/(n+1))*Sum_{j=0..floor(n/2)} binomial(n+1, n-2*j)*binomial(n+1, j). G.f. A(z) satisfies A=1+z*A+(z*A)^2+(z*A)^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)^2*x^k*A(x)^k) * x^n/n ).
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)
From Paul D. Hanna, Feb 24 2011: (Start)
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)^(2*n) * x^(2*n)/n ).
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^(2*n)/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 M*V 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)*(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
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
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 - 2*k) 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 - 2*k). Cf. A186241, A198951, A200731. (End)
a(n) = hypergeom([-n-1, (1-n)/2, -n/2], [1, 3/2], -1). - Vladimir Reshetnikov, Oct 15 2018
Extensions
Name clarified by Andrew Howroyd, Dec 04 2017
Comments