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

Author

Washington Bomfim, Jan 18 2020

Keywords

• nonn

Comments

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

Examples

			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
		

References

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

Links

• Dietmar Cieslik, Counting Networks.
• Carlos R. Lucatero, Combinatorial Enumeration of Graphs.

Crossrefs

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

Programs

PARI

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

Formula

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