login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036765 Number of ordered rooted trees with n non-root nodes and all outdegrees <= three. 39
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) 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', RGS 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.

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.

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.

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.

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+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)^(2n) * 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^(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 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

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

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)^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 *)

PROG

(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 */

(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

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: A277996 A099164 A289453 * A246555 A136751 A154836

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 13 06:26 EST 2019. Contains 329968 sequences. (Running on oeis4.)