OFFSET
0,3
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.
FORMULA
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) = (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
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Apr 01 2018
STATUS
approved