A355740 -id:A355740 - cp's OEIS frontend

A355744 Number of multisets that can be obtained by choosing a prime factor of each prime index of n.

1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2

Offset: 1

Gus Wiseman, Jul 18 2022

nonn

First differs from A355741 at a(169) = 3, A355741(169) = 4.

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.

			The a(169) = 3 multisets are: {2,2}, {2,3}, {3,3}.
The a(507) = 3 multisets are: {2,2,2}, {2,2,3}, {2,3,3}.

Wikipedia, Axiom of choice.

Choosing from all divisors gives A355733, firsts A355734.
Counting sequences instead of multisets gives A355741.
Choosing weakly increasing sequences of divisors gives A355745.
A001414 adds up distinct prime divisors, counted by A001221.
A003963 multiplies together the prime indices of n.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A324850 lists numbers divisible by the product of their prime indices.
A344606 counts alternating permutations of prime indices.
Cf. A000720, A076610, A120383, A289509, A335433, A340852, A355731, A355735, A355737, A355739, A355740.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Union[Sort/@Tuples[primeMS/@primeMS[n]]]],{n,100}]

A051026 Number of primitive subsequences of {1, 2, ..., n}.

Original entry on oeis.org

1, 2, 3, 5, 7, 13, 17, 33, 45, 73, 103, 205, 253, 505, 733, 1133, 1529, 3057, 3897, 7793, 10241, 16513, 24593, 49185, 59265, 109297, 163369, 262489, 355729, 711457, 879937, 1759873, 2360641, 3908545, 5858113, 10534337, 12701537, 25403073, 38090337, 63299265, 81044097, 162088193, 205482593, 410965185, 570487233, 855676353

Offset: 0

Eric W. Weisstein

a(n) counts all subsequences of {1, ..., n} in which no term divides any other. If n is a prime a(n) = 2*a(n-1)-1 because for each subsequence s counted by a(n-1) two different subsequences are counted by a(n): s and s,n. There is only one exception: 1,n is not a primitive subsequence because 1 divides n. For all n>1: a(n) < 2*a(n-1). - Alois P. Heinz, Mar 07 2011

Maximal primitive subsets are counted by A326077. - Gus Wiseman, Jun 07 2019

			a(4) = 7, the primitive subsequences (including the empty sequence) are: (), (1), (2), (3), (4), (2,3), (3,4).
a(5) = 13 = 2*7-1, the primitive subsequences are: (), (5), (1), (2), (2,5), (3), (3,5), (4), (4,5), (2,3), (2,3,5), (3,4), (3,4,5).
From _Gus Wiseman_, Jun 07 2019: (Start)
The a(0) = 1 through a(5) = 13 primitive (pairwise indivisible) subsets:
  {}  {}   {}   {}     {}     {}
      {1}  {1}  {1}    {1}    {1}
           {2}  {2}    {2}    {2}
                {3}    {3}    {3}
                {2,3}  {4}    {4}
                       {2,3}  {5}
                       {3,4}  {2,3}
                              {2,5}
                              {3,4}
                              {3,5}
                              {4,5}
                              {2,3,5}
                              {3,4,5}
a(n) is also the number of subsets of {1..n} containing all of their pairwise products <= n as well as any quotients of divisible elements. For example, the a(0) = 1 through a(5) = 13 subsets are:
  {}  {}   {}     {}       {}         {}
      {1}  {1}    {1}      {1}        {1}
           {1,2}  {1,2}    {1,3}      {1,3}
                  {1,3}    {1,4}      {1,4}
                  {1,2,3}  {1,2,4}    {1,5}
                           {1,3,4}    {1,2,4}
                           {1,2,3,4}  {1,3,4}
                                      {1,3,5}
                                      {1,4,5}
                                      {1,2,3,4}
                                      {1,2,4,5}
                                      {1,3,4,5}
                                      {1,2,3,4,5}
Also the number of subsets of {1..n} containing all of their multiples <= n. For example, the a(0) = 1 through a(5) = 13 subsets are:
  {}  {}   {}     {}       {}         {}
      {1}  {2}    {2}      {3}        {3}
           {1,2}  {3}      {4}        {4}
                  {2,3}    {2,4}      {5}
                  {1,2,3}  {3,4}      {2,4}
                           {2,3,4}    {3,4}
                           {1,2,3,4}  {3,5}
                                      {4,5}
                                      {2,3,4}
                                      {2,4,5}
                                      {3,4,5}
                                      {2,3,4,5}
                                      {1,2,3,4,5}
