login
Number of labeled simple graphs with n vertices and at most n edges (not necessarily covering).
14

%I #11 Jul 15 2024 10:22:35

%S 1,1,2,8,57,638,9949,198440,4791323,135142796,4346814276,156713948672,

%T 6251579884084,273172369790743,12969420360339724,664551587744173992,

%U 36543412829258260135,2146170890448154922648,134053014635659737513358,8872652968135849629240560

%N Number of labeled simple graphs with n vertices and at most n edges (not necessarily covering).

%F a(n) = Sum_{k=0..n} binomial(binomial(n,2),k).

%e The a(0) = 1 through a(3) = 8 graphs:

%e {} {} {} {}

%e {{1,2}} {{1,2}}

%e {{1,3}}

%e {{2,3}}

%e {{1,2},{1,3}}

%e {{1,2},{2,3}}

%e {{1,3},{2,3}}

%e {{1,2},{1,3},{2,3}}

%t Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[#]<=n&]],{n,0,5}]

%o (Python)

%o from math import comb

%o def A369192(n): return sum(comb(comb(n,2),k) for k in range(n+1)) # _Chai Wah Wu_, Jul 14 2024

%Y The version for loop-graphs is A066383, covering A369194.

%Y The case of equality is A116508, covering A367863, also A367862.

%Y The connected case is A129271, unlabeled A005703.

%Y The covering case is A369191, minimal case A053530.

%Y Counting only covered vertices gives A369193.

%Y A006125 counts graphs, unlabeled A000088.

%Y A006129 counts covering graphs, unlabeled A002494.

%Y A054548 counts graphs covering n vertices with k edges, with loops A369199.

%Y A133686 counts choosable graphs, covering A367869.

%Y A367867 counts non-choosable graphs, covering A367868.

%Y Cf. A000169, A000272, A000666, A001187, A006649, A057500, A143543.

%K nonn

%O 0,3

%A _Gus Wiseman_, Jan 17 2024