A036765 -id:A036765 - cp's OEIS frontend

A288942 Number A(n,k) of ordered rooted trees with n non-root nodes and all outdegrees <= k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 4, 1, 0, 1, 1, 2, 5, 9, 1, 0, 1, 1, 2, 5, 13, 21, 1, 0, 1, 1, 2, 5, 14, 36, 51, 1, 0, 1, 1, 2, 5, 14, 41, 104, 127, 1, 0, 1, 1, 2, 5, 14, 42, 125, 309, 323, 1, 0, 1, 1, 2, 5, 14, 42, 131, 393, 939, 835, 1, 0

Offset: 0

Alois P. Heinz, Sep 01 2017

Also the number of Dyck paths of semilength n with all ascent lengths <= k. A(4,2) = 9: /\/\/\/\, //\\/\/\, /\//\\/\, /\/\//\\, //\/\\/\, //\/\/\\, /\//\/\\, //\\//\\, //\//\\\.

Also the number of permutations p of [n] such that in 0p all up-jumps are <= k and no down-jump is larger than 1. An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here. A(4,2) = 9: 1234, 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2431.

			A(4,2) = 9:
.
.   o    o      o      o      o      o       o      o       o
.   |    |      |      |     / \    / \     / \    / \     / \
.   o    o      o      o    o   o  o   o   o   o  o   o   o   o
.   |    |     / \    / \   |          |  ( )        ( )  |   |
.   o    o    o   o  o   o  o          o  o o        o o  o   o
.   |   / \   |          |  |          |
.   o  o   o  o          o  o          o
.   |
.   o
.
Square array A(n,k) begins:
  1, 1,   1,   1,    1,    1,    1,    1,    1, ...
  0, 1,   1,   1,    1,    1,    1,    1,    1, ...
  0, 1,   2,   2,    2,    2,    2,    2,    2, ...
  0, 1,   4,   5,    5,    5,    5,    5,    5, ...
  0, 1,   9,  13,   14,   14,   14,   14,   14, ...
  0, 1,  21,  36,   41,   42,   42,   42,   42, ...
  0, 1,  51, 104,  125,  131,  132,  132,  132, ...
  0, 1, 127, 309,  393,  421,  428,  429,  429, ...
  0, 1, 323, 939, 1265, 1385, 1421, 1429, 1430, ...

Alois P. Heinz, Rows n = 0..140, flattened
N. Hein and J. Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015
Index entries for sequences related to rooted trees

Columns k=0..10 give: A000007, A000012, A001006, A036765, A036766, A036767, A036768, A036769, A291823, A291824, A291825.
Main diagonal (and upper diagonals) give A000108.
First lower diagonal gives A001453.
Cf. A203717.

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(1, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
A:= (n, k)-> b(0, n, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

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_, k_] := b[0, n, k];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Oct 27 2017, translated from Maple *)

