|
| |
|
|
A002494
|
|
Number of n-node graphs without isolated nodes.
(Formerly M1762 N0699)
|
|
28
|
|
|
|
1, 0, 1, 2, 7, 23, 122, 888, 11302, 262322, 11730500, 1006992696, 164072174728, 50336940195360, 29003653625867536, 31397431814147073280, 63969589218557753586160, 245871863137828405125824848, 1787331789281458167615194471072, 24636021675399858912682459613241920
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Number of unlabeled simple graphs covering n vertices. - Gus Wiseman, Aug 02 2018
|
|
|
REFERENCES
|
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
W. L. Kocay, Some new methods in reconstruction theory, Combinatorial Mathematics IX, 952 (1982) 89--114. [From Benoit Jubin, Sep 06 2008]
W. L. Kocay, On reconstructing spanning subgraphs, Ars Combinatoria, 11 (1981) 301--313. [From Benoit Jubin, Sep 06 2008]
J. H. Redfield, The theory of group-reduced distributions, Amer. J. Math., 49 (1927), 433-435; reprinted in P. A. MacMahon, Coll. Papers I, pp. 805-827.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..75 (using A000088)
P. C. Fishburn and W. V. Gehrlein, Niche numbers, J. Graph Theory, 16 (1992), 131-139.
J. H. Redfield, The theory of group-reduced distributions [Annotated scan of pages 452 and 453 only]
Eric Weisstein's World of Mathematics, Isolated Point.
Eric Weisstein's World of Mathematics, Graphical Partition
Gus Wiseman, Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons.
|
|
|
FORMULA
|
O.g.f.: (1-x)*G(x) where G(x) is o.g.f. for A000088. - Geoffrey Critzer, Apr 14 2012
|
|
|
EXAMPLE
|
From Gus Wiseman, Aug 02 2018: (Start)
Non-isomorphic representatives of the a(4) = 7 graphs:
(12)(34)
(12)(13)(14)
(12)(13)(24)
(12)(13)(14)(23)
(12)(13)(24)(34)
(12)(13)(14)(23)(24)
(12)(13)(14)(23)(24)(34)
(End)
|
|
|
MAPLE
|
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
+add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
end:
a:= n-> b(n$2, [])-`if`(n>0, b(n-1$2, []), 0):
seq(a(n), n=0..20); # Alois P. Heinz, Aug 14 2019
|
|
|
MATHEMATICA
|
<< MathWorld`Graphs`
Length /@ (gp = Select[ #, GraphicalPartitionQ] & /@
Graphs /@ Range[9])
nn = 20; g = Sum[NumberOfGraphs[n] x^n, {n, 0, nn}]; CoefficientList[Series[ g (1 - x), {x, 0, nn}], x] (*Geoffrey Critzer, Apr 14 2012*)
sysnorm[m_]:=If[Union@@m!=Range[Max@@Flatten[m]], sysnorm[m/.Rule@@@Table[{(Union@@m)[[i]], i}, {i, Length[Union@@m]}]], First[Sort[sysnorm[m, 1]]]];
sysnorm[m_, aft_]:=If[Length[Union@@m]<=aft, {m}, With[{mx=Table[Count[m, i, {2}], {i, Select[Union@@m, #>=aft&]}]}, Union@@(sysnorm[#, aft+1]&/@Union[Table[Map[Sort, m/.{par+aft-1->aft, aft->par+aft-1}, {0, 1}], {par, First/@Position[mx, Max[mx]]}]])]];
Table[Length[Union[sysnorm/@Select[Subsets[Select[Subsets[Range[n]], Length[#]==2&]], Union@@#==Range[n]&]]], {n, 6}] (* Gus Wiseman, Aug 02 2018 *)
b[n_, i_, l_] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1)/2] + Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
a[n_] := b[n, n, {}] - If[n > 0, b[n-1, n-1, {}], 0];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2019, after Alois P. Heinz *)
|
|
|
CROSSREFS
|
Equals first differences of A000088. Cf. A006129.
Cf. also A006647, A006648, A006649, A006650, A006651.
Cf. A000612, A001187, A055621, A304998.
Sequence in context: A000903 A049021 A332802 * A032264 A139522 A163158
Adjacent sequences: A002491 A002492 A002493 * A002495 A002496 A002497
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms from Vladeta Jovovic, Apr 10 2000
a(0) added from David W. Wilson, Aug 24 2008
|
|
|
STATUS
|
approved
|
| |
|
|
