OFFSET
1,2
COMMENTS
Considering graph evolutions (see the Flajolet link) with 3n vertices initially isolated, the probability of the occurrence of an acyclic graph at the point n, (n = 1/3 * 3n), in the uniform model, will be denoted by P13(n). In the case of the permutation model, the respective probability will be denoted by Pp13(n).
Pp13(n) / P13(n) ~ exp(4/9) since Pp13(n) = f(n) / C(N,n), where f(n) is the number of labeled forests with 3n nodes and n edges, and C(N,n), N = 3n *(3n-1)/2 (see the Lucatero link) is the number of labeled graphs with 3n nodes and n edges.
Because P13(n) = f(n)* n!* 2^n / (3n)^(2n), Pp13(n) / P13(n) = (3n)^(2n) / (C(N,n)* n! *2^n), and Lim_{n->oo} Pp13(n) / P13(n) = exp(4/9).
LINKS
P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.
Carlos R. Lucatero, Combinatorial Enumeration of Graphs.
FORMULA
Equals Lim_{n->oo} Pp13(n) / P13(n) = Lim_{n->oo} (3*n)^(2*n) / (binomial((3*n *(3*n-1)/2), n) * n! * 2^n).
EXAMPLE
1.55962349760678071553370928697947118639482401142214...
MAPLE
evalf(exp(4/9), 134);
MATHEMATICA
RealDigits[Exp[4/9], 10, 120][[1]] (* Harvey P. Dale, Jun 05 2023 *)
PROG
(PARI) exp(4/9)
CROSSREFS
KEYWORD
nonn,cons
AUTHOR
Washington Bomfim, Mar 04 2020
STATUS
approved