login
Number of binary rooted trees with n nodes and internal path length n.
6

%I #22 Jan 31 2019 21:32:15

%S 1,1,0,2,0,1,4,0,4,2,8,6,8,8,8,40,4,29,40,52,56,64,116,112,200,86,296,

%T 366,360,432,652,800,840,1470,1116,2048,2356,3052,3524,4220,5648,6964,

%U 9660,8688,14128,17024,19432,23972,32784,37873,44912,59672,67560,93684

%N Number of binary rooted trees with n nodes and internal path length n.

%C Self-convolution equals A095830 (number of binary trees of path length n). - _Paul D. Hanna_, Aug 20 2007

%D Knuth Vol. 1 Sec. 2.3.4.5, Problem 5.

%H Alois P. Heinz, <a href="/A108643/b108643.txt">Table of n, a(n) for n = 0..1000</a>

%F G.f. = B(w, w) where B(w, z) is defined in A095830.

%F G.f.: A(x) = 1 + x*(A_2)^2; A_2 = 1 + x^2*(A_3)^2; A_3 = 1 + x^3*(A_4)^2; ... A_n = 1 + x^n*(A_{n+1})^2 for n>=1 with A_1 = A(x). - _Paul D. Hanna_, Aug 20 2007

%p A:= proc(n,k) option remember; if n=0 then 1 else convert(series(1+ x^k*A(n-1, k+1)^2, x,n+1), polynom) fi end: a:= n-> coeff(A(n,1), x,n): seq(a(n), n=0..60); # _Alois P. Heinz_, Aug 22 2008

%t A[n_, k_] := A[n, k] = If[n==0, 1, 1+x^k*A[n-1, k+1]^2 + O[x]^(n+1) // Normal]; a[n_] := SeriesCoefficient[A[n, 1], {x, 0, n}]; Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Mar 14 2017, after _Alois P. Heinz_ *)

%o (PARI) {a(n)=local(A=1+x*O(x^n)); for(j=0,n-1,A=1+x^(n-j)*A^2);polcoeff(A,n)} - _Paul D. Hanna_, Aug 20 2007

%K nonn

%O 0,4

%A _N. J. A. Sloane_ and _Nadia Heninger_, Jul 08 2005

%E More terms from _Vladeta Jovovic_, Jul 08 2005