A133686 -id:A133686 - cp's OEIS frontend

A367868 Number of labeled simple graphs covering n vertices and contradicting a strict version of the axiom of choice.

0, 0, 0, 0, 7, 381, 21853, 1790135, 250562543, 66331467215, 34507857686001, 35645472109753873, 73356936892660012513, 301275024409580265134121, 2471655539736293803311467943, 40527712706903494712385171632959, 1328579255614092966328511889576785109

Offset: 0

Gus Wiseman, Dec 08 2023

nonn

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The a(4) = 7 graphs:
  {{1,2},{1,3},{1,4},{2,3},{2,4}}
  {{1,2},{1,3},{1,4},{2,3},{3,4}}
  {{1,2},{1,3},{1,4},{2,4},{3,4}}
  {{1,2},{1,3},{2,3},{2,4},{3,4}}
  {{1,2},{1,4},{2,3},{2,4},{3,4}}
  {{1,3},{1,4},{2,3},{2,4},{3,4}}
  {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

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

The connected case is A140638, unlabeled A140636.
The non-covering case is A367867.
The complement is A367869, connected A129271, non-covering A133686.
The version for set-systems is A367903, ranks A367907.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A143543 counts simple labeled graphs by number of connected components.
Cf. A057500, A116508, A367769, A367770, A367863, A367901, A367902, A367904.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Select[Tuples[#], UnsameQ@@#&]=={}&]],{n,0,5}]

a(n) = A006129(n) - A367869(n). - Andrew Howroyd, Dec 30 2023

Terms a(7) and beyond from Andrew Howroyd, Dec 30 2023

A368413 Number of factorizations of n into positive integers > 1 such that it is not possible to choose a different prime factor of each factor.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 4, 0, 1, 0, 1, 0, 0, 0, 3, 1, 0, 2, 1, 0, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0, 3, 0, 0, 0, 1, 1, 0, 0, 7, 1, 1, 0, 1, 0, 3, 0, 3, 0, 0, 0, 2, 0, 0, 1, 10, 0, 0, 0, 1, 0, 0, 0, 10, 0, 0, 1, 1, 0, 0, 0, 7, 4, 0, 0, 2, 0, 0

Offset: 1

Gus Wiseman, Dec 27 2023

nonn

For example, the factorization f = 2*3*6 has two ways to choose a prime factor of each factor, namely (2,3,2) and (2,3,3), but neither of these has all different elements, so f is counted under a(36).

			The a(1) = 0 through a(24) = 3 factorizations:
 ... 2*2 ... 2*4   3*3 .. 2*2*3 ... 2*8     . 2*3*3 . 2*2*5 ... 2*2*6
             2*2*2                  4*4                         2*3*4
                                    2*2*4                       2*2*2*3
                                    2*2*2*2

For unlabeled graphs: A140637, complement A134964.
For labeled graphs: A367867, A367868, A140638, complement A133686.
For set-systems: A367903, ranks A367907, complement A367902, ranks A367906.
For non-isomorphic set-systems: A368094, A368409, complement A368095.
For non-isomorphic multiset partitions: A368097, A355529, A368411.
Complement for non-isomorphic multiset partitions: A368098, A368100.
The complement is counted by A368414.
For non-isomorphic set multipartitions: A368421, complement A368422.
For divisors instead of prime factors: A370813, complement A370814.
A001055 counts factorizations, strict A045778.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A340596, A340653, A367769, A367901, A368187, A368412.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&, Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]=={}&]],{n,100}]

a(n) + A368414(n) = A001055(n).

A368097 Number of non-isomorphic multiset partitions of weight n contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 1, 3, 12, 37, 133, 433, 1516, 5209, 18555

Offset: 0

Gus Wiseman, Dec 25 2023

