OFFSET
0,3
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
LINKS
Seiichi Manyama, Table of n, a(n) for n = 0..1000
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
EXAMPLE
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 +...
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 *)
PROG
(PARI) a(n, m=1)=sum(k=0, n, binomial(n+m, k)*m/(n+m)*binomial(2*k, n-k))
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Jun 18 2009
STATUS
approved