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

 

Logo

The October issue of the Notices of the Amer. Math. Soc. has an article about the OEIS.

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 20:09 EDT 2018. Contains 315356 sequences. (Running on oeis4.)