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

1, 1, 15, 435, 18865, 1092105, 79170399, 6899167275, 702495121185, 81857181636945, 10742799174110575, 1568060617808784099, 251983549987815976785, 44207398164005846558425, 8407483858740005340602175, 1722961754698440157865926875, 378507890849998531093971032385

Offset: 0

Author

Alois P. Heinz, Apr 01 2018

Keywords

• nonn

Comments

From Washington Bomfim, Mar 20 2020: (Start)

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).

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).

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..310
• P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.

Crossrefs

Cf. A000272, A138464, A331500, A331505.

Programs

Maple

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(2*n, n):
seq(a(n), n=0..20);

Mathematica

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 *)
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 *)
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 *)

Formula

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

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

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

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

a(n) = (A332679(n) - 2*n*A332680(n)) * binomial(2*n, n) / 2^n. - Vaclav Kotesovec, Feb 20 2020

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.

- Washington Bomfim, Apr 05 2020