(End)
From _Gus Wiseman_, Mar 12 2024: (Start)
Also the number of subsets of {1..n} containing all divisors of the elements. For example, the a(0) = 1 through a(6) = 17 subsets are:
  {}  {}   {}     {}       {}         {}
      {1}  {1}    {1}      {1}        {1}
           {1,2}  {1,2}    {1,2}      {1,2}
                  {1,3}    {1,3}      {1,3}
                  {1,2,3}  {1,2,3}    {1,5}
                           {1,2,4}    {1,2,3}
                           {1,2,3,4}  {1,2,4}
                                      {1,2,5}
                                      {1,3,5}
                                      {1,2,3,4}
                                      {1,2,3,5}
                                      {1,2,4,5}
                                      {1,2,3,4,5}
(End)

Blanchet-Sadri, Francine. Algorithmic combinatorics on partial words. Chapman & Hall/CRC, Boca Raton, FL, 2008. ii+385 pp. ISBN: 978-1-4200-6092-8; 1-4200-6092-9 MR2384993 (2009f:68142). See p. 320. - N. J. A. Sloane, Apr 06 2012

Juliana Couras, Ricardo Jesus, and Tomás Oliveira e Silva, Table of n, a(n) for n = 0..800 (terms up to n=80 from Alois P. Heinz)
Marcel K. Goh and Jonah Saks, Alternating-sum statistics for certain sets of integers, arXiv:2206.12535 [math.CO], 2022.
Nathan McNew, Counting primitive subsets and other statistics of the divisor graph of {1,2,..,n}, arXiv:1808.04923 [math.NT], 2018.
Richárd Palincza, Counting type and extremal problems from Arithmetic Combinatorics, Ph. D. Thesis, Budapest Univ. Tech. Econ. (Hungary, 2024).
Eric Weisstein's World of Mathematics, Primitive Sequence

Cf. A007865, A054519, A096827, A103580, A303362, A305148.
Cf. A326023, A326076, A326077, A326081, A326082, A326083, A326117.
Cf. A037031, A051026, A355740, A368110, A370585.

with(numtheory):
b:= proc(s) option remember; local n;
      n:= max(s[]);
      `if`(n<0, 1, b(s minus {n}) + b(s minus divisors(n)))
    end:
bb:= n-> b({$2..n} minus divisors(n)):
sb:= proc(n) option remember; `if`(n<2, 0, bb(n) + sb(n-1)) end:
a:= n-> `if`(n=0, 1, `if`(isprime(n), 2*a(n-1)-1, 2+sb(n))):
seq(a(n), n=0..40);  # Alois P. Heinz, Mar 07 2011

