A328170 Number of integer partitions of n whose parts minus 1 are relatively prime.

0, 0, 1, 1, 2, 3, 5, 8, 12, 18, 27, 38, 53, 74, 102, 137, 184, 241, 317, 413, 536, 687, 880, 1112, 1405, 1765, 2215, 2755, 3424, 4229, 5216, 6402, 7847, 9572, 11662, 14148, 17139, 20688, 24940, 29971, 35969, 43044, 51438, 61311, 72985, 86678, 102807, 121675

Offset: 0

Author

Gus Wiseman, Oct 09 2019

Keywords

• nonn

Comments

A partition is relatively prime if the GCD of its parts is 1. Zeros are ignored when computing GCD, and the empty set has GCD 0.

Examples

			The a(2) = 1 through a(9) = 18 partitions:
  (2)  (21)  (22)   (32)    (42)     (43)      (62)       (54)
             (211)  (221)   (222)    (52)      (332)      (63)
                    (2111)  (321)    (322)     (422)      (72)
                            (2211)   (421)     (431)      (432)
                            (21111)  (2221)    (521)      (522)
                                     (3211)    (2222)     (621)
                                     (22111)   (3221)     (3222)
                                     (211111)  (4211)     (3321)
                                               (22211)    (4221)
                                               (32111)    (4311)
                                               (221111)   (5211)
                                               (2111111)  (22221)
                                                          (32211)
                                                          (42111)
                                                          (222111)
                                                          (321111)
                                                          (2211111)
                                                          (21111111)
		

Links

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

Crossrefs

The Heinz numbers of these partitions are given by A328168.

Partitions whose parts are relatively prime are A000837.

Partitions whose parts plus 1 are relatively prime are A318980.

The GCD of the prime indices of n, all minus 1, is A328167(n).

Cf. A007359, A018783, A258409, A289509, A328163, A328164.

Programs

Mathematica

Table[Length[Select[IntegerPartitions[n],GCD@@(#-1)==1&]],{n,0,30}]

PARI

seq(n)=Vec(sum(d=1, n-1, moebius(d)*(-1/(1-x) + 1/prod(k=0, n\d, 1 - x*x^(k*d) + O(x*x^n)))), -(n+1)) \\ Andrew Howroyd, Oct 17 2019

Formula

G.f.: Sum_{d>=1} mu(d)*(-1/(1-x) + 1/(Prod_{k>=0} 1 - x^(k*d + 1))). - Andrew Howroyd, Oct 17 2019