A331505 Number of labeled graphs with n nodes and floor(n/2) edges.

1, 1, 3, 15, 45, 455, 1330, 20475, 58905, 1221759, 3478761, 90858768, 256851595, 8093990190, 22760723700, 840261910995, 2353351951665, 99615373765775, 278110855548955, 13278694407181203, 36976937738226486

Offset: 1

Author

Washington Bomfim, Jan 18 2020

Keywords

• nonn
• look

Comments

Considering the permutation model of graph evolution (see the Flajolet reference) with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at the critical point n is Pp(n) = A302112(n)/a(2n). Note that a(2n) is the number of labeled graphs with 2n nodes and n edges.

Since a(2n) = C(C(2n, 2), n) we have Pp(n)= A302112(n)/C(C(2n, 2), n).

Therefore, by Vaclav Kotesovec's approximation in A302112, Pp(n) ~ e^(3/4) * P(n), where P(n) = c1 / n^(1/6) is the corresponding probability in the uniform model. Cf. A331500.

If t < n, P(n) is a lower bound of P(t). If t > n, P(n) is an upper bound of P(t). Here P(t) is the probability of an acyclic graph in time t.

Concerning the permutation model, the presence of cycles in graphs evolving near the critical time should be estimated by the above approximation.

Examples

			a(4) is 15 because for n = 4, floor(n/2) = 2, and there are two graphs with four points and two edges. See the figure below or the J. Riordan reference.
The non-isomorphic graphs with four nodes and two edges along with the corresponding number of labeled graphs are as follows:
.
  *--*     *  *
  |        |  |
  |        |  |
  *  *     *  *
   12        3
Pp(2) = A302112(2)/a(4) = 15/15 = 1. All the graphs with four nodes and two edges are acyclic.
		

References

• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 109.

Links

• Washington Bomfim, Approximation of Pp(n)
• 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.

Crossrefs

Cf. A000717, A084546, A331504, A302112 (numerators of Pp(n)), A331500, A331501.

Programs

PARI

C(x, y) = binomial(x, y);
a(n) = C(C(n,2), n\2);
A302112(n)={my(S=0, j); /* From Jon E. Schoenfield's formula in A302112. */
for(j = 0, n,
   S+=(-1/2)^j* C(n, j) * C(2*n-1, n+j-1) * (2*n)^(n-j) * (n+j)!
   );
(1/n!)*S
}; /* end A302112(n) */
c1 = (2/3)^(1/3) * sqrt(Pi) / gamma(1/3);
UpBoundP(n) = c1 / n^(1/6);            /* Approximation for P(n) */
UpBoundPp(n) = exp(3/4) * UpBoundP(n); /* Approximation for Pp(n) */
Pp(n) = A302112(n)/a(2*n);
Ratio(n) = UpBoundPp(n) / Pp(n);

Formula

a(n) = C( C(n,2), floor(n/2) ).