b[s_] := b[s] = With[{n=Max[s]}, If[n < 0, 1, b[Complement[s, {n}]] + b[Complement[s, Divisors[n]]]]];
bb[n_] := b[Complement[Range[2, n], Divisors[n]]];
sb[n_] := sb[n] = If[n < 2, 0, bb[n] + sb[n-1]];
a[n_] := If[n == 0, 1, If[PrimeQ[n], 2a[n-1] - 1, 2 + sb[n]]]; Table[a[n], {n, 0, 37}]
(* Jean-François Alcover, Jul 27 2011, converted from Maple *)
Table[Length[Select[Subsets[Range[n]], SubsetQ[#,Select[Union@@Table[#*i,{i,n}],#<=n&]]&]],{n,10}] (* Gus Wiseman, Jun 07 2019 *)
Table[Length[Select[Subsets[Range[n]], #==Union@@Divisors/@#&]],{n,0,10}] (* Gus Wiseman, Mar 12 2024 *)

More terms from David Wasserman, May 02 2002

a(32)-a(37) from Donovan Johnson, Aug 11 2010

A355732 Least k such that there are exactly n ways to choose a sequence of divisors, one of each element of the multiset of prime indices of k (with multiplicity).

Original entry on oeis.org

1, 3, 7, 9, 53, 21, 311, 27, 49, 159, 8161, 63, 38873, 933, 371, 81, 147, 477, 2177, 24483, 189, 2809, 343, 2799, 1113, 243, 57127, 16483, 441, 1431, 6531, 73449, 2597, 567, 96721, 8427, 1029, 8397, 3339, 15239, 729, 49449, 1323, 19663, 4293, 2401, 19593, 7791

Offset: 1

Gus Wiseman, Jul 21 2022

nonn

This is the position of first appearance of n in A355731.
Appears to be a subset of A353397.
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.

			The terms together with their prime indices begin:
      1: {}
      3: {2}
      7: {4}
      9: {2,2}
     53: {16}
     21: {2,4}
    311: {64}
     27: {2,2,2}
     49: {4,4}
    159: {2,16}
   8161: {1024}
     63: {2,2,4}
For example, the choices for a(12) = 63 are:
  (1,1,1)  (1,2,2)  (2,1,4)
  (1,1,2)  (1,2,4)  (2,2,1)
  (1,1,4)  (2,1,1)  (2,2,2)
  (1,2,1)  (2,1,2)  (2,2,4)

Positions of first appearances in A355731.
Counting distinct sequences after sorting: A355734, firsts of A355733.
Requiring the result to be weakly increasing: A355736, firsts of A355735.
Requiring the result to be relatively prime: A355738, firsts of A355737.
A000005 counts divisors.
A001414 adds up distinct prime divisors, counted by A001221.
A003963 multiplies together the prime indices of n.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A120383 lists numbers divisible by all of their prime indices.
A324850 lists numbers divisible by the product of their prime indices.
Cf. A000720, A076610, A340606, A355739, A355740, A355741, A355742, A355744, A355746, A355747, A355748.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
mnrm[s_]:=If[Min@@s==1,mnrm[DeleteCases[s-1,0]]+1,0];
az=Table[Times@@Length/@Divisors/@primeMS[n],{n,1000}];
Table[Position[az,k][[1,1]],{k,mnrm[az]}]

A368110 Numbers of which it is possible to choose a different divisor of each prime index.

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, 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, 97

Offset: 1

Gus Wiseman, Dec 15 2023

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.

By Hall's marriage theorem, k is a term if and only if there is no sub-multiset S of the prime indices of k such that fewer than |S| numbers are divisors of a member of S. Equivalently, there is no divisor of k in A370348. - Robert Israel, Feb 15 2024

			The terms together with their prime indices begin:
   1: {}
   2: {1}
   3: {2}
   5: {3}
   6: {1,2}
   7: {4}
   9: {2,2}
  10: {1,3}
  11: {5}
  13: {6}
  14: {1,4}
  15: {2,3}
  17: {7}
  19: {8}
  21: {2,4}
  22: {1,5}
  23: {9}
  25: {3,3}
  26: {1,6}
  29: {10}
  30: {1,2,3}

Robert Israel, Table of n, a(n) for n = 1..10000

Partitions of this type are counted by A239312, complement A370320.
Positions of nonzero terms in A355739.
Complement of A355740.
For just prime divisors we have A368100, complement A355529 (odd A355535).
A000005 counts divisors.
A003963 multiplies together the prime indices of n.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A120383 lists numbers divisible by all of their prime indices.
A324850 lists numbers divisible by the product of their prime indices.
A355731 counts choices of a divisor of each prime index, firsts A355732.
A355741 chooses prime factors of prime indices, variations A355744, A355745.
Cf. A000720, A076610, A111774, A335433, A335448, A340852, A355733, A355734, A355737, A355749, A370348.

filter:= proc(n) uses numtheory, GraphTheory; local B,S,F,D,E,G,t,d;
  F:= ifactors(n)[2];
  F:= map(t -> [pi(t[1]),t[2]], F);
  D:= `union`(seq(divisors(t[1]), t = F));
  F:= map(proc(t) local i;seq([t[1],i],i=1..t[2]) end proc,F);
  if nops(D) < nops(F) then return false fi;
  E:= {seq(seq({t,d},d=divisors(t[1])),t = F)};
  S:= map(t -> convert(t,name), [op(F),op(D)]);
  E:= map(e -> map(convert,e,name),E);
  G:= Graph(S,E);
  B:= BipartiteMatching(G);
  B[1] = nops(F);
end proc:
select(filter, [$1..100]); # Robert Israel, Feb 15 2024

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

Heinz numbers of the partitions counted by A239312.

A355745 Number of ways to choose a prime factor of each prime index of n (with multiplicity, in weakly increasing order) such that the result is also weakly increasing.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 0, 0, 2, 0, 2, 0, 1, 0, 2, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2

Offset: 1

Gus Wiseman, Jul 18 2022

nonn

First differs from A355741 and A355744 at n = 35.

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.

			The prime indices of 1469 are {6,30}, and there are five valid choices: (2,2), (2,3), (2,5), (3,3), (3,5), so a(1469) = 5.

Wikipedia, Cartesian product.

Allowing all divisors gives A355735, firsts A355736, reverse A355749.
Not requiring an increasing sequence gives A355741.
Choosing a multiset instead of sequence gives A355744.
A000005 counts divisors.
A001414 adds up distinct prime divisors, counted by A001221.
A003963 multiplies together the prime indices of n.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A120383 lists numbers divisible by all of their prime indices.
A324850 lists numbers divisible by the product of their prime indices.
A355731 chooses of a divisor of each prime index, firsts A355732.
A355733 chooses a multiset of divisors, firsts A355734.
Cf. A000720, A076610, A335433, A340852, A355737, A355739, A355740, A355742.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[Tuples[Union/@primeMS/@primeMS[n]],LessEqual@@#&]],{n,100}]

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

Original entry on oeis.org

1, 0, 1, 4, 34, 387, 5596, 97149, 1959938, 44956945, 1154208544, 32772977715, 1019467710328, 34473686833527, 1259038828370402, 49388615245426933, 2070991708598960524, 92445181295983865757, 4376733266230674345874, 219058079619119072854095, 11556990682657196214302036

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.

Number of labeled n-node graphs with at most one cycle in each component and no isolated vertices. - Andrew Howroyd, Dec 30 2023

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

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

The connected case is A129271.
The non-covering case is A133686, complement A367867.
The complement is A367868, connected A140638 (unlabeled A140636).
A001187 counts connected graphs, A001349 unlabeled.
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.
A143543 counts simple labeled graphs by number of connected components.
Cf. A057500, A116508, A355740, A367770, A367863, A367902.

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

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(sqrt(1/(1-t))*exp(t/2 - 3*t^2/4 - x)))} \\ Andrew Howroyd, Dec 30 2023

E.g.f.: exp(B(x) - x - 1) where B(x) is the e.g.f. of A129271. - Andrew Howroyd, Dec 30 2023

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

A355733 Number of multisets that can be obtained by choosing a divisor of each prime index of n.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 2, 2, 4, 3, 4, 1, 2, 3, 4, 2, 5, 2, 3, 2, 3, 4, 4, 3, 4, 4, 2, 1, 4, 2, 6, 3, 6, 4, 7, 2, 2, 5, 4, 2, 6, 3, 4, 2, 6, 3, 4, 4, 5, 4, 4, 3, 7, 4, 2, 4, 6, 2, 7, 1, 7, 4, 2, 2, 6, 6, 6, 3, 4, 6, 6, 4, 6, 7, 4, 2, 5, 2, 2, 5, 4, 4, 7

Offset: 1

Gus Wiseman, Jul 16 2022

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.

			The a(15) = 4 multisets are: {1,1}, {1,2}, {1,3}, {2,3}.
The a(18) = 3 multisets are: {1,1,1}, {1,1,2}, {1,2,2}.

Robert Price, Table of n, a(n) for n = 1..2000
Wikipedia, Axiom of choice.

Counting all choices of divisors gives A355731, firsts A355732.
Positions of first appearances are A355734.
Choosing weakly increasing divisors gives A355735, firsts A355736.
Choosing only prime divisors gives A355744.
The version choosing a divisor of each number from 1 to n is A355747.
A000005 counts divisors.
A001414 adds up distinct prime divisors, counted by A001221.
A003963 multiplies together the prime indices of n.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A061395 selects the maximum prime index.
A120383 lists numbers divisible by all of their prime indices.
A324850 lists numbers divisible by the product of their prime indices.
A340852 lists numbers that can be factored into divisors of bigomega.
Cf. A000720, A076610, A289509, A316524, A335433, A335448, A340606, A344616, A355737, A355739, A355740, A355741, A355746.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Union[Sort/@Tuples[Divisors/@primeMS[n]]]],{n,100}]

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).

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).

A367901 Number of sets of subsets of {1..n} contradicting a strict version of the axiom of choice.

Original entry on oeis.org

1, 2, 9, 195, 63765, 4294780073, 18446744073639513336, 340282366920938463463374607341656713953, 115792089237316195423570985008687907853269984665640564039457583610129753447747

Offset: 0

Gus Wiseman, Dec 05 2023

nonn

			The a(2) = 9 sets of sets:
  {{}}
  {{},{1}}
  {{},{2}}
  {{},{1,2}}
  {{},{1},{2}}
  {{},{1},{1,2}}
  {{},{2},{1,2}}
  {{1},{2},{1,2}}
  {{},{1},{2},{1,2}}

Wikipedia, Axiom of choice.

The version for simple graphs is A367867, covering A367868.
The complement is counted by A367902, no singletons A367770, ranks A367906.
The version without empty edges is A367903, ranks A367907.
For a unique choice (instead of none) we have A367904, ranks A367908.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems, unlabeled A323819.
A326031 gives weight of the set-system with BII-number n.
Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367769, A367862, A367905.

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

a(n) = 2^2^n - A367902(n). - Christian Sievers, Aug 01 2024

a(5)-a(8) from Christian Sievers, Aug 01 2024

cp's OEIS Frontend

A355744 Number of multisets that can be obtained by choosing a prime factor of each prime index of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A051026 Number of primitive subsequences of {1, 2, ..., n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A355732 Least k such that there are exactly n ways to choose a sequence of divisors, one of each element of the multiset of prime indices of k (with multiplicity).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A368110 Numbers of which it is possible to choose a different divisor of each prime index.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A355745 Number of ways to choose a prime factor of each prime index of n (with multiplicity, in weakly increasing order) such that the result is also weakly increasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A355733 Number of multisets that can be obtained by choosing a divisor of each prime index of n.

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