A001187 -id:A001187 - cp's OEIS frontend

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

1, 1, 2, 8, 57, 638, 9949, 198440, 4791323, 135142796, 4346814276, 156713948672, 6251579884084, 273172369790743, 12969420360339724, 664551587744173992, 36543412829258260135, 2146170890448154922648, 134053014635659737513358, 8872652968135849629240560

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

			The a(0) = 1 through a(3) = 8 graphs:
  {}  {}  {}       {}
          {{1,2}}  {{1,2}}
                   {{1,3}}
                   {{2,3}}
                   {{1,2},{1,3}}
                   {{1,2},{2,3}}
                   {{1,3},{2,3}}
                   {{1,2},{1,3},{2,3}}

The version for loop-graphs is A066383, covering A369194.
The case of equality is A116508, covering A367863, also A367862.
The connected case is A129271, unlabeled A005703.
The covering case is A369191, minimal case A053530.
Counting only covered vertices gives A369193.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable graphs, covering A367869.
A367867 counts non-choosable graphs, covering A367868.
Cf. A000169, A000272, A000666, A001187, A006649, A057500, A143543.

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

from math import comb
def A369192(n): return sum(comb(comb(n,2),k) for k in range(n+1)) # Chai Wah Wu, Jul 14 2024

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

A371452 Number of connected components of the prime indices of the binary indices of n.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 4, 3, 4, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 4, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5

Offset: 1

Gus Wiseman, Apr 01 2024

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The prime indices of binary indices of 281492156579880 are {{1,1},{1,2},{3,4},{4,4}}, with 2 connected components {{1,1},{1,2}} and {{3,4},{4,4}}, so a(281492156579880) = 2.

Positions of first appearances are A080355, opposite A325782.
For prime indices of prime indices we have A305079, ones A305078.
For binary indices of binary indices we have A326753, ones A326749.
Positions of ones are A371291.
For binary indices of prime indices we have A371451, ones A325118.
A001187 counts connected graphs.
A007718 counts non-isomorphic connected multiset partitions.
A048143 counts connected antichains of sets.
A048793 lists binary indices, reverse A272020, length A000120, sum A029931.
A070939 gives length of binary expansion.
A112798 lists prime indices, reverse A296150, length A001222, sum A056239.
A326964 counts connected set-systems, covering A323818.
Cf. A000720, A019565, A087086, A096111, A325097, A326782, A368109, A371292, A371294, A371445, A371447.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
bix[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[csm[prix/@bix[n]]],{n,100}]

A053549 Number of labeled rooted connected graphs.

Original entry on oeis.org

0, 1, 2, 12, 152, 3640, 160224, 13063792, 2012388736, 596666619648, 344964885948160, 392058233038486784, 880255154481199466496, 3916538634445633156373504, 34603083354426212294072477696, 607915214065957203519146330173440

Offset: 0

N. J. A. Sloane, Jan 16 2000

nonn

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 10, R_p.
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.20, G(x).

T. D. Noe, Table of n, a(n) for n=0..50

Cf. A006125.

q:=30; m:=20; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( (&+[2^Binomial(j, 2)*x^j/Factorial(j-1): j in [1..q]])/(&+[2^Binomial(k, 2)*x^k/Factorial(k):k in [0..q]]) )); [0] cat [Factorial(n)*b[n]: n in [1..m-1]]; // G. C. Greubel, May 16 2019

add(2^binomial(n,2)*x^n/(n-1)!,n=1..31)/add(2^binomial(n,2)*x^n/n!,n=0..31);

f[x_, lim_] := Sum[2^Binomial[n, 2]*x^n/(n - 1)!, {n, 1, lim}] / Sum[2^Binomial[n, 2]*x^n/n!, {n, 0, lim}]; nn = 15; Range[0, nn]! CoefficientList[Series[f[x, nn], {x, 0, nn}], x] (* T. D. Noe, Oct 21 2011 *)

q=30; my(x='x+O('x^20)); concat([0], Vec(serlaplace( sum(j=1,q, 2^binomial(j, 2)*x^j/(j-1)!)/(sum(k=0,q,2^binomial(k, 2)*x^k/k!)) ))) \\ G. C. Greubel, May 16 2019