T(n,k)=polcoeff(serreverse(x*(1-x)/(1-x*x^k) + O(x^2*x^n)), n+1);
for(n=0, 10, for(k=0, 10, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 29 2017

A(n,k) = Sum_{j=0..k} A203717(n,j).
G.f. of column k: G(x)/x where G(x) is the reversion of x*(1-x)/(1-x^(k+1)). - Andrew Howroyd, Nov 30 2017
G.f. g_k(x) of column k satisfies: g_k(x) = Sum_{j=0..k} (x*g_k(x))^j. - Alois P. Heinz, May 05 2019
A(n,k) = Sum_{j=0..n/(k+1)} (-1)^j/(n+1) * binomial(n+1,j) * binomial(2*n-j*(k+1),n). [Hein Eq (10)] - R. J. Mathar, Oct 14 2022; corrected by Tijn Caspar de Leeuw, Jul 07 2024

A200718 G.f. satisfies A(x) = (1 + xA(x)^2) (1 + x^2*A(x)^6).

Original entry on oeis.org

1, 1, 3, 14, 75, 433, 2636, 16668, 108399, 720431, 4871555, 33409042, 231817448, 1624503716, 11480658056, 81731416480, 585579734959, 4219179476875, 30552067317233, 222225174139730, 1622894404239115, 11894991079960721, 87472260252499560, 645183802300787356, 4771926560361458884

Offset: 0

Paul D. Hanna, Nov 21 2011

nonn

More generally, for fixed parameters p and q, if F(x) satisfies:
F(x) = exp( Sum_{n>=1} x^n * F(x)^(n*p)/n * [Sum_{k=0..n} C(n,k)^2 * x^k * F(x)^(k*q)] ),
then F(x) = (1 + x*F(x)^(p+1))*(1 + x^2*F(x)^(p+q+1)).

			G.f.: A(x) = 1 + x + 3*x^2 + 14*x^3 + 75*x^4 + 433*x^5 + 2636*x^6 +...
Related expansions:
A(x)^2 = 1 + 2*x + 7*x^2 + 34*x^3 + 187*x^4 + 1100*x^5 + 6784*x^6 +...
A(x)^6 = 1 + 6*x + 33*x^2 + 194*x^3 + 1200*x^4 + 7674*x^5 + 50317*x^6 +...
A(x)^8 = 1 + 8*x + 52*x^2 + 336*x^3 + 2210*x^4 + 14776*x^5 + 100216*x^6 +...
where A(x) = 1 + x*A(x)^2 + x^2*A(x)^6 + x^3*A(x)^8.
The logarithm of the g.f. A = A(x) equals the series:
log(A(x)) = (1 + x*A^4)*x*A + (1 + 2^2*x*A^4 + x^2*A^8)*x^2*A^2/2 +
(1 + 3^2*x*A^4 + 3^2*x^2*A^8 + x^3*A^12)*x^3*A^3/3 +
(1 + 4^2*x*A^4 + 6^2*x^2*A^8 + 4^2*x^3*A^12 + x^4*A^16)*x^4*A^4/4 +
(1 + 5^2*x*A^4 + 10^2*x^2*A^8 + 10^2*x^3*A^12 + 5^2*x^4*A^16 + x^5*A^20)*x^5*A^5/5 + ...
The g.f. of A104545, G(x) = A(x/G(x)^2) where A(x) = G(x*A(x)^2), begins:
G(x) = 1 + x + x^2 + 3*x^3 + 5*x^4 + 11*x^5 + 25*x^6 + 55*x^7 + 129*x^8 +...

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
Vaclav Kotesovec, Recurrence (of order 6)

Cf. A104545, A200716, A200717, A199876, A199877, A198951, A198953, A198957, A192415, A198888, A036765.

Cf. A186241, A199874, A200074, A200075, A200719, A215576.

a[n_] := Sum[Binomial[2*n + 2*k + 1, k]*Binomial[2*n + 2*k + 1, n - 2*k]/ (2*n + 2*k + 1), {k, 0, n/2}];
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Jan 09 2018, after Vladimir Kruchinin *)

a(n):=sum((binomial(2*n+2*k+1,k)*binomial(2*n+2*k+1,n-2*k))/(2*n+2*k+1),k,0,(n)/2); /* Vladimir Kruchinin, Mar 11 2016 */

{a(n)=polcoeff(sqrt( (1/x)*serreverse( 2*x^5*(1+x)^2/(1 - 2*x^2*(1+x)^2 - sqrt(1 - 4*x^2*(1+x)^2+O(x^(n+6)))) ) ),n)}

{a(n)=local(p=1,q=4,A=1+x);for(i=1,n,A=(1+x*A^(p+1))*(1+x^2*A^(p+q+1))+x*O(x^n));polcoeff(A,n)}

{a(n)=local(p=1,q=4,A=1+x);for(i=1,n,A=exp(sum(m=1,n,x^m*(A+x*O(x^n))^(p*m)/m*sum(j=0,m,binomial(m, j)^2*x^j*(A+x*O(x^n))^(q*j))))); polcoeff(A, n, x)}

{a(n)=local(p=1,q=4,A=1+x);for(i=1,n,A=exp(sum(m=1,n,x^m*(A+x*O(x^n))^(p*m)/m*(1-x*A^q)^(2*m+1)*sum(j=0, n, binomial(m+j, j)^2*x^j*(A+x*O(x^n))^(q*j))))); polcoeff(A, n, x)}

G.f. A(x) satisfies:
(1) A(x) = sqrt( (1/x)*Series_Reversion( 2*x^5*(1+x)^2/(1 - 2*x^2*(1+x)^2 - sqrt(1 - 4*x^2*(1+x)^2)) ) ).
(2) A(x) = G(x*A(x)^2) where G(x) = A(x/G(x)^2) is the g.f. of A104545 (Motzkin paths of length n having no consecutive (1,0) steps).
(3) A(x) = exp( Sum_{n>=1} x^n * A(x)^n/n * [Sum_{k=0..n} C(n,k)^2 * x^k * A(x)^(4*k)] ).
(4) A(x) = exp( Sum_{n>=1} x^n * A(x)^n/n * [(1-x/A(x)^4)^(2*n+1) * Sum_{k>=0} C(n+k,k)^2*x^k * A(x)^(4*k)] ).
a(n) = Sum_{k=0..floor(n/2)}((binomial(2*n+2*k+1,k)*binomial(2*n+2*k+1,n-2*k))/(2*n+2*k+1)). - Vladimir Kruchinin, Mar 11 2016

A200719 G.f. satisfies A(x) = (1 + xA(x)^2) (1 + x^2*A(x)^5).

Original entry on oeis.org

1, 1, 3, 13, 64, 340, 1903, 11053, 65993, 402527, 2497439, 15712220, 100001459, 642719263, 4165537744, 27193644061, 178654643151, 1180282875483, 7836312619243, 52259258911091, 349902441457427, 2351240866736891, 15851508780927739, 107187240225220684, 726784821098903319

Offset: 0

Paul D. Hanna, Nov 21 2011

nonn

More generally, for fixed parameters p and q, if F(x) satisfies:
F(x) = exp( Sum_{n>=1} x^n * F(x)^(n*p)/n * [Sum_{k=0..n} C(n,k)^2 * x^k * F(x)^(k*q)] ),
then F(x) = (1 + x*F(x)^(p+1))*(1 + x^2*F(x)^(p+q+1)).

			G.f.: A(x) = 1 + x + 3*x^2 + 13*x^3 + 64*x^4 + 340*x^5 + 1903*x^6 +...
Related expansions:
A(x)^2 = 1 + 2*x + 7*x^2 + 32*x^3 + 163*x^4 + 886*x^5 + 5039*x^6 +...
A(x)^5 = 1 + 5*x + 25*x^2 + 135*x^3 + 765*x^4 + 4481*x^5 + 26920*x^6 +...
A(x)^7 = 1 + 7*x + 42*x^2 + 252*x^3 + 1533*x^4 + 9457*x^5 + 59101*x^6 +...
where A(x) = 1 + x*A(x)^2 + x^2*A(x)^5 + x^3*A(x)^7.
The logarithm of the g.f. A = A(x) equals the series:
log(A(x)) = (1 + x*A^3)*x*A + (1 + 2^2*x*A^3 + x^2*A^6)*x^2*A^2/2 +
(1 + 3^2*x*A^3 + 3^2*x^2*A^6 + x^3*A^9)*x^3*A^3/3 +
(1 + 4^2*x*A^3 + 6^2*x^2*A^6 + 4^2*x^3*A^9 + x^4*A^12)*x^4*A^4/4 +
(1 + 5^2*x*A^3 + 10^2*x^2*A^6 + 10^2*x^3*A^9 + 5^2*x^4*A^12 + x^5*A^15)*x^5*A^5/5 + ...

Seiichi Manyama, Table of n, a(n) for n = 0..1000 (terms 0..300 from Vaclav Kotesovec)

Cf. A200716, A200717, A200718, A200074, A200075, A199876, A199874, A199877, A198951, A198953, A198957, A192415, A198888, A036765, A104545.

Cf. A186241, A199874, A200074, A200075, A200718, A215576.

{a(n)=local(p=1,q=3,A=1+x);for(i=1,n,A=(1+x*A^(p+1))*(1+x^2*A^(p+q+1))+x*O(x^n));polcoeff(A,n)}

{a(n)=local(p=1,q=3,A=1+x);for(i=1,n,A=exp(sum(m=1,n,x^m*(A+x*O(x^n))^(p*m)/m*sum(j=0,m,binomial(m, j)^2*x^j*(A+x*O(x^n))^(q*j))))); polcoeff(A, n, x)}

{a(n)=local(p=1,q=3,A=1+x);for(i=1,n,A=exp(sum(m=1,n,x^m*(A+x*O(x^n))^(p*m)/m*(1-x*A^q)^(2*m+1)*sum(j=0, n, binomial(m+j, j)^2*x^j*(A+x*O(x^n))^(q*j))))); polcoeff(A, n, x)}

G.f. A(x) satisfies:
(1) A(x) = exp( Sum_{n>=1} x^n * A(x)^n/n * [Sum_{k=0..n} C(n,k)^2 * x^k * A(x)^(3*k)] ).
(2) A(x) = exp( Sum_{n>=1} x^n * A(x)^n/n * [(1-x/A(x)^3)^(2*n+1) * Sum_{k>=0} C(n+k,k)^2*x^k * A(x)^(3*k)] ).
Recurrence: 4232*(n-2)*(n-1)*n*(2*n - 3)*(2*n - 1)*(2*n + 1)*(108983978975*n^7 - 1828734495225*n^6 + 13017379495661*n^5 - 50928975062019*n^4 + 118201965098732*n^3 - 162617590602876*n^2 + 122676758610192*n - 39103265134080)*a(n) = 8*(n-2)*(n-1)*(2*n - 3)*(2*n - 1)*(850837923857825*n^9 - 15127768128079400*n^8 + 116088908648008427*n^7 - 502364025369222635*n^6 + 1342887860190877280*n^5 - 2280899268898038065*n^4 + 2433907848768834828*n^3 - 1548429898790214180*n^2 + 521138603722292640*n - 68863424146977600)*a(n-1) - 30*(n-2)*(2*n - 3)*(155302170039375*n^11 - 3227155335853125*n^10 + 29807524885054600*n^9 - 161278340404759950*n^8 + 566950865855228019*n^7 - 1356848300481904461*n^6 + 2250482361655315470*n^5 - 2579665279074165840*n^4 + 1996011605601581864*n^3 - 988803599084885136*n^2 + 280851990522009984*n - 34444332223983360)*a(n-2) + 5*(7288303593953125*n^13 - 187891351713750000*n^12 + 2204843674914291875*n^11 - 15579013461781304250*n^10 + 73867718896175411475*n^9 - 247858726321141236540*n^8 + 604530296941440837821*n^7 - 1082990060568950070282*n^6 + 1421457900098213642392*n^5 - 1345695224728829837040*n^4 + 889319601933492222864*n^3 - 386196670582228097568*n^2 + 97916706472751405568*n - 10797892365692920320)*a(n-3) + 10*(n-3)*(2*n - 7)*(5*n - 18)*(5*n - 14)*(5*n - 12)*(5*n - 11)*(108983978975*n^7 - 1065846642400*n^6 + 4333636082786*n^5 - 9458655747964*n^4 + 11899609166891*n^3 - 8554104592084*n^2 + 3208950812340*n - 473478110640)*a(n-4). - Vaclav Kotesovec, Nov 17 2017
a(n) ~ s * sqrt((r*s*(r*s^3 - 1) - 3) / (7*Pi*(5*r*s*(1 + r*s^3) - 3))) / (2*n^(3/2)*r^n), where r = 0.1385102270697349252376651829944449360743895474888... and s = 1.450646440303399446510765649245639306003224666768... are real roots of the system of equations (1 + r*s^2)*(1 + r^2*s^5) = s, r*s*(2 + 5*r*s^3 + 7*r^2*s^5) = 1. - Vaclav Kotesovec, Nov 22 2017
a(n) = Sum_{k=0..floor(n/2)} binomial(2*n+k+1,k) * binomial(2*n+k+1,n-2*k) / (2*n+k+1). - Seiichi Manyama, Jul 18 2023

A200074 G.f. satisfies A(x) = (1 + xA(x)^2)(1 + x^2*A(x)).

Original entry on oeis.org

1, 1, 3, 9, 30, 108, 406, 1577, 6280, 25499, 105169, 439388, 1855636, 7908909, 33975250, 146954693, 639460707, 2797384235, 12295494109, 54272825103, 240480529815, 1069257987503, 4769306203838, 21334400243252, 95687482105807, 430217846136134, 1938651904470374, 8754225470415889

Offset: 0

Paul D. Hanna, Nov 13 2011

nonn

More generally, for fixed parameters p, q, r, and s, if F(x) satisfies:
F(x) = exp( Sum_{n>=1} x^(n*r)*F(x)^(n*p)/n * [Sum_{k=0..n} C(n,k)^2 * x^(k*s)*F(x)^(k*q)] ),
then F(x) = (1 + x^r*F(x)^(p+1))*(1 + x^(r+s)*F(x)^(p+q+1)).

			G.f.: A(x) = 1 + x + 3*x^2 + 9*x^3 + 30*x^4 + 108*x^5 + 406*x^6 + 1577*x^7 +...
Related expansions:
A(x)^2 = 1 + 2*x + 7*x^2 + 24*x^3 + 87*x^4 + 330*x^5 + 1289*x^6 +...
A(x)^3 = 1 + 3*x + 12*x^2 + 46*x^3 + 180*x^4 + 720*x^5 + 2928*x^6 +...
where A(x) = 1 + x*A(x)^2 + x^2*A(x) + x^3*A(x)^3.
The logarithm of the g.f. A = A(x) equals the series:
log(A(x)) = (A + x)*x + (A^2 + 2^2*x*A + x^2)*x^2/2 +
(A^3 + 3^2*x*A^2 + 3^2*x^2*A + x^3)*x^3/3 +
(A^4 + 4^2*x*A^3 + 6^2*x^2*A^2 + 4^2*x^3*A + x^4)*x^4/4 +
(A^5 + 5^2*x*A^4 + 10^2*x^2*A^3 + 10^2*x^3*A^2 + 5^2*x^4*A + x^5)*x^5/5 +
(A^6 + 6^2*x*A^5 + 15^2*x^2*A^4 + 20^2*x^3*A^3 + 15^2*x^4*A^2 + 6^2*x^5*A + x^6)*x^6/6 +...
more explicitly,
log(A(x)) = x + 5*x^2/2 + 19*x^3/3 + 77*x^4/4 + 331*x^5/5 + 1445*x^6/6 + 6392*x^7/7 + 28565*x^8/8 +...

Alois P. Heinz, Table of n, a(n) for n = 0..450

Cf. A199876, A199877, A198951, A198953, A198957, A192415, A198888, A004148, A036765.

Cf. A186241, A199874, A200075, A200718, A200719, A215576.

a:= n-> coeff(series(RootOf(A=(1+x*A^2)*(1+x^2*A), A), x, n+1), x, n):
seq(a(n), n=0..30);  # Alois P. Heinz, May 16 2012

m = 28; A[_] = 0;
Do[A[x_] = (1 + x A[x]^2)(1 + x^2 A[x]) + O[x]^m, {m}];
CoefficientList[A[x], x] (* Jean-François Alcover, Oct 02 2019 *)

{a(n)=local(A=1+x);for(i=1,n,A=(1+x*A^2)*(1+x^2*A^1)+x*O(x^n));polcoeff(A,n)}

{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^j/A^j)*(x*A+x*O(x^n))^m/m))); polcoeff(A, n, x)}

