0,3

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

Binomial transform of A001005. - Seiichi Manyama, Sep 19 2025

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)

Cyril Banderier and Donnatella 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.

Mariusz Białecki, Arpan Bagchi, and Yohei Tutiya, The Random Domino Automaton on the Bethe Lattice and Power-Law Cluster-Size Distributions, Entropy (2025) Vol. 27, Issue 12, Art. 1226. See Sect. 5.4.

Naiomi Tuere Cameron, Random walks, trees and extensions of Riordan group techniques, Ph. D. Dissertation, Howard Univ., 2002.

Naiomi Cameron and Jillian E. McLeod, Returns and Hills on Generalized Dyck Paths, J. Int. Seq. (2016) Vol. 19, Art. 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. [Broken link]

Isaac DeJager, Madeleine Naquin, Frank Seidl, and Paul Drube, Colored Motzkin Paths of Higher Order, J. Int. Seq. (2021) Vol. 24, Art. 21.4.6. See p. 20, Table 6. See also arXiv:2012.14947 [math.CO], 2020. See p. 18, Table 5

Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908 [math.CO], 2012.

Maciej Dziemiańczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Disc. Math. (2014) Vol. 337, 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, Europ. J. Combin. (2017) Vol. 61, 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.

Lara 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, Disc. Math. (2007) Vol. 307, 2909-2924.

Lajos Takács, Enumeration of rooted trees and forests, Math. Scientist (1993) Vol. 18, 1-10, esp. Eq. (6).

Michael Wallner, Lattice Path Combinatorics, Diplomarbeit, Institut für Diskrete Mathematik und Geometrie der Technischen Universität Wien, 2013.

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

a(n) = Sum_{k=0..n} binomial(n,k) * A001005(k). - Seiichi Manyama, Sep 19 2025

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)

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) ];

# Alternative:

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

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

(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

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. A001005, A005725, A186241, A200731.

Column k=3 of A288942.

Cf. A198951, A369444.

Sequence in context: A358460 A289453 A339290 * A246555 A366023 A136751

Adjacent sequences: A036762 A036763 A036764 * A036766 A036767 A036768

nonn,easy

Name clarified by Andrew Howroyd, Dec 04 2017

approved