|
|
A054548
|
|
Triangular array giving number of labeled graphs on n unisolated nodes and k=0...n*(n-1)/2 edges.
|
|
43
|
|
|
1, 0, 0, 1, 0, 0, 3, 1, 0, 0, 3, 16, 15, 6, 1, 0, 0, 0, 30, 135, 222, 205, 120, 45, 10, 1, 0, 0, 0, 15, 330, 1581, 3760, 5715, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 0, 0, 0, 0, 315, 4410, 23604, 73755, 159390, 259105, 331716, 343161, 290745, 202755, 116175
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,7
|
|
REFERENCES
|
F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, Page 29, Exercise 1.4.
|
|
LINKS
|
|
|
FORMULA
|
T(n, k) = Sum_{i=0..n} (-1)^(n-i)*C(n, i)*C(C(i, 2), k), k=0...n*(n-1)/2.
E.g.f.: exp(-x)*Sum_{n>=0} (1 + y)^C(n,2)*x^n/n!. - Geoffrey Critzer, Oct 07 2012
|
|
EXAMPLE
|
Triangle begins:
1
0
0 1
0 0 3 1
0 0 3 16 15 6 1
0 0 0 30 135 222 205 120 45 10 1
Row n = 4 counts the following graphs:
. . 12-34 12-13-14 12-13-14-23 12-13-14-23-24 12-13-14-23-24-34
13-24 12-13-24 12-13-14-24 12-13-14-23-34
14-23 12-13-34 12-13-14-34 12-13-14-24-34
12-14-23 12-13-23-24 12-13-23-24-34
12-14-34 12-13-23-34 12-14-23-24-34
12-23-24 12-13-24-34 13-14-23-24-34
12-23-34 12-14-23-24
12-24-34 12-14-23-34
13-14-23 12-14-24-34
13-14-24 12-23-24-34
13-23-24 13-14-23-24
13-23-34 13-14-23-34
13-24-34 13-14-24-34
14-23-24 13-23-24-34
14-23-34 14-23-24-34
14-24-34
(End)
|
|
MATHEMATICA
|
nn=5; s=Sum[(1+y)^Binomial[n, 2] x^n/n!, {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[ s Exp[-x], {x, 0, nn}], {x, y}] //Grid (* returns triangle indexed at n = 0, Geoffrey Critzer, Oct 07 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n], {2}], {k}], Union@@#==Range[n]&]], {n, 0, 5}, {k, 0, Binomial[n, 2]}] (* Gus Wiseman, Feb 14 2024 *)
|
|
CROSSREFS
|
This is the covering case of A084546.
A006125 counts simple graphs; also loop-graphs if shifted left.
|
|
KEYWORD
|
easy,nonn,tabf
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|