{a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, (1-x/A)^(2*m+1)*sum(j=0, n, binomial(m+j, j)^2*x^j/A^j)*x^m*A^m/m))); polcoeff(A, n, x)}

G.f. satisfies:
(1) A(x) = exp( Sum_{n>=1} (Sum_{k=0..n} C(n,k)^2 * x^k*A(x)^(n-k)) * x^n/n ).
(2) A(x) = exp( Sum_{n>=1} (1-x/A(x))^(2*n+1)*(Sum_{k>=0} C(n+k,k)^2*x^k/A(x)^k) * x^n*A(x)^n/n ).
(3) A(x) = x / Series_Reversion( x*G(x) ) where G(x) is the g.f. of A199876.
(4) A(x) = G(x/A(x)) where G(x) = A(x*G(x)) is the g.f. of A199876.
Recurrence: (n+1)*(n+2)*(1241*n^4 - 10636*n^3 + 25417*n^2 - 7382*n - 17136)*a(n) =  - 18*(n+1)*(443*n^3 - 3889*n^2 + 9734*n - 5712)*a(n-1) + 4*(6205*n^6 - 53180*n^5 + 115741*n^4 + 64762*n^3 - 370103*n^2 + 246727*n - 25704)*a(n-2) + 6*(2482*n^6 - 24995*n^5 + 76519*n^4 - 36347*n^3 - 185471*n^2 + 293092*n - 140400)*a(n-3) + 2*(4964*n^6 - 57436*n^5 + 228617*n^4 - 276802*n^3 - 361447*n^2 + 956696*n - 320496)*a(n-4) - 6*(2482*n^6 - 32441*n^5 + 140587*n^4 - 173153*n^3 - 266705*n^2 + 677518*n - 291840)*a(n-5) + 12*(n-4)*(2*n - 11)*(11*n^2 + 73*n - 748)*a(n-6) + 2*(n-5)*(2*n - 13)*(1241*n^4 - 5672*n^3 + 955*n^2 + 16508*n - 8496)*a(n-7). - Vaclav Kotesovec, Aug 18 2013
a(n) ~ c*d^n/n^(3/2), where d = 4.770539985405... is the root of the equation -4 + 12*d^2 - 8*d^3 - 12*d^4 - 20*d^5 + d^7 = 0 and c = 0.612892860188927397373456... - Vaclav Kotesovec, Aug 18 2013
a(n) = Sum_{k=0..floor(n/2)} binomial(2*n-3*k+1,k) * binomial(2*n-3*k+1,n-2*k) / (2*n-3*k+1). - Seiichi Manyama, Jul 18 2023

