|
%I #16 Feb 17 2024 12:41:03
%S 0,0,0,2,15,110,936,12073,273972,12003332,1018992968,165091159269,
%T 50502031331411,29054155657134165,31426485969804026075,
%U 64001015704527557101231,245935864153532932681481794,1787577725145611700547871854870,24637809253125004524383007473440146
%N Number of unlabeled graphs of positive excess with n nodes.
%C We can find in "The Birth of the Giant Component" p. 53, see the link, the following: "The excess of a graph or multigraph is the number of edges plus the number of acyclic components, minus the number of vertices."
%C If G has just one complex component with 4 nodes, the "non-complex part" of G can be,
%C a) One forest of order 4. There are 6 forests, so 2*6=12 graphs.
%C b) One triangle and one isolated vertex, or 2*1=2 graphs.
%C c) One unicyclic graph of order 4, so 2*2=4 graphs.
%C Also the number of unchoosable unlabeled graphs with up to n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The labeled version is A367867, covering A367868, connected A140638. - _Gus Wiseman_, Feb 13 2024
%H Svante Janson, Donald E. Knuth, Tomasz Luczak and Boris Pittel, <a href="http://www.math.uu.se/~svante/papers/index.html">The Birth of the Giant Component</a>.
%F a(n) = A000088(n) - A134964(n).
%e Below we show that a(8) = 12073. Note that A140636(n) is the number of connected graphs of positive excess with n nodes.
%e Let G be a disconnected graph of positive excess with 8 nodes. In this case, G has one or two complex components. We have 3 graphs of order 8 with two complex components. One of those graphs is depicted in the figure below:
%e O---O...O---O
%e |\..|...|\./|
%e |.\.|...|.X.|
%e |..\|...|/.\|
%e O---O...O---O
%e If G has one complex component with 5 nodes, the non-complex part of G can be,
%e a) One forest of order 3. There are 3 forests, so A140636(5) * 3 = 39 graphs.
%e b) One triangle, so A140636(5) = 13 graphs.
%e If G has one complex component with 6 nodes, the non-complex part of G is a forest of order 2. There are 2 forests. We have A140636(6) * 2, or 186 graphs.
%e If G has one complex component with 7 nodes, the non-complex part of G is one isolated vertex. We have A140636(7), or 809 graphs.
%e Finally if G is connected, we have A140636(8), or 11005 graphs.
%e The total is 3 + 12 + 2 + 4 + 39 + 13 + 186 + 809 + 11005 = 12073.
%t brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
%t Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{2}]],Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,5}] (* _Gus Wiseman_, Feb 14 2024 *)
%Y Cf. A000088, A005195, A001429.
%Y The labeled complement is A133686, covering A367869, connected A129271.
%Y The complement is A134964, connected A005703.
%Y The connected covering case is A140636.
%Y The labeled version is A367867, covering A367868, connected A140638.
%Y Set-systems not of this type are A367902, ranks A367906.
%Y Set-systems of this type are A367903, ranks A367907.
%Y For set-systems we have A368094, complement A368095.
%Y For multiset partitions we have A368097, complement A368098.
%Y Factorizations of this type are A368413, complement A368414.
%Y Cf. A001349, A002494, A006125, A055621, A367769, A367770, A367901.
%K nonn
%O 1,4
%A _Washington Bomfim_, May 21 2008
| 