A331504 - OEIS

%I #25 Mar 24 2020 02:53:53

%S 1,1,3,20,252,6435,352716,40116600,9075135300,4116715363800,

%T 3824345300380220,7219428434016265740,27217014869199032015600,

%U 205397724721029574666088520,3136262529306125724764953838760

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

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

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

%H Dietmar Cieslik, <a href="https://math-inf.uni-greifswald.de/storages/uni-greifswald/fakultaet/mnf/mathinf/boldt/pdf-dateien/cieslik-counting-graphs.pdf">Counting Networks</a>.

%H Carlos R. Lucatero, <a href="https://www.intechopen.com/online-first/combinatorial-enumeration-of-graphs">Combinatorial Enumeration of Graphs</a>.

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

%e 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.

%e The non-isomorphic graphs with four nodes and three edges along with the corresponding number of labeled graphs are as follows:

%e .

%e   *--*     *--*        *

%e   | /      |           |

%e   |/ *     |           |

%e   *        *--*     *--*--*

%e    4        12         4

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

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

%K nonn

%O 1,3

%A _Washington Bomfim_, Jan 18 2020