A200075 G.f. satisfies A(x) = (1 + xA(x)^2)(1 + x^2*A(x)^3).

Original entry on oeis.org

1, 1, 3, 11, 45, 198, 914, 4367, 21414, 107155, 544987, 2808978, 14640073, 77025373, 408544815, 2182206259, 11727989593, 63373962690, 344109933186, 1876562458845, 10273572074493, 56443282489240, 311097732946200, 1719707775782826, 9531914043637385, 52963938340248863, 294966593345731623

Offset: 0

Paul D. Hanna, Nov 13 2011

nonn

More generally, for fixed parameters p, q, r, and s, if F(x) satisfies:
F(x) = exp( Sum_{n>=1} x^(n*r)*F(x)^(n*p)/n * [Sum_{k=0..n} C(n,k)^2 * x^(k*s)*F(x)^(k*q)] ),
then F(x) = (1 + x^r*F(x)^(p+1))*(1 + x^(r+s)*F(x)^(p+q+1)).

			G.f.: A(x) = 1 + x + 3*x^2 + 11*x^3 + 45*x^4 + 198*x^5 + 914*x^6 +...
Related expansions:
A(x)^2 = 1 + 2*x + 7*x^2 + 28*x^3 + 121*x^4 + 552*x^5 + 2615*x^6 +...
A(x)^3 = 1 + 3*x + 12*x^2 + 52*x^3 + 237*x^4 + 1122*x^5 + 5463*x^6 +...
A(x)^5 = 1 + 5*x + 25*x^2 + 125*x^3 + 630*x^4 + 3211*x^5 + 16545*x^6 +...
where A(x) = 1 + x*A(x)^2 + x^2*A(x)^3 + x^3*A(x)^5.
The logarithm of the g.f. A = A(x) equals the series:
log(A(x)) = (1 + x*A)*x*A + (1 + 2^2*x*A + x^2*A^2)*x^2*A^2/2 +
(1 + 3^2*x*A + 3^2*x^2*A^2 + x^3*A^3)*x^3*A^3/3 +
(1 + 4^2*x*A + 6^2*x^2*A^2 + 4^2*x^3*A^3 + x^4*A^4)*x^4*A^4/4 +
(1 + 5^2*x*A + 10^2*x^2*A^2 + 10^2*x^3*A^3 + 5^2*x^4*A^4 + x^5*A^5)*x^5*A^5/5 +
(1 + 6^2*x*A + 15^2*x^2*A^2 + 20^2*x^3*A^3 + 15^2*x^4*A^4 + 6^2*x^5*A^5 + x^6*A^6)*x^6*A^6/6 +...
more explicitly,
log(A(x)) = x + 5*x^2/2 + 25*x^3/3 + 129*x^4/4 + 686*x^5/5 + 3713*x^6/6 + 20350*x^7/7 +...
Given G(x) where 1+x*G(x) is the g.f. of A004148, then the coefficients in the powers of G(x) begin:
1: [(1), 1, 2, 4, 8, 17, 37, 82, 185, 423, 978, ...];
2: [1,(2), 5, 12, 28, 66, 156, 370, 882, 2112, ...];
3: [1, 3,(9), 25, 66, 171, 437, 1107, 2790, 7009, ...];
4: [1, 4, 14,(44), 129, 364, 1000, 2696, 7172, 18892, ...];
5: [1, 5, 20, 70,(225), 686, 2015, 5760, 16135, 44500, ...];
6: [1, 6, 27, 104, 363,(1188), 3713, 11214, 32994, 95106, ...];
7: [1, 7, 35, 147, 553, 1932,(6398), 20350, 62734, 188650, ...];
8: [1, 8, 44, 200, 806, 2992, 10460,(34936), 112585, 352560, ...];
9: [1, 9, 54, 264, 1134, 4455, 16389, 57330,(192726), 627406, ...]; ...;
the coefficients in parenthesis form the initial terms of this sequence:
[1/1, 2/2, 9/3, 44/4, 225/5, 1188/6, 6398/7, 34936/8, 192726/9, ...].
The coefficients in the logarithm of the g.f. is also a diagonal in the above table.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A004148, A199876, A199877, A198951, A198953, A198957, A192415, A198888, A036765.

Cf. A186241, A199874, A200074, A200718, A200719, A215576.

CoefficientList[1/x*InverseSeries[Series[x*(1-x-x^2 + Sqrt[(1+x+x^2)*(1-3*x+x^2)])/2,{x,0,20}],x],x] (* Vaclav Kotesovec, Sep 19 2013 *)

{a(n)=local(A=1+x);for(i=1,n,A=(1+x*A^2)*(1+x^2*A^3)+x*O(x^n));polcoeff(A,n)}

{a(n)=polcoeff(1/x*serreverse(x*(1-x-x^2 + sqrt((1+x+x^2)*(1-3*x+x^2)+x*O(x^n)))/2),n)}

{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^j*A^j)*(x*A+x*O(x^n))^m/m))); polcoeff(A, n, x)}

{a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, (1-x*A)^(2*m+1)*sum(j=0, n, binomial(m+j, j)^2*x^j*A^j)*x^m*A^m/m))); polcoeff(A, n, x)}

