|
|
A331504
|
|
Number of labeled graphs with n nodes and floor(n*(n-1)/4) edges.
|
|
1
|
|
|
1, 1, 3, 20, 252, 6435, 352716, 40116600, 9075135300, 4116715363800, 3824345300380220, 7219428434016265740, 27217014869199032015600, 205397724721029574666088520, 3136262529306125724764953838760
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|