A370316 - OEIS

A370316

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

%I #10 Feb 19 2024 22:56:32

%S 1,0,1,2,5,10,28,68,193,534,1568,4635,14146,43610,137015,435227,

%T 1400058,4547768,14917504,49348612,164596939,553177992,1872805144,

%U 6385039022,21917878860,75739158828,263438869515,922219844982,3249042441125,11519128834499,41097058489426

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

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

%e The a(0) = 1 through a(5) = 10 simple graphs:

%e {} . {12} {12-13} {12-34} {12-13-45}

%e {12-13-23} {12-13-14} {12-13-14-15}

%e {12-13-24} {12-13-14-25}

%e {12-13-14-23} {12-13-23-45}

%e {12-13-24-34} {12-13-24-35}

%e {12-13-14-15-23}

%e {12-13-14-23-25}

%e {12-13-14-23-45}

%e {12-13-14-25-35}

%e {12-13-24-35-45}

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

%o (PARI) \\ G defined in A008406.

%o 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

%Y The connected case is A005703, labeled A129271.

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

%Y The labeled version is A369191.

%Y Partial row sums of A370167, covering case of A008406.

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

%Y The version with loops is A370169, labeled A369194.

%Y The non-covering version is A370315, labeled A369192.

%Y A006125 counts graphs, unlabeled A000088.

%Y A006129 counts covering graphs, unlabeled A002494.

%Y A322661 counts covering loop-graphs, unlabeled A322700.

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

%K nonn

%O 0,4

%A _Gus Wiseman_, Feb 18 2024

%E a(8) onwards from _Andrew Howroyd_, Feb 19 2024