A370316 Number of unlabeled simple graphs covering n vertices with at most n edges.

1, 0, 1, 2, 5, 10, 28, 68, 193, 534, 1568, 4635, 14146, 43610, 137015, 435227, 1400058, 4547768, 14917504, 49348612, 164596939, 553177992, 1872805144, 6385039022, 21917878860, 75739158828, 263438869515, 922219844982, 3249042441125, 11519128834499, 41097058489426

Offset: 0

Author

Gus Wiseman, Feb 18 2024

Keywords

• nonn

Examples

			The a(0) = 1 through a(5) = 10 simple graphs:
  {}  .  {12}  {12-13}     {12-34}        {12-13-45}
               {12-13-23}  {12-13-14}     {12-13-14-15}
                           {12-13-24}     {12-13-14-25}
                           {12-13-14-23}  {12-13-23-45}
                           {12-13-24-34}  {12-13-24-35}
                                          {12-13-14-15-23}
                                          {12-13-14-23-25}
                                          {12-13-14-23-45}
                                          {12-13-14-25-35}
                                          {12-13-24-35-45}
		

Links

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

Crossrefs

The connected case is A005703, labeled A129271.

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

The labeled version is A369191.

Partial row sums of A370167, covering case of A008406.

The non-covering version with loops is A370168, labeled A066383.

The version with loops is A370169, labeled A369194.

The non-covering version is A370315, labeled A369192.

A006125 counts graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

A322661 counts covering loop-graphs, unlabeled A322700.

Cf. A054548, A062734, A116508, A367862, A367863, A368599, A369193.

Programs

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}],{0,n}], Union@@#==Range[n]&]]],{n,0,5}]

PARI

\\ G defined in A008406.
a(n)=my(A=O(x*x^n)); if(n==0, 1, polcoef((G(n,A)-G(n-1,A))/(1-x), n)) \\ Andrew Howroyd, Feb 19 2024

Extensions

a(8) onwards from Andrew Howroyd, Feb 19 2024