A multiset partition is a finite multiset of finite nonempty multisets. The weight of a multiset partition is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			Non-isomorphic representatives of the a(2) = 1 through a(4) = 12 multiset partitions:
  {{1},{1}}  {{1},{1,1}}    {{1},{1,1,1}}
             {{1},{1},{1}}  {{1,1},{1,1}}
             {{1},{2},{2}}  {{1},{1},{1,1}}
                            {{1},{1},{2,2}}
                            {{1},{1},{2,3}}
                            {{1},{2},{1,2}}
                            {{1},{2},{2,2}}
                            {{2},{2},{1,2}}
                            {{1},{1},{1},{1}}
                            {{1},{1},{2},{2}}
                            {{1},{2},{2},{2}}
                            {{1},{2},{3},{3}}

Wikipedia, Axiom of choice.

The case of unlabeled graphs appears to be A140637, complement A134964.
These multiset partitions have ranks A355529.
The case of labeled graphs is A367867, complement A133686.
Set-systems not of this type are A367902, ranks A367906.
Set-systems of this type are A367903, ranks A367907.
For set-systems we have A368094, complement A368095.
The complement is A368098, ranks A368100, connected case A368412.
Minimal multiset partitions of this type are ranked by A368187.
The connected case is A368411.
Factorizations of this type are counted by A368413, complement A368414.
For set multipartitions we have A368421, complement A368422.
A000110 counts set partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A302545, A316983, A317533, A319616, A321405, A367905, A368409, A368410.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]] /@ Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
Table[Length[Union[brute/@Select[mpm[n], Select[Tuples[#],UnsameQ@@#&]=={}&]]], {n,0,6}]

A370592 Number of integer partitions of n such that it is possible to choose a different prime factor of each part.

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 1, 3, 3, 4, 4, 5, 6, 7, 9, 11, 12, 12, 16, 18, 22, 26, 29, 29, 37, 41, 49, 55, 61, 68, 72, 88, 98, 110, 120, 135, 146, 166, 190, 209, 227, 252, 277, 309, 346, 379, 413, 447, 500, 548, 606, 665, 727, 785, 857, 949, 1033, 1132, 1228, 1328, 1440

Offset: 0

Gus Wiseman, Feb 29 2024

nonn

			The partition (10,6,4) has choice (5,3,2) so is counted under a(20).
The a(0) = 1 through a(10) = 4 partitions:
  ()  .  (2)  (3)  (4)  (5)    (6)  (7)    (8)    (9)    (10)
                        (3,2)       (4,3)  (5,3)  (5,4)  (6,4)
                                    (5,2)  (6,2)  (6,3)  (7,3)
                                                  (7,2)  (5,3,2)
The a(0) = 1 through a(17) = 12 partitions (0 = {}, A..H = 10..17):
  0  .  2  3  4  5   6  7   8   9   A    B   C    D    E    F    G    H
                 32     43  53  54  64   65  66   76   86   87   97   98
                        52  62  63  73   74  75   85   95   96   A6   A7
                                72  532  83  A2   94   A4   A5   B5   B6
                                         92  543  A3   B3   B4   C4   C5
                                             732  B2   C2   C3   D3   D4
                                                  652  653  D2   E2   E3
                                                       743  654  754  F2
                                                       752  753  763  665
                                                            762  853  764
                                                            A32  952  A43
                                                                 B32  7532

The version for divisors instead of factors is A239312, ranks A368110.
The version for set-systems is A367902, ranks A367906, unlabeled A368095.
The complement for set-systems is A367903, ranks A367907, unlabeled A368094.
For unlabeled multiset partitions we have A368098, complement A368097.
These partitions have ranks A368100.
The version for factorizations is A368414, complement A368413.
The complement is counted by A370593, ranks A355529.
For a unique choice we have A370594, ranks A370647.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, A112798 indices, length A001222.
A355741 counts choices of a prime factor of each prime index.
Cf. A000040, A000720, A133686, A355739, A355740, A355745, A367771, A367905, A370585, A370586, A370636.

Table[Length[Select[IntegerPartitions[n], Length[Select[Tuples[If[#==1, {},First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]>0&]],{n,0,30}]

a(n) = A000041(n) - A370593(n).

A140637 Number of unlabeled graphs of positive excess with n nodes.

Original entry on oeis.org

0, 0, 0, 2, 15, 110, 936, 12073, 273972, 12003332, 1018992968, 165091159269, 50502031331411, 29054155657134165, 31426485969804026075, 64001015704527557101231, 245935864153532932681481794, 1787577725145611700547871854870, 24637809253125004524383007473440146

Offset: 1

Washington Bomfim, May 21 2008

nonn

We can find in "The Birth of the Giant Component" p. 53, see the link, the following: "The excess of a graph or multigraph is the number of edges plus the number of acyclic components, minus the number of vertices."
If G has just one complex component with 4 nodes, the "non-complex part" of G can be,
a) One forest of order 4. There are 6 forests, so 2*6=12 graphs.
b) One triangle and one isolated vertex, or 2*1=2 graphs.
c) One unicyclic graph of order 4, so 2*2=4 graphs.
Also the number of unchoosable unlabeled graphs with up to n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The labeled version is A367867, covering A367868, connected A140638. - Gus Wiseman, Feb 13 2024

			Below we show that a(8) = 12073. Note that A140636(n) is the number of connected graphs of positive excess with n nodes.
Let G be a disconnected graph of positive excess with 8 nodes. In this case, G has one or two complex components. We have 3 graphs of order 8 with two complex components. One of those graphs is depicted in the figure below:
  O---O...O---O
  |\..|...|\./|
  |.\.|...|.X.|
  |..\|...|/.\|
  O---O...O---O
If G has one complex component with 5 nodes, the non-complex part of G can be,
a) One forest of order 3. There are 3 forests, so A140636(5) * 3 = 39 graphs.
b) One triangle, so A140636(5) = 13 graphs.
If G has one complex component with 6 nodes, the non-complex part of G is a forest of order 2. There are 2 forests. We have A140636(6) * 2, or 186 graphs.
If G has one complex component with 7 nodes, the non-complex part of G is one isolated vertex. We have A140636(7), or 809 graphs.
Finally if G is connected, we have A140636(8), or 11005 graphs.
The total is 3 + 12 + 2 + 4 + 39 + 13 + 186 + 809 + 11005 = 12073.

Svante Janson, Donald E. Knuth, Tomasz Łuczak and Boris Pittel, The Birth of the Giant Component.

Cf. A000088, A005195, A001429.
The labeled complement is A133686, covering A367869, connected A129271.
The complement is A134964, connected A005703.
The connected covering case is A140636.
The labeled version is A367867, covering A367868, connected A140638.
Set-systems not of this type are A367902, ranks A367906.
Set-systems of this type are A367903, ranks A367907.
For set-systems we have A368094, complement A368095.
For multiset partitions we have A368097, complement A368098.
Factorizations of this type are A368413, complement A368414.
Cf. A001349, A002494, A006125, A055621, A367769, A367770, A367901.

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}]],Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,5}] (* Gus Wiseman, Feb 14 2024 *)

a(n) = A000088(n) - A134964(n).

A368414 Number of factorizations of n into positive integers > 1 such that it is possible to choose a different prime factor of each factor.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 1, 2, 2, 2, 5, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 1, 2, 5, 1, 3, 2, 5, 1, 6, 1, 2, 3, 3, 2, 5, 1, 5, 1, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Dec 29 2023

nonn

For example, the factorization f = 2*3*6 has two ways to choose a prime factor of each factor, namely (2,3,2) and (2,3,3), but neither of these has all different elements, so f is not counted under a(36).

			The a(n) factorizations for selected n:
  1    6      12     24      30       60        72      120
       2*3    2*6    2*12    2*15     2*30      2*36    2*60
              3*4    3*8     3*10     3*20      3*24    3*40
                     4*6     5*6      4*15      4*18    4*30
                             2*3*5    5*12      6*12    5*24
                                      6*10      8*9     6*20
                                      2*3*10            8*15
                                      2*5*6             10*12
                                      3*4*5             2*3*20
                                                        2*5*12
                                                        2*6*10
                                                        3*4*10
                                                        3*5*8
                                                        4*5*6

For labeled graphs: A133686, complement A367867, A367868, A140638.
For unlabeled graphs: A134964, complement A140637.
For set-systems: A367902, ranks A367906, complement A367903, ranks A367907.
For non-isomorphic set-systems: A368095, complement A368094, A368409.
Complementary non-isomorphic multiset partitions: A368097, A355529, A368411.
For non-isomorphic multiset partitions: A368098, A368100.
The complement is counted by A368413.
For non-isomorphic set multipartitions: A368422, complement A368421.
For divisors instead of prime factors: A370813, complement A370814.
A001055 counts factorizations, strict A045778.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A340596, A340653, A367769, A367901, A368187, A368412, A368413.

facs[n_]:=If[n<=1,{{}},Join @@ Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]], {d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]!={}&]],{n,100}]

