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

1, 1, 2, 4, 9, 20, 54, 146, 436, 1372, 4577, 15971, 58376, 221876, 876012, 3583099, 15159817, 66248609, 298678064, 1387677971, 6637246978, 32648574416, 165002122350, 855937433641, 4553114299140, 24813471826280, 138417885372373, 789683693019999, 4603838061688077

Offset

0,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50

Formula

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

Example

The a(1) = 1 through a(4) = 9 graph edge sets:
  {}  {}    {}          {}
      {12}  {12}        {12}
            {12-13}     {12-13}
            {12-13-23}  {12-34}
                        {12-13-14}
                        {12-13-23}
                        {12-13-24}
                        {12-13-14-23}
                        {12-13-24-34}

Mathematica

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n], {2}]], Length[#]<=n&]]], {n, 0, 5}]

Prog

(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

Crossrefs

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

The connected covering case is A005703, labeled A129271.

Partial row sums of A008406, covering A370167.

The labeled version is A369192.

The version with loops is A370168, labeled A066383.

The covering case is A370316, labeled A369191.

A006125 counts graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

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

Sequence in context: A032200 A130969 A264293 * A034750 A079060 A225173

Adjacent sequences: A370312 A370313 A370314 * A370316 A370317 A370318

Keyword

nonn

Author

Gus Wiseman, Feb 18 2024

Status

approved