A331504 Number of labeled graphs with n nodes and floor(n*(n-1)/4) edges.

1, 1, 3, 20, 252, 6435, 352716, 40116600, 9075135300, 4116715363800, 3824345300380220, 7219428434016265740, 27217014869199032015600, 205397724721029574666088520, 3136262529306125724764953838760

Offset

1,3

Comments

The expected number of edges of a random graph is n*(n - 1)/4. [See the Cieslik reference.]

References

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

Links

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

Dietmar Cieslik, Counting Networks.

Carlos R. Lucatero, Combinatorial Enumeration of Graphs.

Formula

a(n) = binomial(binomial(n,2), floor(n*(n-1)/4)).

Example

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

Prog

(PARI) a(n) = binomial(binomial(n, 2), n*(n-1)\4);

Crossrefs

Cf. A000717 ("unlabeled case"), A084546.

Sequence in context: A262208 A324955 A183607 * A197322 A197975 A210906

Adjacent sequences: A331501 A331502 A331503 * A331505 A331506 A331507

Keyword

nonn

Author

Washington Bomfim, Jan 18 2020

Status

approved