login
Number of planar planted trees with n non-root nodes and without isolated 2-valent nodes.
0

%I #11 Apr 15 2016 13:46:35

%S 0,1,0,2,2,7,14,41,107,307,871,2546,7497,22380,67366,204517,625132,

%T 1922700,5945469,18473841,57649699,180602285,567772883,1790663427,

%U 5663969707,17963483548,57112388657,181994536484,581168157605

%N Number of planar planted trees with n non-root nodes and without isolated 2-valent nodes.

%C An isolated 2-valent node is a 2-valent node non-adjacent to any other 2-valent node.

%D I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983,(2.7.11).

%F G.f.: Sum_{i >= 0} 1/(i+1)*binomial(2*i, i)*x^(i+1)*((1+x^3)/(1-x^2))^(i+1)*(1+x*(1+x^3)/(1-x^2))^(-(i+1)) or (1-x^2+x^3-sqrt((1-x^2+x^3)*(1-4*x+3*x^2-3*x^3)))/(2-2*x^2+2*x^3).

%F a(n) = Sum_{k=1..n}(((Sum_{j=1..k}(binomial(2*j-2,j-1)*(-1)^(j-k)*binomial(k,j)))*Sum_{j=0..(n-k)/2}(binomial(k,j)*binomial(n-k-j-1,n-k-2*j)))/k). - _Vladimir Kruchinin_, Apr 15 2016

%t Table[Sum[((Sum[Binomial[2 j - 2, j - 1] (-1)^(j - k) Binomial[k, j], {j, 1, k}]) Sum[Binomial[k, j] Binomial[n - k - j - 1, n - k - 2 j], {j,

%t 0, (n - k)/2}])/k, {k, 1, n}], {n, 0, 28}] (* _Michael De Vlieger_, Apr 15 2016 *)

%o (Maxima)

%o a(n):=sum(((sum(binomial(2*j-2,j-1)*(-1)^(j-k)*binomial(k,j),j,1,k))*sum(binomial(k,j)*binomial(n-k-j-1,n-k-2*j),j,0,(n-k)/2))/k,k,1,n); /* _Vladimir Kruchinin_, Apr 15 2016 */

%K nonn

%O 0,4

%A _Vladeta Jovovic_, Jun 13 2001