A161634 - OEIS

%I #18 Nov 13 2023 11:18:37

%S 1,1,3,8,25,81,274,953,3389,12265,45025,167256,627540,2374672,9052447,

%T 34731401,134010573,519683813,2024370167,7917605996,31080085431,

%U 122407860927,483558273368,1915535953655,7607408410408,30283240593756

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

%C 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

%H Seiichi Manyama, <a href="/A161634/b161634.txt">Table of n, a(n) for n = 0..1000</a>

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

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

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

%F ...

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

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

%F 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

%F 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

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

%e (1 + x*A(x))^2 = 1 + 2*x + 3*x^2 + 8*x^3 + 23*x^4 + 72*x^5 + 237*x^6 +...

%t Table[Sum[Binomial[n+1,k]/(n+1)*Binomial[2*k,n-k],{k,0,n}],{n,0,20}] (* _Vaclav Kotesovec_, Sep 18 2013 *)

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

%K nonn

%O 0,3

%A _Paul D. Hanna_, Jun 18 2009