|
%I #186 Jun 24 2021 19:29:27
%S 1,2,120,20880,7244160,4193683200,3648171985920,4450790792448000,
%T 7251098441261875200,15208619045076276019200,
%U 39919072914444753469440000,128188338317208930555828633600,494389344738688341547326898176000,2255096937522349816552823932846080000
%N a(n) = A302112(n) * n! * 2^n.
%C 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.
%C 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.
%C 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.
%C 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.
%C ----------------------------------------------
%C n | 1 | 10 | 100 | 1000 | 10^4 | 10^5 | 10^6 |
%C |---+-----+------+------+------+-------+-------|
%C ev(n) | 2 |2.63 | 3.76 | 5.48 | 8.03 | 11.79 | 17.30 |
%C ----------------------------------------------
%C (Expected values for n >= 10^4 determined using _Vaclav Kotesovec_'s approximation of A302112.)
%C 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].
%H Washington Bomfim, <a href="/A331500/a331500_2.txt">Experimental expected values</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.
%H George Havas and Bohdan S. Majewski, <a href="https://staff.itee.uq.edu.au/havas/TR0234.pdf">Optimal algorithms for minimal perfect hashing</a>
%F a(n) = A302112(n) * n! * 2^n = A000165(n) * A302112(n).
%e 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.
%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)*n!*2^n:
%p seq(a(n), n=0..14); # _Alois P. Heinz_, Jun 24 2021
%t Array[(-1)^#*HypergeometricPFQ[{1 - 2 #, -#}, {1, -2 #}, 4 #]*(2 #)! &, 7] (* _Michael De Vlieger_, Feb 07 2020, after _Vaclav Kotesovec_ at A302112 *)
%o (PARI) A302112(n) = { \\ From _Jon E. Schoenfield_'s formula in A302112.
%o sum(j = 0, n, (-1/2)^j * binomial(n, j) * binomial(2*n-1, n+j-1) * (2*n)^(n-j) * (n+j)!) / n! };
%o a(n) = A302112(n) * n! * 2^n;
%Y Cf. A000165, A085534, A302112, A331505.
%K nonn
%O 0,2
%A _Washington Bomfim_, Feb 02 2020
%E Edited by _Washington Bomfim_, Jun 14 2021
| 