A005703 -id:A005703 - cp's OEIS frontend

A369200 Number of unlabeled loop-graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

1, 1, 3, 7, 18, 43, 112, 282, 740, 1940, 5182, 13916, 37826, 103391, 284815, 788636, 2195414, 6137025, 17223354, 48495640, 136961527, 387819558, 1100757411, 3130895452, 8922294498, 25470279123, 72823983735, 208515456498, 597824919725, 1716072103910, 4931540188084

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

These are covering loop-graphs with at most one cycle (unicyclic) in each connected component.

			Representatives of the a(1) = 1 through a(4) = 18 loop-graphs (loops shown as singletons):
  {{1}}  {{1,2}}      {{1},{2,3}}          {{1,2},{3,4}}
         {{1},{2}}    {{1,2},{1,3}}        {{1},{2},{3,4}}
         {{1},{1,2}}  {{1},{2},{3}}        {{1},{1,2},{3,4}}
                      {{1},{2},{1,3}}      {{1},{2,3},{2,4}}
                      {{1},{1,2},{1,3}}    {{1},{2},{3},{4}}
                      {{1},{1,2},{2,3}}    {{1,2},{1,3},{1,4}}
                      {{1,2},{1,3},{2,3}}  {{1,2},{1,3},{2,4}}
                                           {{1},{2},{3},{1,4}}
                                           {{1},{2},{1,3},{1,4}}
                                           {{1},{2},{1,3},{2,4}}
                                           {{1},{2},{1,3},{3,4}}
                                           {{1},{1,2},{1,3},{1,4}}
                                           {{1},{1,2},{1,3},{2,4}}
                                           {{1},{1,2},{2,3},{2,4}}
                                           {{1},{1,2},{2,3},{3,4}}
                                           {{1},{2,3},{2,4},{3,4}}
                                           {{1,2},{1,3},{1,4},{2,3}}
                                           {{1,2},{1,3},{2,4},{3,4}}

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

Without the choice condition we have A322700, labeled A322661.
Without loops we have A368834, covering case of A134964.
For exactly n edges we have A368984, labeled A333331 (maybe).
The labeled version is A369140, covering case of A368927.
The labeled complement is A369142, covering case of A369141.
This is the covering case of A369145.
The complement is counted by A369147, covering case of A369146.
The complement without loops is A369202, covering case of A140637.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, labeled A006125 (shifted left).
A006129 counts covering graphs, unlabeled A002494.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A129271 counts connected choosable simple graphs, unlabeled A005703.
A133686 counts choosable labeled graphs, covering A367869.
Cf. A000088, A000612, A006649, A014068, A055621, A137916, A137917, A368835, A369194, A369199.

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],{1,2}]], Union@@#==Range[n]&&Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]]],{n,0,4}]

First differences of A369145.

Euler transform of A369289 with A369289(1) = 1. - Andrew Howroyd, Feb 02 2024

a(7) onwards from Andrew Howroyd, Feb 02 2024

A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 7, 30, 124, 507, 2036, 8216, 33515, 138557, 583040, 2503093, 10985364, 49361893, 227342301, 1073896332, 5204340846, 25874724616, 131937166616, 689653979583, 3693193801069, 20247844510508, 113564665880028, 651138092719098, 3813739129140469

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

