login
Number of unlabeled simple graphs with n possibly isolated vertices and up to n edges.
5

%I #10 Feb 20 2024 19:28:41

%S 1,1,2,4,9,20,54,146,436,1372,4577,15971,58376,221876,876012,3583099,

%T 15159817,66248609,298678064,1387677971,6637246978,32648574416,

%U 165002122350,855937433641,4553114299140,24813471826280,138417885372373,789683693019999,4603838061688077

%N Number of unlabeled simple graphs with n possibly isolated vertices and up to n edges.

%H Andrew Howroyd, <a href="/A370315/b370315.txt">Table of n, a(n) for n = 0..50</a>

%F Sum of first n+1 terms of row n of A008406.

%e The a(1) = 1 through a(4) = 9 graph edge sets:

%e {} {} {} {}

%e {12} {12} {12}

%e {12-13} {12-13}

%e {12-13-23} {12-34}

%e {12-13-14}

%e {12-13-23}

%e {12-13-24}

%e {12-13-14-23}

%e {12-13-24-34}

%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}]], Length[#]<=n&]]],{n,0,5}]

%o (PARI) a(n) = if(n<=1, n>=0, polcoef(G(n, O(x*x^n))/(1-x),n)) \\ G(n) defined in A008406. - _Andrew Howroyd_, Feb 20 2024

%Y The case of exactly n edges is A001434, covering A006649.

%Y The connected covering case is A005703, labeled A129271.

%Y Partial row sums of A008406, covering A370167.

%Y The labeled version is A369192.

%Y The version with loops is A370168, labeled A066383.

%Y The covering case is A370316, labeled A369191.

%Y A006125 counts graphs, unlabeled A000088.

%Y A006129 counts covering graphs, unlabeled A002494.

%Y Cf. A000666, A322661, A322700, A369194, A369196, A369197, A369199, A370169.

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 18 2024