a(n) = A001055(n) - A368413(n).

A137916 Number of n-node labeled graphs whose components are unicyclic graphs.

Original entry on oeis.org

1, 0, 0, 1, 15, 222, 3670, 68820, 1456875, 34506640, 906073524, 26154657270, 823808845585, 28129686128940, 1035350305641990, 40871383866109888, 1722832666898627865, 77242791668604946560, 3670690919234354407000, 184312149879830557190940, 9751080154504005703189791

Offset: 0

Washington Bomfim, Feb 22 2008

Also the number of labeled simple graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. The version without the choice condition is A116508, covering A367863. - Gus Wiseman, Jan 25 2024

			a(6) = 3670 because A057500(6) = 3660 and two triangles can be labeled in 10 ways.
From _Gus Wiseman_, Jan 25 2024: (Start)
The a(0) = 1 through a(4) = 15 simple graphs:
  {}  .  .  {12,13,23}  {12,13,14,23}
                        {12,13,14,24}
                        {12,13,14,34}
                        {12,13,23,24}
                        {12,13,23,34}
                        {12,13,24,34}
                        {12,14,23,24}
                        {12,14,23,34}
                        {12,14,24,34}
                        {12,23,24,34}
                        {13,14,23,24}
                        {13,14,23,34}
                        {13,14,24,34}
                        {13,23,24,34}
                        {14,23,24,34}
