|
| |
|
|
A161634
|
|
G.f. satisfies A(x) = 1/(1 - x*(1 + x*A(x))^2).
|
|
11
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