These are graphs with n vertices and n edges having at least two cycles in the same component.

			The a(0) = 0 through a(6) = 7 simple graphs:
  .  .  .  .  .  {{12}{13}{14}{23}{24}}  {{12}{13}{14}{15}{23}{24}}
                                         {{12}{13}{14}{15}{23}{45}}
                                         {{12}{13}{14}{23}{24}{34}}
                                         {{12}{13}{14}{23}{24}{35}}
                                         {{12}{13}{14}{23}{24}{56}}
                                         {{12}{13}{14}{23}{25}{45}}
                                         {{12}{13}{14}{25}{35}{45}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(6) = 7 unlabeled non-choosable graphs with 6 vertices and 6 edges.

Without the choice condition we have A001434, covering A006649.
The labeled version without choice is A116508, covering A367863, A367862.
The complement is counted by A137917, labeled A137916.
For any number of edges we have A140637, complement A134964.
For labeled set-systems we have A368600.
The case with loops is A368835, labeled A368596.
The labeled version is A369143, covering A369144.
A006129 counts covering graphs, unlabeled A002494.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable simple graphs, unlabeled A005703.
Cf. A000088, A000612, A014068, A053530, A133686, A140638, A368601, A369141, A369146.

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

a(n) = A001434(n) - A137917(n).

a(25) onwards from Andrew Howroyd, Feb 02 2024

A370168 Number of unlabeled loop-graphs with n vertices and at most n edges.

Original entry on oeis.org

1, 2, 5, 13, 36, 102, 313, 994, 3318, 11536, 41748, 156735, 609973, 2456235, 10224216, 43946245, 194866898, 890575047, 4190997666, 20289434813, 100952490046, 515758568587, 2703023502100, 14518677321040, 79852871813827, 449333028779385, 2584677513933282

Offset: 0

Gus Wiseman, Feb 16 2024

nonn

			The a(0) = 1 through a(3) = 13 loop-graph edge sets (loops shown as singletons):
  {}  {}     {}           {}
      {{1}}  {{1}}        {{1}}
             {{1,2}}      {{1,2}}
             {{1},{2}}    {{1},{2}}
             {{1},{1,2}}  {{1},{1,2}}
                          {{1},{2,3}}
                          {{1,2},{1,3}}
                          {{1},{2},{3}}
                          {{1},{2},{1,2}}
                          {{1},{2},{1,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{1,2},{1,3},{2,3}}

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

The labeled version is A066383, covering A369194.
The case of equality is A368598, covering A368599.
The covering case is A370169, labeled A369194.
The loopless version is A370315, labeled A369192.
The covering loopless version is A370316, labeled A369191.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A000666, A005703, A014068, A062740, A368597, A368927, A369141, A369196, A369197, A369199.

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], {1,2}]],Length[#]<=n&]]],{n,0,5}]

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

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

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

Original entry on oeis.org

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

Gus Wiseman, Feb 18 2024

nonn

			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}

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

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.

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}]

\\ 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

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

A387118 Number of integer partitions of n without choosable initial intervals.

Original entry on oeis.org

0, 0, 1, 1, 2, 4, 6, 8, 13, 19, 28, 37, 52, 70, 97, 130, 172, 224, 293, 378, 492, 630, 806, 1018, 1286, 1609, 2019, 2514, 3131, 3874, 4784, 5872, 7198, 8786, 10712, 13013, 15794, 19100, 23063, 27752, 33341, 39939, 47781, 57013, 67955, 80816, 95992, 113773, 134668

Offset: 0

Gus Wiseman, Sep 02 2025

The initial interval of a nonnegative integer x is the set {1,...,x}.

We say that a sequence of nonempty sets is choosable iff it is possible to choose a different element from each set. For example, ({1,2},{1},{1,3}) is choosable because we have the choice (2,1,3), but ({1},{2},{1,3},{2,3}) is not.

			The partition y = (2,2,1) has initial intervals ({1,2},{1,2},{1}), which are not choosable, so y is counted under a(5).
The a(2) = 1 through a(8) = 13 partitions:
  (11)  (111)  (211)   (221)    (222)     (511)      (611)
               (1111)  (311)    (411)     (2221)     (2222)
                       (2111)   (2211)    (3211)     (3221)
                       (11111)  (3111)    (4111)     (3311)
                                (21111)   (22111)    (4211)
                                (111111)  (31111)    (5111)
                                          (211111)   (22211)
                                          (1111111)  (32111)
                                                     (41111)
                                                     (221111)
                                                     (311111)
                                                     (2111111)
                                                     (11111111)

The complement is counted by A238873, ranks A387112.
The complement for divisors is A239312, ranks A368110.
For divisors instead of initial intervals we have A370320, ranks A355740.
The complement for prime factors is A370592, ranks A368100.
For prime factors instead of initial intervals we have A370593, ranks A355529.
These partitions have ranks A387113.
For partitions instead of initial intervals we have A387134.
The complement for partitions is A387328.
For strict partitions instead of initial intervals we have A387137, ranks A387176.
The complement for strict partitions is A387178.
A000005 counts divisors.
A000041 counts integer partitions, strict A000009.
A367902 counts choosable set-systems, complement A367903.
A370582 counts sets with choosable prime factors, complement A370583.
Cf. A005703, A052335, A367867, A367901, A367905, A367907, A370585, A370594, A387111.

