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

0, 12, 180, 5040, 151200, 6029100, 276215940, 14983768800, 919653134400, 63694663332300, 4888759865289300, 412920835111184400, 38015644799992860000, 3791220682538296507500, 407033985027273005902500, 46814497435454120812440000, 5742194963898519585098640000, 748255970051952172869045487500

Offset

1,2

Comments

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.

References

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

Links

Table of n, a(n) for n=1..18.

Formula

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

From Vaclav Kotesovec, Apr 17 2020: (Start)

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

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

Example

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.

Mathematica

Table[(2*n)! * (Hypergeometric2F1[1/2 - n/2, -n/2, 1, 8] - 1) / (2^n * n!), {n, 2, 20}] (* Vaclav Kotesovec, Apr 17 2020 *)

Prog

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

Crossrefs

Column k=3 of A332959.

Sequence in context: A327079 A013924 A145560 * A230345 A166773 A202632

Adjacent sequences: A332957 A332958 A332959 * A332961 A332962 A332963

Keyword

nonn

Author

Washington Bomfim, Apr 15 2020

Status

approved