%I #114 Jan 17 2021 14:52:27

%S 1,1,15,435,18865,1092105,79170399,6899167275,702495121185,

%T 81857181636945,10742799174110575,1568060617808784099,

%U 251983549987815976785,44207398164005846558425,8407483858740005340602175,1722961754698440157865926875,378507890849998531093971032385

%N Number of forests with 2n nodes and n labeled trees. Also number of forests with exactly n edges on 2n labeled nodes.

%C From _Washington Bomfim_, Mar 20 2020: (Start)

%C Considering the uniform model of graph evolution [see the Flajolet link] with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at the critical point n is P(n) = a(n) * n! * 2^n / (2n)^(2n). Concerning the permutation model [see same link] the corresponding probability is Pp(n) = a(n) / A331505(2n).

%C By Kotesovec's approximation of a(n), P(n) ~ c1/n^(1/6), and Pp(n) ~ e^(3/4)* P(n), c1 = 0.577983047665... = (2/3)^(1/3) * sqrt(Pi) / Gamma(1/3).

%C In both models the presence of cycles in graphs evolving near the critical time should be estimated by the above approximations. (End)

%H Alois P. Heinz, <a href="/A302112/b302112.txt">Table of n, a(n) for n = 0..310</a>

%H P. Flajolet, D. E. Knuth, and B. Pittel, <a href="https://doi.org/10.1016/0012-365X(89)90087-3">The first cycles in an evolving graph</a>, Discrete Mathematics, 75(1-3):167-215, 1989.

%F a(n) = A105599(2*n,n) = A138464(2*n,n).

%F a(n) ~ c * 2^n * exp(n) * n^(n - 2/3), where c = 0.2305818... = 1 / (2^(1/6) * 3^(1/3) * Gamma(1/3)) [symbolic expression for c is conjectural]. - _Vaclav Kotesovec_, Jul 20 2019, updated Feb 20 2020

%F a(n) = (1/n!) * Sum_{j=0..n} (-1/2)^j * binomial(n,j) * binomial(2*n-1,n+j-1) * (2*n)^(n-j) * (n+j)!. - _Jon E. Schoenfield_, Jan 13 2020

%F a(n) = (-1)^n * (2*n)! * (Laguerre(n, 4*n) + 2*n*hypergeometric1F1(1 - n, 2, 4*n)) / (n! * 2^n). - _Vaclav Kotesovec_, Feb 19 2020

%F a(n) = (A332679(n) - 2*n*A332680(n)) * binomial(2*n, n) / 2^n. - _Vaclav Kotesovec_, Feb 20 2020

%F a(n) = (2*n)! * Sum_{P(2*n,n)} Product_{p=1..2*n} f(p)^c_p / (c_p! * p!^c_p), where f(n) = A000272(n) = n^(n-2) and P(2*n,n) are the partitions of 2*n with n parts, 1*c_1 + 2*c_2 + ... + (2*n)*c_n; c_1, c_2, ..., c_(2*n) >= 0.

%F - _Washington Bomfim_, Apr 05 2020

%p T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,

%p `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*

%p T(n-j, m-1), j=1..n-m+1))))

%p end:

%p a:= n-> T(2*n, n):

%p seq(a(n), n=0..20);

%t Flatten[{1, Table[Sum[(-1)^k * Binomial[n, k] * Binomial[2*n - 1, n - k] * 2^(n - 2*k) * n^(n - k) * (n + k)!, {k, 0, n} ] / n!, {n, 1, 20}]}] (* _Vaclav Kotesovec_, Jul 19 2019 *)

%t Table[(-1)^n * HypergeometricPFQ[{1 - 2*n, -n}, {1, -2*n}, 4*n] * (2*n)! / (n!*2^n), {n, 0, 20}] (* _Vaclav Kotesovec_, Jul 19 2019 *)

%t Table[(-1)^n * 2^n * Gamma[n + 1/2] * (2*n*Hypergeometric1F1[1 - n, 2, 4*n] + LaguerreL[n, 4*n]) / Sqrt[Pi], {n, 0, 20}] (* _Vaclav Kotesovec_, Feb 19 2020 *)

%Y Cf. A000272, A138464, A331500, A331505.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Apr 01 2018