login
Number of labeled forests with n trees and 2n nodes and with the largest tree having exactly 3 nodes.
2

%I #18 Jun 12 2020 19:10:12

%S 0,12,180,5040,151200,6029100,276215940,14983768800,919653134400,

%T 63694663332300,4888759865289300,412920835111184400,

%U 38015644799992860000,3791220682538296507500,407033985027273005902500,46814497435454120812440000,5742194963898519585098640000,748255970051952172869045487500

%N Number of labeled forests with n trees and 2n nodes and with the largest tree having exactly 3 nodes.

%C Given a forest of 2n nodes and n trees, suppose that it has c_1 trees of 1 node, c_2 trees of 2 nodes, and c_3 trees of 3 nodes. We have c_1 + c_2 + c_3 = n, and c_1 + 2c_2 + 3c_3 = 2n, so c_1 = c_3, and c_2 = n - 2c_1. Because c_2 >= 0, c_1 <= floor(n/2). In this case the first formula in A332959 (with k = 3) reduces to the first formula below.

%D D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions, Addison-Wesley, 2005, pp. 39.

%F a(n) = (2*n)! * Sum_{c=1..floor(n/2)} 1/(c!^2 * (n-2*c)! * 2^(n-c)).

%F From _Vaclav Kotesovec_, Apr 17 2020: (Start)

%F a(n) ~ (2 + 4*sqrt(2))^(n + 1/2) * n^(n - 1/2) / (2^(5/4) * sqrt(Pi) * exp(n)).

%F a(n) ~ n! * (2 + 4*sqrt(2))^(n + 1/2) / (2^(7/4)*Pi*n). (End)

%e a(6) = 12! * ( 1 / (1!^2 * (6-2*1)! * 2^(6-1)) + 1 / (2!^2 * (6-2*2)! * 2^(6-2)) + 1 / (3!^2 * (6-2*3)! * 2^(6-3)) ) = 6029100.

%t Table[(2*n)! * (Hypergeometric2F1[1/2 - n/2, -n/2, 1, 8] - 1) / (2^n * n!), {n, 2, 20}] (* _Vaclav Kotesovec_, Apr 17 2020 *)

%o (PARI) a(n)= {(2*n)! * sum(c=1, n\2, 1/(c!^2 * (n-2*c)! * 2^(n-c)))};

%Y Column k=3 of A332959.

%K nonn

%O 1,2

%A _Washington Bomfim_, Apr 15 2020