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,3

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.

References

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

Links

Table of n, a(n) for n=1..21.

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.

Formula

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

Example

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.

Prog

(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);

Crossrefs

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

Sequence in context: A178669 A110464 A261505 * A088108 A226030 A232077

Adjacent sequences: A331502 A331503 A331504 * A331506 A331507 A331508

Keyword

nonn,look

Author

Washington Bomfim, Jan 18 2020

Status

approved