A331500 a(n) = A302112(n) * n! * 2^n.

1, 2, 120, 20880, 7244160, 4193683200, 3648171985920, 4450790792448000, 7251098441261875200, 15208619045076276019200, 39919072914444753469440000, 128188338317208930555828633600, 494389344738688341547326898176000, 2255096937522349816552823932846080000

Offset: 0

Author

Washington Bomfim, Feb 02 2020

Keywords

• nonn

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

Examples

			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.
		

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

Crossrefs

Cf. A000165, A085534, A302112, 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)*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 *)

PARI

A302112(n) = { \\ From Jon E. Schoenfield's formula in A302112.
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;

Formula

a(n) = A302112(n) * n! * 2^n = A000165(n) * A302112(n).

Extensions

Edited by Washington Bomfim, Jun 14 2021