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

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.

Links

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

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

Example

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)

Mathematica

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

Prog

(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

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.

Sequence in context: A280278 A136275 A344002 * A078408 A007478 A014605

Adjacent sequences: A328167 A328168 A328169 * A328171 A328172 A328173

Keyword

nonn

Author

Gus Wiseman, Oct 09 2019

Status

approved