G.f.: (1/x)*Series_Reversion( x*(1-x-x^2 + sqrt((1+x+x^2)*(1-3*x+x^2)))/2 ).
a(n) = [x^n] G(x)^(n+1)/(n+1), where 1+x*G(x) is the g.f. of A004148.
G.f. A(x) satisfies:
(1) A(x) = (1/x)*Series_Reversion( x/G(x) ) where 1+x*G(x) is the g.f. of A004148.
(2) A(x) = G(x*A(x)) where G(x) = A(x/G(x)) and 1+x*G(x) is the g.f. of A004148.
(3) A(x) = exp( Sum_{n>=1} (Sum_{k=0..n} C(n,k)^2 * x^k*A(x)^k) * x^n*A(x)^n/n ).
(4) A(x) = exp( Sum_{n>=1} (1-x*A(x))^(2*n+1)*(Sum_{k>=0} C(n+k,k)^2*x^k*A(x)^k) * x^n*A(x)^n/n ).
Recurrence: 8*n*(2*n+1)*(4*n+1)*(4*n+3)*(1557671*n^7 - 18939961*n^6 + 94817789*n^5 - 252067387*n^4 + 381880748*n^3 - 327052012*n^2 + 145198992*n - 25583040)*a(n) = (2026529971*n^11 - 24640889261*n^10 + 122927623620*n^9 - 322351865586*n^8 + 467303512311*n^7 - 343677276405*n^6 + 61590777290*n^5 + 76066203476*n^4 - 45605627832*n^3 + 4625651136*n^2 + 1916801280*n - 338688000)*a(n-1) + 2*(800642894*n^11 - 10936104295*n^10 + 62803409541*n^9 - 196202081616*n^8 + 357730085364*n^7 - 370711524567*n^6 + 174415015309*n^5 + 25877389846*n^4 - 63266190708*n^3 + 19055552472*n^2 + 1313789760*n - 861840000)*a(n-2) + 6*(308418858*n^11 - 4675368852*n^10 + 30103912361*n^9 - 106665982366*n^8 + 223860428776*n^7 - 274000455628*n^6 + 166116940489*n^5 - 2432493994*n^4 - 54297743044*n^3 + 22033617000*n^2 + 936446400*n - 1315440000)*a(n-3) + 6*(n-2)*(2*n-7)*(3*n-10)*(3*n-8)*(1557671*n^7 - 8036264*n^6 + 13889114*n^5 - 7559372*n^4 - 2491645*n^3 + 2975476*n^2 - 179460*n - 187200)*a(n-4). - Vaclav Kotesovec, Sep 19 2013
a(n) ~ c*d^n/(sqrt(Pi)*n^(3/2)), where d = 1301/1024 + 1/(1024*sqrt(3/(7183147 - (2002819072*2^(2/3))/(3725055779 + 42057117*sqrt(16305))^(1/3) + 1024*(7450111558 + 84114234*sqrt(16305))^(1/3)))) + (1/2)*sqrt(7183147/393216 - (3725055779 + 42057117*sqrt(16305))^(1/3)/(384*2^(2/3)) + 977939/(192*(7450111558 + 84114234*sqrt(16305))^(1/3)) + (1/131072)*(4194454317*sqrt(3/(7183147 - (2002819072*2^(2/3))/(3725055779 + 42057117*sqrt(16305))^(1/3) + 1024*(7450111558 + 84114234*sqrt(16305))^(1/3))))) = 5.89828930084513611... is the root of the equation -108 - 1188*d - 1028*d^2 - 1301*d^3 + 256*d^4 = 0 and c = 0.656947859044624009263362998790812821830934... - Vaclav Kotesovec, Sep 19 2013
a(n) = Sum_{k=0..floor(n/2)} binomial(2*n-k+1,k) * binomial(2*n-k+1,n-2*k) / (2*n-k+1). - Seiichi Manyama, Jul 18 2023

A210736 Expansion of (1 + sqrt( (1 + 2x) / (1 - 2x))) / 2 in powers of x.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300, 40116600, 77558760, 155117520, 300540195, 601080390, 1166803110, 2333606220, 4537567650

Offset: 0

Michael Somos, May 10 2012

nonn

Hankel transform is period 4 sequence [ 1, 0, -1, 0, ...] A056594 and the Hankel transform of sequence omitting a(0) is the all 1s sequence A000012. This is the unique sequence with that property.
Series reversion of x*A(x) apparently yields x*A036765(-x). - R. J. Mathar, Sep 24 2012
a(n) is the number of length n words on {-1,1} such that the sum of any of its prefixes is always positive.  Cf. A001405 where the sum of all prefixes is nonnegative. - Geoffrey Critzer, Jul 08 2013

			G.f. = 1 + x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 10*x^6 + 20*x^7 + 35*x^8 + 70*x^9 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).
Paul Barry, d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths, arXiv:2505.16718 [math.CO], 2025. See p. 25.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; page 77.

Essentially the same as A001405.
Cf. A056594, A138350, A210628, A211278.
Cf. A000108, A091867, A146559, A126930.

nn=36; d=(1-(1-4x^2)^(1/2))/(2x^2);CoefficientList[Series[1/(1-x d),{x,0,nn}],x] (* Geoffrey Critzer, Jul 08 2013 *)
CoefficientList[Series[2 x / (-1 + 2 x + Sqrt[1 - 4 x^2]), {x, 0, 40}], x] (* Vincenzo Librandi, Nov 10 2014 *)

{a(n) = if( n<1, n==0, binomial( n - 1, (n - 1)\2))};

{a(n) = polcoeff( (1 + sqrt( (1 + 2*x) / (1 - 2*x) + x * O(x^n))) / 2, n)};