(End)

V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999.

Alois P. Heinz, Table of n, a(n) for n = 0..386 (terms n = 151..200 from Andrew Howroyd)
Eric Weisstein's World of Mathematics, Pseudoforest.
Wikipedia, Pseudoforest.

The connected case is A057500.
Row sums of A106239.
The unlabeled version is A137917.
Diagonal of A144228.
The version with loops appears to be A333331, unlabeled A368984.
Column k = 0 of A368924.
The complement is counted by A369143, unlabeled A369201, covering A369144.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable simple graphs, covering A367869.
A140637 counts unlabeled non-choosable graphs, covering A369202.
A367867 counts non-choosable graphs, covering A367868.
Cf. A001434, A006649, A053530, A116508, A129271, A134964, A140638, A367862, A367863, A369191.

cy:= proc(n) option remember;
       binomial(n-1, 2)*add((n-3)!/(n-2-t)!*n^(n-2-t), t=1..n-2)
     end:
T:= proc(n,k) option remember; `if`(k=0, 1, `if`(k<0 or n T(n,n):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 15 2008

nn = 20; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; Drop[Range[0, nn]! CoefficientList[Series[Exp[Log[1/(1 - t)]/2 - t/2 - t^2/4], {x, 0, nn}], x], 1] (* Geoffrey Critzer, Jan 24 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}] (* Gus Wiseman, Jan 25 2024 *)

A057500(p) = (p-1)! * p^p /2 * sum(k = 3,p, 1/(p^k*(p-k)!)); /* Vladeta Jovovic, A057500. */
F(n,N) = { my(s = 0, K, D, Mc); forpart(P = n, D = Set(P); K = vector(#D);
for(i=1, #D, K[i] = #select(x->x == D[i], Vec(P)));
Mc = n!/prod(i=1,#D, K[i]!);
s += Mc * prod(i = 1, #D, A057500(D[i])^K[i] / ( D[i]!^K[i])) , [3, n], [N, N]); s };
a(n)= {my(N); sum(N = 1, n, F(n,N))};

seq(n)={my(w=lambertw(-x+O(x*x^n))); Vec(serlaplace(exp(-log(1+w)/2 + w/2 - w^2/4)))} \\ Andrew Howroyd, May 18 2021

a(n) = Sum_{N = 1..n} ((n!/N!) * Sum_{n_1 + n_2 + ... + n_N = n} Product_{i = 1..N} ( A057500(n_i) / n_i! ) ). [V. F. Kolchin p. 31, (1.4.2)] replacing numerator terms n_i^(n_i-2) by A057500(n_i).
a(n) = A144228(n,n). - Alois P. Heinz, Sep 15 2008
E.g.f.: exp(B(T(x))) where B(x) = (log(1/(1-x))-x-x^2/2)/2 and T(x) is the e.g.f. for A000169 (labeled rooted trees). - Geoffrey Critzer, Jan 24 2012
a(n) ~ 2^(-1/4)*exp(-3/4)*GAMMA(3/4)*n^(n-1/4)/sqrt(Pi) * (1-7*Pi/(12*GAMMA(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Aug 16 2013
E.g.f.: exp(B(x)) where B(x) is the e.g.f. of A057500. - Andrew Howroyd, May 18 2021

a(0)=1 prepended by Andrew Howroyd, May 18 2021

A368094 Number of non-isomorphic set-systems of weight n contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 5, 12, 36, 97, 291

Offset: 0

Gus Wiseman, Dec 23 2023

A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			Non-isomorphic representatives of the a(5) = 1 through a(7) = 12 set-systems:
  {{1},{2},{3},{2,3}}  {{1},{2},{1,3},{2,3}}    {{1},{2},{1,2},{3,4,5}}
                       {{1},{2},{3},{1,2,3}}    {{1},{3},{2,3},{1,2,3}}
                       {{2},{3},{1,3},{2,3}}    {{1},{4},{1,4},{2,3,4}}
                       {{3},{4},{1,2},{3,4}}    {{2},{3},{2,3},{1,2,3}}
                       {{1},{2},{3},{4},{3,4}}  {{3},{1,2},{1,3},{2,3}}
                                                {{1},{2},{3},{1,3},{2,3}}
                                                {{1},{2},{3},{2,4},{3,4}}
                                                {{1},{2},{3},{4},{2,3,4}}
                                                {{1},{3},{4},{2,4},{3,4}}
                                                {{1},{4},{5},{2,3},{4,5}}
                                                {{2},{3},{4},{1,2},{3,4}}
                                                {{1},{2},{3},{4},{5},{4,5}}

Wikipedia, Axiom of choice.

The case of unlabeled graphs is A140637, complement A134964.
The case of labeled graphs is A367867, complement A133686.
The labeled version is A367903, ranks A367907.
The complement is counted by A368095, connected A368410.
Repeats allowed: A368097, ranks A355529, complement A368098, ranks A368100.
Minimal multiset partitions of this type are ranked by A368187.
The connected case is A368409.
Factorizations of this type are counted by A368413, complement A368414.
Allowing repeated edges gives A368421, complement A368422.
A000110 counts set partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A302545, A306005, A316983, A317533, A319616, A321155, A321405, A326031, A330223, A330227, A367905.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]] /@ Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
Table[Length[Union[brute/@Select[mpm[n], UnsameQ@@#&&And@@UnsameQ@@@# && Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,8}]

A370593 Number of integer partitions of n such that it is not possible to choose a different prime factor of each part.

Original entry on oeis.org

0, 1, 1, 2, 4, 5, 10, 12, 19, 26, 38, 51, 71, 94, 126, 165, 219, 285, 369, 472, 605, 766, 973, 1226, 1538, 1917, 2387, 2955, 3657, 4497, 5532, 6754, 8251, 10033, 12190, 14748, 17831, 21471, 25825, 30976, 37111, 44331, 52897, 62952, 74829, 88755, 105145, 124307

Offset: 0

Gus Wiseman, Feb 29 2024

nonn

			The a(0) = 0 through a(7) = 12 partitions:
  .  (1)  (11)  (21)   (22)    (41)     (33)      (61)
                (111)  (31)    (221)    (42)      (322)
                       (211)   (311)    (51)      (331)
                       (1111)  (2111)   (222)     (421)
                               (11111)  (321)     (511)
                                        (411)     (2221)
                                        (2211)    (3211)
                                        (3111)    (4111)
                                        (21111)   (22111)
                                        (111111)  (31111)
                                                  (211111)
                                                  (1111111)

The complement for divisors instead of factors is A239312, ranks A368110.
These partitions have ranks A355529, complement A368100.
The complement for set-systems is A367902, ranks A367906, unlabeled A368095.
The version for set-systems is A367903, ranks A367907, unlabeled A368094.
For unlabeled multiset partitions we have A368097, complement A368098.
The version for factorizations is A368413, complement A368414.
The complement is counted by A370592.
For a unique choice we have A370594, ranks A370647.
A006530 gives greatest prime factor, least A020639.
A027746 lists prime factors, A112798 indices, length A001222.
A355741 counts choices of a prime factor of each prime index.
Cf. A000040, A000720, A133686, A355739, A355740, A367771, A367867, A367905, A370583, A370585, A370586, A370636.

Table[Length[Select[IntegerPartitions[n], Length[Select[Tuples[If[#==1,{},First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]==0&]],{n,0,30}]

a(n) = A000041(n) - A370592(n).

A367862 Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.

Original entry on oeis.org

1, 1, 1, 2, 20, 308, 5338, 105298, 2366704, 60065072, 1702900574, 53400243419, 1836274300504, 68730359299960, 2782263907231153, 121137565273808792, 5645321914669112342, 280401845830658755142, 14788386825536445299398, 825378055206721558026931, 48604149005046792753887416

Offset: 0

Gus Wiseman, Dec 07 2023

nonn

Unlike the connected case (A057500), these graphs may have more than one cycle; for example, the graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}} has multiple cycles.

			Non-isomorphic representatives of the a(4) = 20 graphs:
  {}
  {{1,2},{1,3},{2,3}}
  {{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..200

The connected case is A057500, unlabeled A001429.
Counting all vertices (not just covered) gives A116508.
The covering case is A367863, unlabeled A006649.
For set-systems we have A367916, ranks A367917.
A001187 counts connected graphs, A001349 unlabeled.
A003465 counts covering set-systems, unlabeled A055621, ranks A326754.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A323818 counts connected set-systems, unlabeled A323819, ranks A326749.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A006126, A316983, A321405, A326754, A326870, A326877, A367770, A367901, A367902, A367903.

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

\\ Here b(n) is A367863(n)
b(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n))
a(n) = sum(k=0, n, binomial(n,k) * b(k)) \\ Andrew Howroyd, Dec 29 2023

Binomial transform of A367863.

Terms a(8) and beyond from Andrew Howroyd, Dec 29 2023

cp's OEIS Frontend

A367868 Number of labeled simple graphs covering n vertices and contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A368413 Number of factorizations of n into positive integers > 1 such that it is not possible to choose a different prime factor of each factor.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A368097 Number of non-isomorphic multiset partitions of weight n contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A370592 Number of integer partitions of n such that it is possible to choose a different prime factor of each part.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A140637 Number of unlabeled graphs of positive excess with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A368414 Number of factorizations of n into positive integers > 1 such that it is possible to choose a different prime factor of each factor.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A137916 Number of n-node labeled graphs whose components are unicyclic graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A368094 Number of non-isomorphic set-systems of weight n contradicting a strict version of the axiom of choice.