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

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

Links

Table of n, a(n) for n=0..60.

Formula

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

Example

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

Mathematica

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

Crossrefs

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.

Sequence in context: A342016 A360923 A123621 * A151662 A049786 A282611

Adjacent sequences: A370589 A370590 A370591 * A370593 A370594 A370595

Keyword

nonn

Author

Gus Wiseman, Feb 29 2024

Status

approved