G.f.: 2 * x / (-1 + 2*x + sqrt(1 - 4*x^2)).
G.f. A(x) satisfies A(x) = A(x)^2 - x / (1 - 2*x).
G.f. A(x) satisfies A( x / (1 + x^2) ) = 1 / (1 - x).
G.f. A(x) satisfies A(1/3) = (1 + sqrt(5))/2.
G.f. A(x) = 1 + x / (1 - 2*x + x / A(x)).
G.f. A(x) = 1 + x / (1 - x / (1 - x / (1 + x / A(x)))).
G.f. A(x) = 1 + x * A001405(x). a(n+1) = A001405(n).
Convolution inverse is A210628. Partial sums is A072100.
Binomial transform with offset 1 is A211278 with offset 1. a(n+2) * a(n) - a(n+1)^2 = A138350(n-1).
a(n) = (-1)^floor(n/2)*hypergeom2F1([1-n, -n],[1],-1). - Peter Luschny, Sep 01 2012
D-finite with recurrence: n*a(n) -2*a(n-1) +4*(2-n)*a(n-2)=0. - R. J. Mathar, Sep 14 2012
G.f. A(x) = 1 / (1 - x / (1 - x^2 / (1 - x^2 / (1 - x^2 / ...)))). - Michael Somos, Jan 02 2013
G.f.: 1/(1 - x*C(x)) where C(x) is the o.g.f. for A126120. - Geoffrey Critzer, Jul 08 2013
a(n) ~ 2^(n-1/2) / sqrt(Pi*n). - Vaclav Kotesovec, Feb 01 2014
G.f.: A(x) = 1 - x/(- 1 + x/A(-x)). - Arkadiusz Wesolowski, Feb 28 2014
From Tom Copeland, Nov 07 2014: (Start)
Setting a(0)=0 here, we have a signed version in A126930 and
O.g.f. G(x)=[-1+sqrt(1+4*x/(1-2x))]/2 = x + x^2 + 2 x^3 + ... = -C[-P(P(x,-1),-1)]= -C[-P(x,-2)] where C(x)= [1-sqrt(1-4*x)]/2= x + x^2 + 2 x^3 + ... = A000108(x) with inverse Cinv(x)=x*(1-x), and P(x,t)= x/(1 + t*x) with inverse P(x,-t).
These types of arrays are from linear fractional transformations of C(x). See A091867.
Ginv(x) = P[-Cinv(-x),2] = x*(1+x)/(1+2*x*(1-x))= (x+x^2)/(1+2(x+x^2)) (see A146559). (End)

A186241 G.f. satisfies A(x) = 1 + xA(x)^2 + x^2A(x)^4 + x^3*A(x)^6.

Original entry on oeis.org

1, 1, 3, 12, 54, 262, 1337, 7072, 38426, 213197, 1202795, 6879160, 39794416, 232429030, 1368806610, 8118934656, 48458809586, 290832756606, 1754059333738, 10625545472716, 64620970743082, 394409682103262, 2415084675723048, 14832185219521152, 91339478577683664

Offset: 0

Vladimir Kruchinin, Feb 15 2011

			G.f.: A(x) = 1 + x + 3*x^2 + 12*x^3 + 54*x^4 + 262*x^5 + 1337*x^6 +...
where A(x) = (1 + x*A(x)^2)*(1 + x^2*A(x)^4).
Related expansions:
A(x)^2 = 1 + 2*x + 7*x^2 + 30*x^3 + 141*x^4 + 704*x^5 + 3666*x^6 +...
A(x)^4 = 1 + 4*x + 18*x^2 + 88*x^3 + 451*x^4 + 2392*x^5 + 13022*x^6 +...
A(x)^6 = 1 + 6*x + 33*x^2 + 182*x^3 + 1014*x^4 + 5718*x^5 + 32623*x^6 +...
where A(x) = 1 + x*A(x)^2 + x^2*A(x)^4 + x^3*A(x)^6.
From _Paul D. Hanna_, Nov 11 2011: (Start)
The logarithm of the g.f. A = A(x) equals the series:
log(A(x)) = (1 + x*A^2)*x*A + (1 + 2^2*x*A^2 + x^2*A^4)*x^2*A^2/2 +
(1 + 3^2*x*A^2 + 3^2*x^2*A^4 + x^3*A^6)*x^3*A^3/3 +
(1 + 4^2*x*A^2 + 6^2*x^2*A^4 + 4^2*x^3*A^6 + x^4*A^8)*x^4*A^4/4 +
(1 + 5^2*x*A^2 + 10^2*x^2*A^4 + 10^2*x^3*A^6 + 5^2*x^4*A^8 + x^5*A^10)*x^5*A^5/5 + ...
which involves squares of binomial coefficients. (End)

Robert Israel, Table of n, a(n) for n = 0..1108
Nathan Gabriel, Katherine Peske, Lara Pudwell, and Samuel Tay, Pattern avoidance in ternary trees J. Integer Seq. 15 (2012), no. 1, Article 12.1.5, 20 pp.
Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.

Cf. A199876, A199877, A198951, A198953, A198957, A192415, A198888, A036765.
Cf. A200731.
Cf. A199874, A200074, A200075, A200718, A200719, A215576.

F:= proc(n) if n::even then
  simplify((1/2)*hypergeom([-(1/2)*n, -2*n-1, -(1/2)*n+1/2], [(1/2)*n+1, 3/2+(1/2)*n], -1)*(2*n+2)!/((2*n+1)*((n+1)!)^2))
  else
  simplify((1/2)*hypergeom([-(1/2)*n, -2*n-1, -(1/2)*n+1/2], [(1/2)*n+1, 3/2+(1/2)*n], -1)*(2*n+2)!/((2*n+1)*((n+1)!)^2))
  fi
end proc:
map(F, [$0..30]); # Robert Israel, Jun 22 2015

a[n_] := 1/(2n + 1) Sum[Binomial[2n + 1, k] Binomial[2n + 1, n - 2k], {k, 0, n/2}];
(* or: *)
a[n_] := (Binomial[2n + 1, n] HypergeometricPFQ[{-2n - 1, 1/2 - n/2, -n/2}, {n/2 + 1, n/2 + 3/2}, -1])/(2n + 1);
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Nov 17 2017 *)

{a(n)=local(A=1+x);for(i=1,n,A=(1+x*A^2)*(1+x^2*A^4)+x*O(x^n));polcoeff(A,n)} /* Paul D. Hanna */

{a(n)=polcoeff(sqrt((1/x)*serreverse(x/(1 + x + x^2 + x^3 +x*O(x^n))^2)), n)} /* Paul D. Hanna */

{a(n)=polcoeff( (1 + x + x^2 + x^3+x*O(x^n))^(2*n+1)/(2*n+1), n)} /* Paul D. Hanna */

{a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n, (x*A+x*O(x^n))^m/m*sum(j=0, m, binomial(m, j)^2*x^j*A^(2*j))))); polcoeff(A, n, x)} /* Paul D. Hanna */

{a(n)=local(A=1+x); for(i=1, n, A=exp(sum(m=1, n,x^m*A^m/m*(1-x*A^2)^(2*m+1)*sum(j=0, n, binomial(m+j, j)^2*x^j*A^(2*j))))); polcoeff(A, n, x)} /* Paul D. Hanna */

