A338553 Number of integer partitions of n that are either constant or relatively prime.

1, 1, 2, 3, 5, 7, 10, 15, 20, 29, 37, 56, 68, 101, 122, 170, 213, 297, 352, 490, 587, 778, 948, 1255, 1488, 1953, 2337, 2983, 3585, 4565, 5393, 6842, 8123, 10088, 12015, 14865, 17534, 21637, 25527, 31085, 36701, 44583, 52262, 63261, 74175, 88936, 104305, 124754

Offset: 0

Author

Gus Wiseman, Nov 03 2020

Keywords

• nonn

Comments

The Heinz numbers of these partitions are given by A338555 = A000961 \/ A289509. The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.

Examples

			The a(1) = 1 through a(7) = 15 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (21)   (22)    (32)     (33)      (43)
             (111)  (31)    (41)     (51)      (52)
                    (211)   (221)    (222)     (61)
                    (1111)  (311)    (321)     (322)
                            (2111)   (411)     (331)
                            (11111)  (2211)    (421)
                                     (3111)    (511)
                                     (21111)   (2221)
                                     (111111)  (3211)
                                               (4111)
                                               (22111)
                                               (31111)
                                               (211111)
                                               (1111111)
		

Crossrefs

A023022(n) + A059841(n) is the 2-part version.

A078374(n) + 1 is the strict case (n > 1).

A338554 counts the complement, with Heinz numbers A338552.

A338555 gives the Heinz numbers of these partitions.

A000005 counts constant partitions, with Heinz numbers A000961.

A000837 counts relatively prime partitions, with Heinz numbers A289509.

A282750 counts relatively prime partitions by sum and length.

Cf. A000010, A007360, A008284, A023023, A051424, A101271, A101391, A302698, A304712, A327516, A337664.

Programs

Mathematica

Table[Length[Select[IntegerPartitions[n],SameQ@@#||GCD@@#==1&]],{n,0,30}]

Formula

For n > 0, a(n) = A000005(n) + A000837(n) - 1.