This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A036765 #172 May 26 2025 09:52:12
%S A036765 1,1,2,5,13,36,104,309,939,2905,9118,28964,92940,300808,980864,
%T A036765 3219205,10626023,35252867,117485454,393133485,1320357501,4449298136,
%U A036765 15038769672,50973266380,173214422068,589998043276,2014026871496,6889055189032,23608722350440
%N A036765 Number of ordered rooted trees with n non-root nodes and all outdegrees <= three.
%C A036765 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 A036765 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 A036765 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 A036765 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 A036765 a(n) = number of noncrossing partitions of [n] in which all blocks are of size <= 3. - _David Callan_, Aug 27 2014
%H A036765 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 A036765 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 A036765 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 A036765 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 A036765 Paul Barry, <a href="https://arxiv.org/abs/2505.16718">d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths</a>, arXiv:2505.16718 [math.CO], 2025. See p. 25.
%H A036765 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 A036765 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 A036765 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 A036765 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 A036765 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 A036765 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 A036765 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 A036765 Nickolas Hein and Jia Huang, <a href="http://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015.
%H A036765 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 A036765 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 A036765 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 A036765 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 A036765 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 A036765 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 A036765 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A036765 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
%F A036765 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 A036765 From _Paul D. Hanna_, Feb 13 2011: (Start)
%F A036765 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 A036765 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 A036765 From _Paul D. Hanna_, Feb 24 2011: (Start)
%F A036765 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 ).
%F A036765 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)
%F A036765 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 A036765 An infinite square production matrix M for the sequence is:
%F A036765 1, 1, 0, 0, 0, 0, ...
%F A036765 1, 0, 1, 0, 0, 0, ...
%F A036765 2, 1, 0, 1, 0, 0, ...
%F A036765 3, 2, 1, 0, 1, 0, ...
%F A036765 4, 3, 2, 1, 0, 1, ...
%F A036765 5, 4, 3, 2, 1, 0, ...
%F A036765 ..., such that a(n) is the top left term of M^n. - _Gary W. Adamson_, Feb 21 2012
%F A036765 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 A036765 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 A036765 From _Peter Bala_, Jun 21 2015: (Start)
%F A036765 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 A036765 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 A036765 a(n) = hypergeom([-n-1, (1-n)/2, -n/2], [1, 3/2], -1). - _Vladimir Reshetnikov_, Oct 15 2018
%e A036765 a(4) = 13 since the top row of M^4 = (13, 8, 4, 1, 1).
%e A036765 From _Joerg Arndt_, Oct 31 2012: (Start)
%e A036765 a(5)=36 because there are 36 Dyck words of length 5 that avoid "1111":
%e A036765 [ #] RGS rises Dyck word
%e A036765 [ 1] [ . . . . . ] [ . . . . . ] 1.1.1.1.1.
%e A036765 [ 2] [ . . . . 1 ] [ . . . . 1 ] 1.1.1.11..
%e A036765 [ 3] [ . . . 1 . ] [ . . . 1 . ] 1.1.11..1.
%e A036765 [ 4] [ . . . 1 1 ] [ . . . 1 . ] 1.1.11.1..
%e A036765 [ 5] [ . . . 1 2 ] [ . . . 1 2 ] 1.1.111...
%e A036765 [ 6] [ . . 1 . . ] [ . . 1 . . ] 1.11..1.1.
%e A036765 [ 7] [ . . 1 . 1 ] [ . . 1 . 1 ] 1.11..11..
%e A036765 [ 8] [ . . 1 1 . ] [ . . 1 . . ] 1.11.1..1.
%e A036765 [ 9] [ . . 1 1 1 ] [ . . 1 . . ] 1.11.1.1..
%e A036765 [10] [ . . 1 1 2 ] [ . . 1 . 1 ] 1.11.11...
%e A036765 [11] [ . . 1 2 . ] [ . . 1 2 . ] 1.111...1.
%e A036765 [12] [ . . 1 2 1 ] [ . . 1 2 . ] 1.111..1..
%e A036765 [13] [ . . 1 2 2 ] [ . . 1 2 . ] 1.111.1...
%e A036765 [--] [ . . 1 2 3 ] [ . . 1 2 3 ] 1.1111....
%e A036765 [14] [ . 1 . . . ] [ . 1 . . . ] 11..1.1.1.
%e A036765 [15] [ . 1 . . 1 ] [ . 1 . . 1 ] 11..1.11..
%e A036765 [16] [ . 1 . 1 . ] [ . 1 . 1 . ] 11..11..1.
%e A036765 [17] [ . 1 . 1 1 ] [ . 1 . 1 . ] 11..11.1..
%e A036765 [18] [ . 1 . 1 2 ] [ . 1 . 1 2 ] 11..111...
%e A036765 [19] [ . 1 1 . . ] [ . 1 . . . ] 11.1..1.1.
%e A036765 [20] [ . 1 1 . 1 ] [ . 1 . . 1 ] 11.1..11..
%e A036765 [21] [ . 1 1 1 . ] [ . 1 . . . ] 11.1.1..1.
%e A036765 [22] [ . 1 1 1 1 ] [ . 1 . . . ] 11.1.1.1..
%e A036765 [23] [ . 1 1 1 2 ] [ . 1 . . 1 ] 11.1.11...
%e A036765 [24] [ . 1 1 2 . ] [ . 1 . 1 . ] 11.11...1.
%e A036765 [25] [ . 1 1 2 1 ] [ . 1 . 1 . ] 11.11..1..
%e A036765 [26] [ . 1 1 2 2 ] [ . 1 . 1 . ] 11.11.1...
%e A036765 [27] [ . 1 1 2 3 ] [ . 1 . 1 2 ] 11.111....
%e A036765 [28] [ . 1 2 . . ] [ . 1 2 . . ] 111...1.1.
%e A036765 [29] [ . 1 2 . 1 ] [ . 1 2 . 1 ] 111...11..
%e A036765 [30] [ . 1 2 1 . ] [ . 1 2 . . ] 111..1..1.
%e A036765 [31] [ . 1 2 1 1 ] [ . 1 2 . . ] 111..1.1..
%e A036765 [32] [ . 1 2 1 2 ] [ . 1 2 . 1 ] 111..11...
%e A036765 [33] [ . 1 2 2 . ] [ . 1 2 . . ] 111.1...1.
%e A036765 [34] [ . 1 2 2 1 ] [ . 1 2 . . ] 111.1..1..
%e A036765 [35] [ . 1 2 2 2 ] [ . 1 2 . . ] 111.1.1...
%e A036765 [36] [ . 1 2 2 3 ] [ . 1 2 . 1 ] 111.11....
%e A036765 [--] [ . 1 2 3 . ] [ . 1 2 3 . ] 1111....1.
%e A036765 [--] [ . 1 2 3 1 ] [ . 1 2 3 . ] 1111...1..
%e A036765 [--] [ . 1 2 3 2 ] [ . 1 2 3 . ] 1111..1...
%e A036765 [--] [ . 1 2 3 3 ] [ . 1 2 3 . ] 1111.1....
%e A036765 [--] [ . 1 2 3 4 ] [ . 1 2 3 4 ] 11111.....
%e A036765 (Dots are used for zeros for readability.)
%e A036765 (End)
%p A036765 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 A036765 # second Maple program:
%p A036765 b:= proc(u, o) option remember; `if`(u+o=0, 1,
%p A036765 add(b(u-j, o+j-1), j=1..min(1, u))+
%p A036765 add(b(u+j-1, o-j), j=1..min(3, o)))
%p A036765 end:
%p A036765 a:= n-> b(0, n):
%p A036765 seq(a(n), n=0..30); # _Alois P. Heinz_, Aug 28 2017
%t A036765 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 A036765 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 A036765 a[n_] := b[0, n, 3];
%t A036765 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 05 2017, after _Alois P. Heinz_ *)
%t A036765 Table[HypergeometricPFQ[{-n-1, (1-n)/2, -n/2}, {1, 3/2}, -1], {n, 0, 28}] (* _Vladimir Reshetnikov_, Oct 15 2018 *)
%o A036765 (PARI) {a(n)=sum(j=0,n\2,binomial(n+1, n-2*j)*binomial(n+1,j))/(n+1)}
%o A036765 (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 A036765 (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 A036765 (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 A036765 (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 A036765 (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 A036765 (PARI) Vec(serreverse(x/(1+x+x^2+x^3)+O(x^66))/x) /* _Joerg Arndt_, Jun 10 2011 */
%o A036765 (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 A036765 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 A036765 Cf. A005725, A186241, A198951, A200731.
%Y A036765 Column k=3 of A288942.
%K A036765 nonn,easy
%O A036765 0,3
%A A036765 _N. J. A. Sloane_
%E A036765 Name clarified by _Andrew Howroyd_, Dec 04 2017