a(n) = (1/(2*n-1))*Sum_{j=0..2*n-1} binomial(2*n-1,j)*Sum_{i=j..n+j-1} binomial(j,i-j)*binomial(2*n-j-1,3*j-3*n-i+1), n>0.
From Paul D. Hanna, Nov 11 2011: (Start)
G.f. A(x) satisfies:
(1) A(x) = sqrt( (1/x)*Series_Reversion( x/(1 + x + x^2 + x^3)^2 ) ).
(2) A( x/(1 + x + x^2 + x^3)^2 ) = 1 + x + x^2 + x^3.
(3) A(x) = G(x*A(x)) where G(x) = A(x/G(x)) = g.f. of A036765 (number of rooted trees with a degree constraint).
(4) a(n) = [x^n] (1 + x + x^2 + x^3)^(2*n+1) / (2*n+1).
(5) A(x) = exp( Sum_{n>=1} x^n*A(x)^n/n * [Sum_{k=0..n} C(n,k)^2 * x^k*A(x)^(2*k)] ).
(6) A(x) = exp( Sum_{n>=1} x^n*A(x)^n/n * [(1-x*A(x)^2)^(2*n+1)*Sum_{k>=0} C(n+k,k)^2*x^k*A(x)^(2*k)] ).
(End)
From Peter Bala, Jun 21 2015: (Start)
a(n) = 1/(2*n + 1)*Sum_{k = 0..floor(n/2)} binomial(2*n + 1,k)*binomial(2*n + 1,n - 2*k).
More generally, the coefficient of x^n in A(x)^r equals r/(2*n + r)*Sum_{k = 0..floor(n/2)} binomial(2*n + r,k)*binomial(2*n + r,n - 2*k) by the Lagrange-Bürmann formula.
O.g.f. A(x) = exp(Sum_{n >= 1} 1/2*b(n)*x^n/n), where b(n) = Sum_{k = 0..floor(n/2)} binomial(2*n,k)*binomial(2*n,n - 2*k). Cf. A036765, A198951, A200731. (End)
Recurrence: 5*n*(5*n - 1)*(5*n + 1)*(5*n + 2)*(5*n + 3)*(13144*n^4 - 57784*n^3 + 90149*n^2 - 59354*n + 13980)*a(n) = 8*(2*n - 1)*(16259128*n^8 - 71478808*n^7 + 108653137*n^6 - 60530902*n^5 - 2811173*n^4 + 12694433*n^3 - 2398482*n^2 - 352503*n + 78570)*a(n-1) + 128*(n-1)*(2*n - 3)*(2*n - 1)*(52576*n^6 - 178560*n^5 + 136156*n^4 + 22938*n^3 - 16067*n^2 - 3138*n - 405)*a(n-2) + 2048*(n-2)*(n-1)*(2*n - 5)*(2*n - 3)*(2*n - 1)*(13144*n^4 - 5208*n^3 - 4339*n^2 + 168*n + 135)*a(n-3). - Vaclav Kotesovec, Nov 17 2017
A(x^2) = (1/x) * series reversion of x/(1 + x^2 + x^4 + x^6). - Peter Bala, Jul 27 2023

A291534 Expansion of the series reversion of x/((1 + x)*(1 - x^2)).

Original entry on oeis.org

1, 1, 0, -3, -7, -4, 24, 85, 99, -215, -1196, -2100, 1420, 17512, 42160, 9477, -252073, -815965, -736456, 3365813, 15248793, 22861712, -37036000, -273657748, -575046252, 180950476, 4658415696, 13042693000, 6717278152, -73400374512, -275797704864, -321427878811, 1012425395135

Offset: 1

Ilya Gutkovskiy, Aug 25 2017

sign

Reversion of g.f. for the canonical enumeration of integers (A001057).

Seiichi Manyama, Table of n, a(n) for n = 1..1000
N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Series Reversion
Index entries for reversions of series

Cf. A001057, A001764, A036765.

Cf. A363982, A364051, A364764.

Rest[CoefficientList[InverseSeries[Series[x/((1 + x) (1 - x^2)), {x, 0, 33}], x], x]]
Table[HypergeometricPFQ[{(1 - n)/2, 1 - n/2, -n}, {1, 3/2}, 1], {n, 1, 33}] (* Vladimir Reshetnikov, Oct 15 2018 *)

a(n) = sum(k=0, n-1, (-1)^k*binomial(n, k)*binomial(2*n, n-1-k))/n; \\ Seiichi Manyama, Aug 05 2023

G.f. A(x) satisfies: A(x)/((1 + A(x))*(1 - A(x)^2)) = x.
a(n) = hypergeom([(1 - n)/2, 1 - n/2, -n], [1, 3/2], 1). - Vladimir Reshetnikov, Oct 15 2018
From Vladimir Reshetnikov, Oct 18 2018: (Start)
G.f.: 2^(1/3)*(6 - 8*x - 2^(1/3)*t^2)/(6*sqrt(x)*t), where t = (3*sqrt(12 - 39*x + 96*x^2) - (9 + 16*x)*sqrt(x))^(1/3).
D-finite with recurrence: 64*n*(n + 1)*(2*n + 1)*a(n) - 4*(n + 1)*(37*n^2 + 134*n + 120)*a(n + 1)  + (n + 2)*(55*n^2 + 235*n + 240)*a(n + 2) - 2*(6*n + 21)*(n + 2)*(n + 3)*a(n + 3) = 0. (End)
a(n) = (1/n) * Sum_{k=0..n-1} (-1)^k * binomial(n,k) * binomial(2*n,n-1-k). - Seiichi Manyama, Aug 05 2023
From Seiichi Manyama, Aug 11 2023: (Start)
a(n) = Sum_{k=0..n} (-1)^k * 2^(n-k) * binomial(n,k) * binomial(2*n+k+1,n) / (2*n+k+1).
a(n) = (1/n) * Sum_{k=0..n-1} (-2)^k * binomial(n,k) * binomial(3*n-k,n-1-k). (End)

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

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 125, 393, 1265, 4147, 13798, 46476, 158170, 543050, 1878670, 6542330, 22915999, 80682987, 285378270, 1013564805, 3613262795, 12924536005, 46373266470, 166856922125, 601928551824, 2176616383346, 7888184659826, 28645799759632, 104224861693855

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of Dyck n-paths that avoid UUUUU=(U^5). For example, a(5)=41 counts all 42 Dyck 5-paths except (U^5)(D^5). - David Callan, Sep 25 2006
Number of n-leaf binary trees that do not contain (()(()(()(()(()()))))) as a subtree. - Eric Rowland, Jun 17 2009
a(n) is the number of ordered unlabeled rooted trees on n+1 nodes where each node has no more than 4 children. - Geoffrey Critzer, Jan 05 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
CombOS - Combinatorial Object Server, Generate binary trees
Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908 [math.CO], 2012-2014.
Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015.
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From N. J. A. Sloane, Jan 03 2013
Lajos Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).
Index entries for sequences related to rooted trees

The sequence of sequences A000007 (0^n), A000012 (1's), A001006 (Motzkin), A036765, A036766, ... tends to A000108 (Catalan).

Column k=4 of A288942.

r := 4; [ 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) ];

nn=20;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[Series[0==f[x]-x -x f[x]-x f[x]^2-x f[x]^3-x f[x]^4,{x,0,nn}],x];Table[a[n],{n,0,nn}]/.sol  (* Geoffrey Critzer, Jan 05 2013 *)
Table[1/(n+1)*Sum[(-1)^j*Binomial[n+1,j]*Binomial[2*n-5*j,n],{j,0,Floor[n/5]}],{n,0,20}] (* Vaclav Kotesovec, Mar 13 2014 *)
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, 4];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