q=30; m = 20; T = taylor(sum(2^binomial(j, 2)*x^j/factorial(j-1) for j in (1..q))/(sum(2^binomial(k, 2)*x^k/factorial(k) for k in (0..q))), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # G. C. Greubel, May 16 2019

E.g.f.: (Sum_{n>1} 2^binomial(n, 2)*x^n/(n-1)!)/(Sum_{n>=0} 2^binomial(n, 2)*x^n/n!).

a(n) = n * A001187(n).

A054780 Number of n-covers of a labeled n-set.

Original entry on oeis.org

1, 1, 3, 32, 1225, 155106, 63602770, 85538516963, 386246934638991, 6001601072676524540, 327951891446717800997416, 64149416776011080449232990868, 45546527789182522411309599498741023, 118653450898277491435912500458608964207578

Offset: 0

Vladeta Jovovic, May 21 2000

Also, number of n X n rational {0,1}-matrices with no zero rows or columns and with all rows distinct, up to permutation of rows.

			From _Gus Wiseman_, Dec 19 2023: (Start)
Number of ways to choose n nonempty sets with union {1..n}. For example, the a(3) = 32 covers are:
  {1}{2}{3}  {1}{2}{13}  {1}{2}{123}  {1}{12}{123}  {12}{13}{123}
             {1}{2}{23}  {1}{3}{123}  {1}{13}{123}  {12}{23}{123}
             {1}{3}{12}  {1}{12}{13}  {1}{23}{123}  {13}{23}{123}
             {1}{3}{23}  {1}{12}{23}  {2}{12}{123}
             {2}{3}{12}  {1}{13}{23}  {2}{13}{123}
             {2}{3}{13}  {2}{3}{123}  {2}{23}{123}
                         {2}{12}{13}  {3}{12}{123}
                         {2}{12}{23}  {3}{13}{123}
                         {2}{13}{23}  {3}{23}{123}
                         {3}{12}{13}  {12}{13}{23}
                         {3}{12}{23}
                         {3}{13}{23}
(End)

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

Main diagonal of A055154.
Cf. A048291, A088310, A181230, A259763.
Covers with any number of edges are counted by A003465, unlabeled A055621.
Connected graphs of this type are counted by A057500, unlabeled A001429.
This is the covering case of A136556.
The case of graphs is A367863, covering case of A116508, unlabeled A006649.
Binomial transform is A367916.
These set-systems have ranks A367917.
The unlabeled version is A368186.
A006129 counts covering graphs, connected A001187, unlabeled A002494.
A046165 counts minimal covers, ranks A309326.
Cf. A006126, A058891, A059201, A133686, A323816, A323817, A323818, A326754, A367862, A367901.

Join[{1}, Table[Sum[StirlingS1[n+1, k+1]*(2^k - 1)^n, {k, 0, n}]/n!, {n, 1, 15}]] (* Vaclav Kotesovec, Jun 04 2022 *)
Table[Length[Select[Subsets[Rest[Subsets[Range[n]]],{n}],Union@@#==Range[n]&]],{n,0,4}] (* Gus Wiseman, Dec 19 2023 *)

a(n) = sum(k=0, n, (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n)) \\ Andrew Howroyd, Jan 20 2024

a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*binomial(2^(n-k)-1, n).
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n+1, k+1)*(2^k-1)^n.
G.f.: Sum_{n>=0} log(1+(2^n-1)*x)^n/((1+(2^n-1)*x)*n!). - Paul D. Hanna and Vladeta Jovovic, Jan 16 2008
a(n) ~ 2^(n^2) / n!. - Vaclav Kotesovec, Jun 04 2022
Inverse binomial transform of A367916. - Gus Wiseman, Dec 19 2023

A368951 Number of connected labeled graphs with n edges and n vertices and with loops allowed.

Original entry on oeis.org

1, 1, 2, 10, 79, 847, 11436, 185944, 3533720, 76826061, 1880107840, 51139278646, 1530376944768, 49965900317755, 1767387701671424, 67325805434672100, 2747849045156064256, 119626103584870552921, 5533218319763109888000, 270982462739224265922466

Offset: 0

Andrew Howroyd, Jan 10 2024

nonn

Exponential transform appears to be A333331. - Gus Wiseman, Feb 12 2024

			From _Gus Wiseman_, Feb 12 2024: (Start)
The a(0) = 1 through a(3) = 10 loop-graphs:
  {}  {11}  {11,12}  {11,12,13}
            {22,12}  {11,12,23}
                     {11,13,23}
                     {22,12,13}
                     {22,12,23}
                     {22,13,23}
                     {33,12,13}
                     {33,12,23}
                     {33,13,23}
                     {12,13,23}
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Graph Loop.

Cf. A000169, A333331, A063170, A053506.
This is the connected covering case of A014068.
The case without loops is A057500, covering case of A370317.
Allowing any number of edges gives A062740, connected case of A322661.
This is the connected case of A368597.
The unlabeled version is A368983, connected case of A368984.
For at most n edges we have A369197.
A000085 counts set partitions into singletons or pairs.
A006129 counts covering graphs, connected A001187.
Cf. A000272, A000666, A054780, A116508, A136556, A367863, A368600.

egf:= (L-> 1-L/2-log(1+L)/2-L^2/4)(LambertW(-x)):
a:= n-> n!*coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 10 2024

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(-log(1-t)/2 + t/2 - t^2/4 + 1))}

a(n) = A000169(n) + A057500(n) for n > 0.
E.g.f.: 1 - log(1-T(x))/2 + T(x)/2 - T(x)^2/4 where T(x) = -LambertW(-x) is the e.g.f. of A000169.
From Peter Luschny, Jan 10 2024: (Start)
a(n) = (exp(n)*Gamma(n + 1, n) - (n - 1)*n^(n - 1))/(2*n) for n > 0.
a(n) = (1/2)*(A063170(n)/n - A053506(n)) for n > 0.  (End)

A327075 Number of non-connected unlabeled simple graphs covering n vertices.

Original entry on oeis.org

1, 0, 0, 0, 1, 2, 10, 35, 185, 1242, 13929, 292131, 12344252, 1032326141, 166163019475, 50671385831320, 29105332577409883, 31455744378606296280, 64032559078724993894492, 245999991257359808853560276, 1787823917424909126688749033668, 24639597815428343970034635549911427

Offset: 0

Gus Wiseman, Aug 26 2019

nonn

We consider the empty graph to be neither connected (one component) nor disconnected (more than one component).

			Non-isomorphic representatives of the a(0) = 1 through a(6) = 10 graphs (empty columns not shown):
  {}  {12,34}  {12,35,45}     {12,34,56}
               {12,34,35,45}  {12,35,46,56}
                              {12,36,46,56}
                              {13,23,46,56}
                              {12,34,35,46,56}
                              {12,36,45,46,56}
                              {13,23,45,46,56}
                              {12,13,23,45,46,56}
                              {12,35,36,45,46,56}
                              {12,34,35,36,45,46,56}

Gus Wiseman, The a(4) = 1 through a(6) = 10 non-connected covering graphs.

Column k = 0 of A327201.
The labeled version is A327070.
Disconnected graphs are A000719.
Cf. A000088, A001187, A001349, A002494, A006129, A054592.

from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A327075(n):
    if n <= 1: return 1-n
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return b(n)-b(n-1)-sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # Chai Wah Wu, Jul 03 2024

a(n) = A002494(n) - A001349(n), if we assume A001349(0) = A001349(1) = 0.

a(20)-a(21) from Chai Wah Wu, Jul 03 2024

A245883 Number of distinct chromatic polynomials among all connected graphs on n nodes.

Original entry on oeis.org

1, 1, 2, 5, 14, 50, 231, 1650, 21121, 584432

Offset: 1

Travis Hoppe and Anna Petrone, Aug 05 2014

A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic polynomial is given by chi_G(x) = Sum_p (x)k, where the sum is over all stable partitions of G, k is the length (number of blocks) of p, and (x)_k is the falling factorial x(x-1)(x-2)...(x-k+1). - _Gus Wiseman, Nov 24 2018

			From _Gus Wiseman_, Nov 24 2018: (Start)
The a(4) = 5 chromatic polynomials:
  -6x + 11x^2 - 6x^3 + x^4
  -4x +  8x^2 - 5x^3 + x^4
  -2x +  5x^2 - 4x^3 + x^4
  -3x +  6x^2 - 4x^3 + x^4
   -x +  3x^2 - 3x^3 + x^4
(End)

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Chromatic Polynomial

Cf. A229048 (simple graphs, including disconnected ones, with unique chromatic polynomials).

Cf. A001187, A001349, A006125, A125702, A229048, A240936, A245883, A277203, A321911, A322011.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
falling[x_,k_]:=Product[(x-i),{i,0,k-1}];
chromPoly[g_]:=Expand[Sum[falling[x,Length[stn]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}]];
simpleSpans[n_]:=simpleSpans[n]=If[n==0,{{}},Union@@Table[If[#=={},Union[ine,{{n}}],Union[Complement[ine,List/@#],{#,n}&/@#]]&/@Subsets[Range[n-1]],{ine,simpleSpans[n-1]}]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[chromPoly/@Select[simpleSpans[n],Length[csm[#]]==1&]]],{n,5}] (* Gus Wiseman, Nov 24 2018 *)

A317631 Number of connected set partitions of the edges of labeled graphs with n vertices.

Original entry on oeis.org

1, 1, 1, 8, 200, 15901

Offset: 0

Gus Wiseman, Aug 02 2018

In the terminology of my linked article, a(n) counts caps of connected graphs. - Gus Wiseman, Sep 06 2025

Gus Wiseman, All 200 connected set partitions of labeled graphs with 4 vertices.
Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Cf. A000110, A001187, A006125, A048143, A293510, A304717, A317632.
A317634 counts caps (also clutter partitions) of clutters covering n vertices.
A317635 counts connected vertex sets of clutters covering n vertices.
Cf. A000272, A007718, A056156, A125702, A147878, A275307, A318697, A320921.

Name modified by Gus Wiseman, Sep 06 2025

A317634 Number of caps (also clutter partitions) of clutters (connected antichains) spanning n vertices.

Original entry on oeis.org

1, 0, 1, 9, 315, 64880

Offset: 0

Gus Wiseman, Aug 02 2018

A kernel of a clutter is the restriction of the edge set to all edges contained within some connected vertex set. A clutter partition is a set partition of the edge set using kernels.

			The a(3) = 9 clutter partitions:
  {{{1,2,3}}}
  {{{1,3},{2,3}}}
  {{{1,2},{2,3}}}
  {{{1,2},{1,3}}}
  {{{1,3}},{{2,3}}}
  {{{1,2}},{{2,3}}}
  {{{1,2}},{{1,3}}}
  {{{1,2},{1,3},{2,3}}}
  {{{1,2}},{{1,3}},{{2,3}}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.
Gus Wiseman, All clutter partitions of non-isomorphic clutters on 4 vertices.

Cf. A001187, A030019, A048143, A275307, A286520,, A293510, A304717, A317631, A317632, A317635.

A321911 Number of distinct chromatic symmetric functions of simple connected graphs with n vertices.

Original entry on oeis.org

1, 1, 2, 6, 20, 103, 759

Offset: 1

Gus Wiseman, Nov 21 2018

A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions p of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895).

			The a(4) = 6 connected chromatic symmetric functions (m is the augmented monomial symmetric function basis):
                    m(1111)
           m(211) + m(1111)
          2m(211) + m(1111)
  m(22) + 2m(211) + m(1111)
  m(22) + 3m(211) + m(1111)
  m(31) + 3m(211) + m(1111)

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
Gus Wiseman, A partition of connected graphs, Electronic J. Combinatorics 12, N1 (2005), 8pp. arXiv:math/0505155 [math.CO].

First differs from A079457 at a(7) = 759, A079457(7) = 706.

Cf. A000110, A001349, A001187, A125702, A147878, A191970, A229048, A240936, A245883, A277203, A317631, A317632, A320921, A321750, A321751, A321895.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
simpleSpans[n_]:=simpleSpans[n]=If[n==0,{{}},Union@@Table[If[#=={},Union[ine,{{n}}],Union[Complement[ine,List/@#],{#,n}&/@#]]&/@Subsets[Range[n-1]],{ine,simpleSpans[n-1]}]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[chromSF/@Select[simpleSpans[n],Length[csm[#]]==1&]]],{n,6}]

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A371452 Number of connected components of the prime indices of the binary indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A053549 Number of labeled rooted connected graphs.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A054780 Number of n-covers of a labeled n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A368951 Number of connected labeled graphs with n edges and n vertices and with loops allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A327075 Number of non-connected unlabeled simple graphs covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A245883 Number of distinct chromatic polynomials among all connected graphs on n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica