A161634 G.f. satisfies A(x) = 1/(1 - x*(1 + x*A(x))^2).

1, 1, 3, 8, 25, 81, 274, 953, 3389, 12265, 45025, 167256, 627540, 2374672, 9052447, 34731401, 134010573, 519683813, 2024370167, 7917605996, 31080085431, 122407860927, 483558273368, 1915535953655, 7607408410408, 30283240593756

Offset: 0

Author

Paul D. Hanna, Jun 18 2009

Keywords

• nonn

Comments

With offset 1, a(n) is the number of n-edge (unlabeled) ordered trees in which each nonroot nonleaf vertex has 2 or more children one of which is designated a favorite child. For example, a(3) = 3 counts the trees with edges {01,02,03}, {01,1(2),13}, {01,12,1(3)} with favorite children in parentheses, where the labels are merely for convenience. The generating function A(x) = 1 + x + x^2 + 3*x^3 + 8*x^4 + ... for these trees satisfies A(x) = 1 + x - x*A(x)^2 + x*A(x)^3. To see this, consider in addition the trees in which the root also has 2 or more children and a favorite child, and use the "symbolic method" of Flajolet and Sedgewick to get both generating functions. - David Callan, May 15 2022

Examples

			G.f.: A(x) = 1 + x + 3*x^2 + 8*x^3 + 25*x^4 + 81*x^5 + 274*x^6 +...
(1 + x*A(x))^2 = 1 + 2*x + 3*x^2 + 8*x^3 + 23*x^4 + 72*x^5 + 237*x^6 +...
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000

Programs

Mathematica

Table[Sum[Binomial[n+1,k]/(n+1)*Binomial[2*k,n-k],{k,0,n}],{n,0,20}] (* Vaclav Kotesovec, Sep 18 2013 *)

PARI

a(n,m=1)=sum(k=0,n,binomial(n+m,k)*m/(n+m)*binomial(2*k,n-k))

Formula

a(n) = Sum_{k=0..n} C(n+1,k)/(n+1) * C(2*k,n-k).

Let A(x)^m = Sum_{n>=0} a(n,m)*x^n then

a(n,m) = Sum_{k=0..n} C(n+m,k)*m/(n+m) * C(2*k,n-k).

...

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

G.f.: A(x) = (1/x)*Series_Reversion[x/(1 + x + 2*x^2 + x^3)].

Recurrence: 2*(n+1)*(2*n+3)*(19*n+2)*a(n) = 2*(2*n+1)*(38*n^2 + 23*n + 9)*a(n-1) + 2*(n-1)*(304*n^2 + 184*n - 99)*a(n-2) + 23*(n-2)*(n-1)*(19*n+21)*a(n-3). - Vaclav Kotesovec, Sep 18 2013

a(n) ~ c*d^n/(sqrt(Pi)*n^(3/2)), where d = 1/12*(8 + (10088 - 456*sqrt(57))^(1/3) + 2*(1261 + 57*sqrt(57))^(1/3)) = 4.219136248741586519... is the root of the equation -23 - 32*d - 8*d^2 + 4*d^3 = 0 and c = sqrt((893 + 2*(19*(4479877 - 238353*sqrt(57)))^(1/3) + 2*(19*(4479877 + 238353*sqrt(57)))^(1/3))/912) = 1.6945853695750331225605382455867539183676739... - Vaclav Kotesovec, Sep 18 2013, updated Nov 13 2023