Table[Length[Select[IntegerPartitions[n],Select[Tuples[Range/@#],UnsameQ@@#&]=={}&]],{n,0,10}]

More terms from Jinyuan Wang, Sep 05 2025

A387137 Number of integer partitions of n whose parts do not have choosable sets of strict integer partitions.

Original entry on oeis.org

0, 0, 1, 1, 3, 4, 6, 9, 14, 20, 29, 39, 56, 74, 101, 134, 178, 232, 305, 392, 508, 646, 825, 1042, 1317, 1649, 2066, 2567, 3190, 3937, 4859, 5960, 7306, 8914, 10863, 13183, 15984, 19304, 23288, 28003, 33631, 40272, 48166, 57453, 68448, 81352, 96568, 114383

Offset: 0

Gus Wiseman, Sep 02 2025

We say that a sequence of nonempty sets is choosable iff it is possible to choose a different element from each set. For example, ({1,2},{1},{1,3}) is choosable because we have the choice (2,1,3), but ({1},{2},{1,3},{2,3}) is not.
a(n) is the number of integer partitions of n such that it is not possible to choose a sequence of distinct strict integer partitions, one of each part.
Also the number of integer partitions of n with at least one part k whose multiplicity exceeds A000009(k).

			The a(2) = 1 through a(8) = 14 partitions:
  (11)  (111)  (22)    (221)    (222)     (322)      (422)
               (211)   (311)    (411)     (511)      (611)
               (1111)  (2111)   (2211)    (2221)     (2222)
                       (11111)  (3111)    (3211)     (3221)
                                (21111)   (4111)     (3311)
                                (111111)  (22111)    (4211)
                                          (31111)    (5111)
                                          (211111)   (22211)
                                          (1111111)  (32111)
                                                     (41111)
                                                     (221111)
                                                     (311111)
                                                     (2111111)
                                                     (11111111)

The complement for initial intervals is A238873, ranks A387112.
The complement for divisors is A239312, ranks A368110.
Twice-partitions of this type (into distinct strict partitions) are counted by A358914.
For divisors instead of strict partitions we have A370320, ranks A355740.
The complement for prime factors is A370592, ranks A368100.
For prime factors instead of strict partitions we have A370593, ranks A355529.
For initial intervals instead of strict partitions we have A387118, ranks A387113.
For all partitions instead of strict partitions we have A387134, ranks A387577.
These partitions are ranked by A387176.
The complement is counted by A387178, ranks A387177.
The complement for partitions is A387328, ranks A387576.
The version for constant partitions is A387329, ranks A387180.
The complement for constant partitions is A387330, ranks A387181.
A000005 counts divisors.
A000041 counts integer partitions, strict A000009.
A367902 counts choosable set-systems, complement A367903.
Cf. A005703, A052335, A261049, A270995, A276078, A335448, A355535, A367867, A367901, A367905, A383706, A387115.

strptns[n_]:=Select[IntegerPartitions[n],UnsameQ@@#&];
Table[Length[Select[IntegerPartitions[n],Length[Select[Tuples[strptns/@#],UnsameQ@@#&]]==0&]],{n,0,15}]

A000368 Number of connected graphs with one cycle of length 4.

Original entry on oeis.org

1, 1, 4, 9, 28, 71, 202, 542, 1507, 4114, 11381, 31349, 86845, 240567, 668553, 1860361, 5188767, 14495502, 40572216, 113743293, 319405695, 898288484, 2530058013, 7135848125, 20152898513, 56986883801

Offset: 4

N. J. A. Sloane

nonn

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, page 69.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 4..2000 (terms 4..43 from Sean A. Irvine, 44..200 from Washington Bomfim)
Washington Bomfim, Illustration of initial terms

Column k=4 of A217781.
Cf. A000081, A000226, A001429, A005703.
Second diagonal of A058879.

Needs["Combinatorica`"]; nn = 30; s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2 k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n - 1, i] i, {i, 1, n - 1}]/(n - 1); rt = Table[a[i], {i, 1, nn}]; Take[CoefficientList[CycleIndex[DihedralGroup[4], s] /. Table[s[j] -> Table[Sum[rt[[i]] x^(k*i), {i, 1, nn}], {k, 1, nn}][[j]], {j, 1, nn}], x], {5, nn}]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
A000081 = Rest[Cases[ Import["https://oeis.org/A000081/b000081.txt", "Table"], {, }][[All, 2]]]; max = 30; g81 = Sum[A000081[[k]]*x^k, {k, 1, max}]; g81x2 = Sum[A000081[[k]]*x^(2 k), {k, 1, max}]; g81x4 = Sum[A000081[[k]]*x^(4 k), {k, 1, max}]; Drop[CoefficientList[ Series[(2*g81x4 + 3*g81x2^2 + 2*g81^2*g81x2 + g81^4)/8, {x, 0, max}], x], 4] (* Vaclav Kotesovec, Dec 25 2020 *)

g(Q)={my(V=Vec(Q),D=Set(V),d=#D); if(d==4,return(3*f[D[1]]*f[D[2]]*f[D[3]]*f[D[4]]));
if(d==1, return((f[D[1]]^4+2*f[D[1]]^3+3*f[D[1]]^2+2*f[D[1]])/8));
my(k=1, m = #select(x->x == D[k],V), t); while(m==1, k++; m = #select(x->x == D[k], V)); t = D[1]; D[1] = D[k]; D[k] = t;
if(d == 3, return( f[D[1]] * f[D[2]] * f[D[3]] * (3 * f[D[1]] + 1)/2 ) );
if(m==3, return(f[D[1]]^2 * f[D[2]] * (f[D[1]] + 1)/2));
((3*f[D[2]]^2 + f[D[2]])*f[D[1]]^2 + (f[D[2]]^2 + 3*f[D[2]])*f[D[1]])/4 };
seq(max_n) = { my(s, a = vector(max_n), U); f = vector(max_n); f[1] = 1;
for(j=1, max_n - 1, if(j%100==0,print(j)); f[j+1] = 1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1]));
for(n=4, max_n, s=0; forpart(Q = n, if( (Q[4] > Q[3]) && (Q[3]-1 > Q[2]),
      U = U / (f[Q[4] + 1] * f[Q[3] - 1]) * f[Q[4]] * f[Q[3]],  U = g(Q)); s += U,
[1,n],[4,4]); a[n] = s; if(n % 100 == 0, print(n": " s))); a[4..max_n] };
\\ Washington Bomfim, Jul 19 2012 and Dec 22 2020

From Washington Bomfim, Jul 19 2012 and Dec 22 2020: (Start)
a(n) = Sum_{P}( g(Q) ), where P is the set of the partitions Q of n with 4 parts, Q with distinct parts D[1]..D[d], D[1] the part of maximum multiplicity m in Q, f(n) = A000081(n), and g(Q) given by,
       | 3 * f(D[1]) * f(D[2]) * f(D[3]) * f(D[4]),              if d = 4,
       | (f(D[1])^4 + 2*f(D[1])^3 + 3*f(D[1])^2 + 2*f(D[1]))/8,  if d = 1,
g(Q) = | f(D[1]) * f(D[2]) * f(D[3]) * (3 * f(D[1]) + 1)/2,      if d = 3,
       | ((3*f(D[2])^2+f(D[2]))*f(D[1])^2+(f(D[2])^2+3*f(D[2]))*f(D[1]))/4,
       |                                                   if d=2, and m=2,
       | f(D[1])^2 * f(D[2]) * (f(D[1]) + 1)/2,            if d=2, and m=3.
(End)
G.f.: (2*t(x^4) + 3*t(x^2)^2 + 2*t(x)^2*t(x^2) + t(x)^4)/8 where t(x) is the g.f. of A000081. - Andrew Howroyd, Dec 03 2020
a(n) ~ (A187770 + A339986) * A051491^n / (2 * n^(3/2)). - Vaclav Kotesovec, Dec 25 2020

More terms from Vladeta Jovovic, Apr 20 2000
Definition improved by Franklin T. Adams-Watters, May 16 2006
More terms from Sean A. Irvine, Nov 14 2010

A369202 Number of unlabeled simple graphs covering n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 0, 0, 2, 13, 95, 826, 11137, 261899, 11729360, 1006989636, 164072166301, 50336940172142, 29003653625802754, 31397431814146891910, 63969589218557753075156, 245871863137828405124380563, 1787331789281458167615190373076, 24636021675399858912682459601585276

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

These are simple graphs covering n vertices such that some connected component has at least two cycles.

			Representatives of the a(4) = 2 and a(5) = 13 simple graphs:
  {12}{13}{14}{23}{24}      {12}{13}{14}{15}{23}{24}
  {12}{13}{14}{23}{24}{34}  {12}{13}{14}{15}{23}{45}
                            {12}{13}{14}{23}{24}{35}
                            {12}{13}{14}{23}{25}{45}
                            {12}{13}{14}{25}{35}{45}
                            {12}{13}{14}{15}{23}{24}{25}
                            {12}{13}{14}{15}{23}{24}{34}
                            {12}{13}{14}{15}{23}{24}{35}
                            {12}{13}{14}{23}{24}{35}{45}
                            {12}{13}{14}{15}{23}{24}{25}{34}
                            {12}{13}{14}{15}{23}{24}{35}{45}
                            {12}{13}{14}{15}{23}{24}{25}{34}{35}
                            {12}{13}{14}{15}{23}{24}{25}{34}{35}{45}

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

Without the choice condition we have A002494, labeled A006129.
The connected case is A140636.
This is the covering case of A140637, complement A134964.
The labeled version is A367868, complement A367869.
The complement is counted by A368834.
The version with loops is A369147, complement A369200.
A005703 counts unlabeled connected choosable simple graphs, labeled A129271.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A283877 counts unlabeled set-systems, connected A300913.
Cf. A000088, A000612, A006649, A001434, A055621, A137916, A137917, A140638, A368596, A369141, A369146.

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

First differences of A140637.

a(n) = A002494(n) - A368834(n).

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

Original entry on oeis.org

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

Gus Wiseman, Feb 18 2024

nonn

			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}

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

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.

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}]

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

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

A387112 Numbers with (strictly) choosable initial intervals of prime indices.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 45, 46, 47, 49, 50, 51, 53, 55, 57, 58, 59, 61, 62, 63, 65, 66, 67, 69, 70, 71, 73, 74, 75, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95

Offset: 1

Gus Wiseman, Aug 23 2025

First differs from A371088 in having a(86) = 121.
The initial interval of a nonnegative integer x is the set {1,...,x}.
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.
We say that a set or sequence of nonempty sets is choosable iff it is possible to choose a different element from each set. For example, ({1,2},{1},{1,3}) is choosable because we have the choice (2,1,3), but ({1,2,3},{1},{1,3},{2}) is not.
This sequence lists all numbers k such that if the prime indices of k are (x1,x2,...,xz), then the sequence of sets (initial intervals) ({1,...,x1},{1,...,x2},...,{1,...,xz}) is choosable.

			The prime indices of 85 are {3,7}, with initial intervals {{1,2,3},{1,2,3,4,5,6,7}}, which are choosable, so 85 is in the sequence
The prime indices of 90 are {1,2,2,3}, with initial intervals {{1},{1,2},{1,2},{1,2,3}}, which are not choosable, so 90 is not in the sequence.

Partitions of this type are counted by A238873, complement A387118.
For partitions instead of initial intervals we have A276078, complement A276079.
For prime factors instead of initial intervals we have A368100, complement A355529.
For divisors instead of initial intervals we have A368110, complement A355740.
These are all the positions of nonzero terms in A387111, complement A387134.
The complement is A387113.
For strict partitions instead of initial intervals we have A387176, complement A387137.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, row sums A056239 or A066328, lengths A001222.
A120383 lists numbers divisible by all of their prime indices.
A367902 counts choosable set-systems, complement A367903.
A370582 counts sets with choosable prime factors, complement A370583.
A370585 counts maximal subsets with choosable prime factors.
Cf. A003963, A005703, A052335, A239312, A335433, A335448, A355739, A387110, A383706.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Select[Tuples[Range/@prix[#]],UnsameQ@@#&]!={}&]

cp's OEIS Frontend

A369200 Number of unlabeled loop-graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A370168 Number of unlabeled loop-graphs with n vertices and at most n edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A387118 Number of integer partitions of n without choosable initial intervals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A387137 Number of integer partitions of n whose parts do not have choosable sets of strict integer partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A000368 Number of connected graphs with one cycle of length 4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A369202 Number of unlabeled simple graphs covering n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

Views