OFFSET
0,2
COMMENTS
Considering the uniform model of graph evolution [Flajolet] with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at time n is P(n) = a(n)/(2n)^(2n). See the following.
Since endpoints of edges are in 1..2n, if at time n we write side by side the 2n endpoints of the included n edges, we can have any one of the (2n)^(2n) strings of length 2n in 2n characters [A085534]. A single forest G(V,E) corresponds to n! * 2^n sequences because the n edges of E(G) are exchanged for n! ways, and each permutation corresponds to 2^n sequences since each edge u-v can be in a sequence as u-v or v-u. So the number of distinct sequences of length 2n on 2n symbols formed by A302112(n) forests is a(n) = A302112(n) * n! * 2^n.
If t < n, P(n) is a lower bound of P(t). If t > n, P(n) is an upper bound of P(t), P(t) the probability of an acyclic graph in time t.
The expected value of the number of trials until the appearance of a forest at time n is ev(n) = 1/P(n) = (2*n)^(2*n) / a(n). Below is a table of n and corresponding values of ev(n) for selected values of n.
----------------------------------------------
n | 1 | 10 | 100 | 1000 | 10^4 | 10^5 | 10^6 |
|---+-----+------+------+------+-------+-------|
ev(n) | 2 |2.63 | 3.76 | 5.48 | 8.03 | 11.79 | 17.30 |
----------------------------------------------
(Expected values for n >= 10^4 determined using Vaclav Kotesovec's approximation of A302112.)
To obtain a bijection h: S -> {1,2,...,n}, where S is a given set of n elements (keys) it is only necessary to determine an acyclic graph from the elements of S. Because the expected number of generated graphs is small when the number of nodes N = 2n we can use space proportional to 2n to store a graph. If n = 10^5, for example, from table above we expect to generate 11.79 graphs. For details about determination of bijections see [Havas].
LINKS
Washington Bomfim, Experimental expected values
P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.
George Havas and Bohdan S. Majewski, Optimal algorithms for minimal perfect hashing
EXAMPLE
If n = 1 a(n) = 2, a(n)/(2*n)^(2*n) = 1/2. If we toss two coins we obtain one of the four ordered pairs: (H,H), (H,T), (T,H), or (T,T). The probability of a forest is 1/2, and the expected value of trials until a forest is 2.
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)*n!*2^n:
seq(a(n), n=0..14); # Alois P. Heinz, Jun 24 2021
MATHEMATICA
Array[(-1)^#*HypergeometricPFQ[{1 - 2 #, -#}, {1, -2 #}, 4 #]*(2 #)! &, 7] (* Michael De Vlieger, Feb 07 2020, after Vaclav Kotesovec at A302112 *)
PROG
sum(j = 0, n, (-1/2)^j * binomial(n, j) * binomial(2*n-1, n+j-1) * (2*n)^(n-j) * (n+j)!) / n! };
a(n) = A302112(n) * n! * 2^n;
CROSSREFS
KEYWORD
nonn
AUTHOR
Washington Bomfim, Feb 02 2020
EXTENSIONS
Edited by Washington Bomfim, Jun 14 2021
STATUS
approved