A328172 Number of integer partitions of n with all pairs of consecutive parts relatively prime.

1, 1, 2, 3, 4, 6, 7, 10, 12, 16, 19, 24, 28, 36, 43, 51, 62, 74, 87, 104, 122, 143, 169, 195, 227, 260, 302, 346, 397, 455, 521, 599, 686, 780, 889, 1001, 1138, 1286, 1454, 1638, 1846, 2076, 2330, 2614, 2929, 3280, 3666, 4093, 4565, 5085, 5667, 6300, 7002

Offset: 0

Author

Gus Wiseman, Oct 12 2019

Keywords

• nonn

Comments

Except for any number of 1's, these partitions must be strict. The fully strict case is A328188.

Partitions with no consecutive pair of parts relatively prime are A328187, with strict case A328220.

Examples

			The a(1) = 1 through a(8) = 12 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (31)    (32)     (51)      (43)       (53)
             (111)  (211)   (41)     (321)     (52)       (71)
                    (1111)  (311)    (411)     (61)       (431)
                            (2111)   (3111)    (511)      (521)
                            (11111)  (21111)   (3211)     (611)
                                     (111111)  (4111)     (5111)
                                               (31111)    (32111)
                                               (211111)   (41111)
                                               (1111111)  (311111)
                                                          (2111111)
                                                          (11111111)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

The case of compositions is A167606.

The strict case is A328188.

The Heinz numbers of these partitions are given by A328335.

Cf. A000837, A018783, A178470, A328028, A328170, A328171, A328187, A328188 A328220.

Programs

Maple

b:= proc(n, i, s) option remember; `if`(n=0 or i=1, 1,
      `if`(andmap(j-> igcd(i, j)=1, s), b(n-i, min(n-i, i-1),
           numtheory[factorset](i)), 0)+b(n, i-1, s))
    end:
a:= n-> b(n$2, {}):
seq(a(n), n=0..60);  # Alois P. Heinz, Oct 13 2019

Mathematica

Table[Length[Select[IntegerPartitions[n],!MatchQ[#,{_,x_,y_,_}/;GCD[x,y]>1]&]],{n,0,30}]
(* Second program: *)
b[n_, i_, s_] := b[n, i, s] = If[n == 0 || i == 1, 1,
     If[AllTrue[s, GCD[i, #] == 1&], b[n - i, Min[n - i, i - 1],
     FactorInteger[i][[All, 1]]], 0] + b[n, i - 1, s]];
a[n_] := b[n, n, {}];
a /@ Range[0, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)