login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002494 Number of n-node graphs without isolated nodes.
(Formerly M1762 N0699)
6

%I M1762 N0699

%S 1,0,1,2,7,23,122,888,11302,262322,11730500,1006992696,164072174728,

%T 50336940195360,29003653625867536,31397431814147073280,

%U 63969589218557753586160,245871863137828405125824848

%N Number of n-node graphs without isolated nodes.

%C Number of unlabeled simple graphs covering n vertices. - _Gus Wiseman_, Aug 02 2018

%D F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.

%D W. L. Kocay, Some new methods in reconstruction theory, Combinatorial Mathematics IX, 952 (1982) 89--114. [From _Benoit Jubin_, Sep 06 2008]

%D W. L. Kocay, On reconstructing spanning subgraphs, Ars Combinatoria, 11 (1981) 301--313. [From _Benoit Jubin_, Sep 06 2008]

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A002494/b002494.txt">Table of n, a(n) for n=0..75</a> (using A000088)

%H P. C. Fishburn and W. V. Gehrlein, <a href="https://doi.org/10.1002/jgt.3190160204">Niche numbers</a>, J. Graph Theory, 16 (1992), 131-139.

%H J. H. Redfield, <a href="/A002494/a002494.pdf">The theory of group-reduced distributions</a> [Annotated scan of pages 452 and 453 only]

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IsolatedPoint.html">Isolated Point.</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphicalPartition.html">Graphical Partition</a>

%H Gus Wiseman, <a href="/A048143/a048143_4.txt">Sequences enumerating clutters, antichains, hypertrees, and hyperforests, organized by labeling, spanning, and allowance of singletons</a>.

%F O.g.f.: (1-x)*G(x) where G(x) is o.g.f. for A000088. - _Geoffrey Critzer_, Apr 14 2012.

%e From _Gus Wiseman_, Aug 02 2018: (Start)

%e Non-isomorphic representatives of the a(4) = 7 graphs:

%e (12)(34)

%e (12)(13)(14)

%e (12)(13)(24)

%e (12)(13)(14)(23)

%e (12)(13)(24)(34)

%e (12)(13)(14)(23)(24)

%e (12)(13)(14)(23)(24)(34)

%e (End)

%t << MathWorld`Graphs`

%t Length /@ (gp = Select[ #, GraphicalPartitionQ] & /@

%t Graphs /@ Range[9])

%t 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*)

%t 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]]]];

%t 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]]}]])]];

%t Table[Length[Union[sysnorm/@Select[Subsets[Select[Subsets[Range[n]],Length[#]==2&]],Union@@#==Range[n]&]]],{n,6}] (* _Gus Wiseman_, Aug 02 2018 *)

%Y Equals first differences of A000088. Cf. A006129.

%Y Cf. also A006647, A006648, A006649, A006650, A006651.

%Y Cf. A000612, A001187, A055621, A304998.

%K nonn,nice

%O 0,4

%A _N. J. A. Sloane_.

%E More terms from _Vladeta Jovovic_, Apr 10 2000

%E a(0) added from David Wilson, Aug 24 2008

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 02:05 EST 2018. Contains 318049 sequences. (Running on oeis4.)