a(n)=if(n<0,0,polcoeff(serreverse(x/polcyclo(5)+O(x^(n+2))),n+1)) /* Ralf Stephan */

G.f.: A(x) satisfies A(x) = 1+x*A(x)+x^2*A(x)^2+x^3*A(x)^3+x^4*A(x)^4. - Vladimir Kruchinin, Feb 22 2011
a(n) ~ sqrt(s/(1 + 3*r*s + 6*r^2*s^2)) / (2*n^(3/2)*sqrt(Pi)*r^(n+1)), where r = 0.2607944621478111633... and s = 2.176953284456253116... are roots of the system of equations r + 2*r^2*s + 3*r^3*s^2 + 4*r^4*s^3 = 1, 1 + r*s + r^2*s^2 + r^3*s^3 + r^4*s^4 = s. - Vaclav Kotesovec, Mar 13 2014
Conjecture: -3*(3*n+2)*(133*n-347)*(3*n+4)*(n+1)*a(n) +(111457*n^4-364730*n^3+228995*n^2+19310*n-33312)*a(n-1) +5*(-68503*n^4+34661
8*n^3-590627*n^2+397748*n-90564)*a(n-2) -25*(n-2)*(1933*n^3-9435*n^2+14354*n-7518)*a(n-3) -125*(n-2)*(n-3)*(1333*n^2-4384*n+2718)*
a(n-4) -625*(733*n-400)*(n-2)*(n-3)*(n-4)*a(n-5)=0. - R. J. Mathar, Aug 04 2015

Name clarified by Andrew Howroyd, Dec 04 2017

A159772 Number of n-leaf binary trees that do not contain (()((((()())())())())) as a subtree.

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 124, 384, 1210, 3865, 12482, 40677, 133572, 441468, 1467296, 4900760, 16439370, 55357305, 187050302, 633998079, 2154950454, 7343407521, 25082709012, 85858848820, 294480653064, 1011871145116, 3482837144984, 12006861566684, 41454180382688

Offset: 1

Eric Rowland, Apr 23 2009

nonn

By 'binary tree' we mean a rooted, ordered tree in which each vertex has either 0 or 2 children.
a(n) is also the number of Dyck words of semilength n-1 with no DUUUU.
Also, number of ordered rooted trees with n nodes and all non-root nodes having outdegrees < 4. - Andrew Howroyd, Dec 04 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
CombOS - Combinatorial Object Server, Generate binary trees
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
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.
Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2008-2010.

Column k=4 of A295679.

Cf. A036765, A064580.

terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];
col[4] (* Jean-François Alcover, Dec 05 2017, after Andrew Howroyd *)

a(n):=if n=1 then 1 else sum(k*sum(binomial(n-1,j)*sum(binomial(j,i-j)*binomial(n-j-1,3*j-n-k-i+1),i,j,n-k+j-1),j,0,n-1),k,1,n-1)/(n-1); /* Vladimir Kruchinin, Oct 23 2011 */

Vec(1/(1-serreverse(x*(1-x)/(1-x^4) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017

G.f. f(x) satisfies (1 - 4 x) f(x)^3 + (6 x - 1) x f(x)^2 - 4 x^3 f(x) + x^4 = 0.
a(n) = sum(k=1..n-1, k*sum(j=0..n-1, binomial(n-1,j)*sum(i=j..n-k+j-1, binomial(j,i-j)*binomial(n-j-1,3*j-n-k-i+1))))/(n-1), n>1. a(0)=0, a(1)=1. - Vladimir Kruchinin, Oct 23 2011
Conjecture: 2*(n-1)*(2*n-3)*a(n) +(-43*n^2+172*n-177)*a(n-1) +4*(44*n^2-266*n+411)*a(n-2) +8*(-43*n^2+358*n-741)*a(n-3) +96*(3*n^2-29*n+69)*a(n-4) -128*(n-4)*(n-6)*a(n-5) +512*(n-6)*(n-7)*a(n-6)=0. - R. J. Mathar, May 30 2014
G.f.: x/(1-x*G(x)) where G(x) is g.f. of A036765. - Andrew Howroyd, Dec 04 2017
From Vaclav Kotesovec, Dec 05 2017: (Start)
Recurrence (of order 4): 2*(n-1)*(2*n - 3)*(13*n^2 - 75*n + 104)*a(n) = 3*(117*n^4 - 1039*n^3 + 3315*n^2 - 4513*n + 2216)*a(n-1) - 12*(39*n^4 - 368*n^3 + 1268*n^2 - 1893*n + 1032)*a(n-2) - 16*(n-4)*(13*n^3 - 75*n^2 + 122*n - 54)*a(n-3) - 64*(n-5)*(n-4)*(13*n^2 - 49*n + 42)*a(n-4).
a(n) ~ sqrt(r*s*(r - s + 2*s^2) / (2*Pi*(r - 6*r^2 - 3*s + 12*r*s))) / (n^(3/2) * r^n), where r = 0.2769531794372340984240353119411920830379502290822... and s = 0.8081460429543529393193017440354060980373344931954... are real roots of the system of equations r^4 + r*(-1 + 6*r)*s^2 + (1 - 4*r)*s^3 = 4*r^3*s, s*(12*r^2 + 3*s - 2*r*(1 + 6*s)) = 4*r^3. (End)
a(n+1) = Sum_{k=0..n} A064580(n,k). - Georg Fischer, Jul 20 2023

cp's OEIS Frontend

A288942 Number A(n,k) of ordered rooted trees with n non-root nodes and all outdegrees <= k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A200718 G.f. satisfies A(x) = (1 + x*A(x)^2) * (1 + x^2*A(x)^6).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

PARI

PARI

PARI

Formula

A200719 G.f. satisfies A(x) = (1 + x*A(x)^2) * (1 + x^2*A(x)^5).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

PARI

Formula

A200074 G.f. satisfies A(x) = (1 + x*A(x)^2)*(1 + x^2*A(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A200075 G.f. satisfies A(x) = (1 + x*A(x)^2)*(1 + x^2*A(x)^3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Formula

A210736 Expansion of (1 + sqrt( (1 + 2*x) / (1 - 2*x))) / 2 in powers of x.

Views

Author

Keywords

Comments

Examples

Links

A200718 G.f. satisfies A(x) = (1 + xA(x)^2) (1 + x^2*A(x)^6).

A200719 G.f. satisfies A(x) = (1 + xA(x)^2) (1 + x^2*A(x)^5).

A200074 G.f. satisfies A(x) = (1 + xA(x)^2)(1 + x^2*A(x)).

A200075 G.f. satisfies A(x) = (1 + xA(x)^2)(1 + x^2*A(x)^3).

A210736 Expansion of (1 + sqrt( (1 + 2x) / (1 - 2x))) / 2 in powers of x.

A186241 G.f. satisfies A(x) = 1 + xA(x)^2 + x^2A(x)^4 + x^3*A(x)^6.