login
Number of labeled rooted trees with all 2n nodes of odd degree.
1

%I #28 Nov 06 2024 04:14:36

%S 2,16,576,47104,6860800,1562148864,512260833280,228646878969856,

%T 133296779352342528,98349146136012390400,89583293999931442855936,

%U 98732413018143104723582976,129497500112719525122855141376,199333356644821012200519079297024

%N Number of labeled rooted trees with all 2n nodes of odd degree.

%C There are no such trees with an odd number of nodes.

%D I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

%H G. C. Greubel, <a href="/A060279/b060279.txt">Table of n, a(n) for n = 1..210</a>

%F a(n) = (n/2^n)*Sum_{k=0..n} binomial(n, k)*(n-2*k)^(n-2).

%F a(n) = 2*n * A007106(n).

%F a(n) ~ sqrt(1+s^2) * s^(2*n-1) * 2^(2*n) * n^(2*n-1) / exp(2*n), where s = 1.5088795615383199289... is the root of the equation sqrt(1+s^2) = s*log(s+sqrt(1+s^2)). - _Vaclav Kotesovec_, Jan 23 2014

%p a:= j-> (n-> (n/2^n)*add(binomial(n, k)*(n-2*k)^(n-2), k=0..n))(2*j):

%p seq(a(n), n=1..15); # _Alois P. Heinz_, Sep 27 2020

%t Flatten[{2,Table[n/2^n*Sum[Binomial[n,k]*(n-2*k)^(n-2),{k,0,n}],{n,4,30,2}]}] (* _Vaclav Kotesovec_, Jan 23 2014 *)

%t A060279[n_]:= n*Sum[Binomial[2*n,k]*(n-k)^(2*n-2), {k,0,n-1}] +Boole[n==1];

%t Table[A060279[n], {n,40}] (* _G. C. Greubel_, Nov 05 2024 *)

%o (PARI) a(n) = n/2^n*sum(k=0, n, binomial(n, k)*(n-2*k)^(n-2)) \\ _Michel Marcus_, Jun 17 2013

%o (Magma)

%o A060279:= func< n | n eq 1 select 2 else n*(&+[Binomial(2*n,k)*(n-k)^(2*n-2) : k in [0..n-1]]) >;

%o [A060279(n): n in [1..30]]; // _G. C. Greubel_, Nov 05 2024

%o (SageMath)

%o def A060279(n): return n*sum( binomial(2*n,k)*(n-k)^(2*n-2) for k in range(n)) + int(n==1)

%o [A060279(n) for n in range(1,41)] # _G. C. Greubel_, Nov 05 2024

%Y Cf. A007106.

%K easy,nonn,changed

%O 1,1

%A _Vladeta Jovovic_, Mar 28 2001