cp's OEIS Frontend

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

%I A328172 #15 May 10 2021 15:33:27
%S A328172 1,1,2,3,4,6,7,10,12,16,19,24,28,36,43,51,62,74,87,104,122,143,169,
%T A328172 195,227,260,302,346,397,455,521,599,686,780,889,1001,1138,1286,1454,
%U A328172 1638,1846,2076,2330,2614,2929,3280,3666,4093,4565,5085,5667,6300,7002
%N A328172 Number of integer partitions of n with all pairs of consecutive parts relatively prime.
%C A328172 Except for any number of 1's, these partitions must be strict. The fully strict case is A328188.
%C A328172 Partitions with no consecutive pair of parts relatively prime are A328187, with strict case A328220.
%H A328172 Alois P. Heinz, <a href="/A328172/b328172.txt">Table of n, a(n) for n = 0..1000</a>
%e A328172 The a(1) = 1 through a(8) = 12 partitions:
%e A328172   (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
%e A328172        (11)  (21)   (31)    (32)     (51)      (43)       (53)
%e A328172              (111)  (211)   (41)     (321)     (52)       (71)
%e A328172                     (1111)  (311)    (411)     (61)       (431)
%e A328172                             (2111)   (3111)    (511)      (521)
%e A328172                             (11111)  (21111)   (3211)     (611)
%e A328172                                      (111111)  (4111)     (5111)
%e A328172                                                (31111)    (32111)
%e A328172                                                (211111)   (41111)
%e A328172                                                (1111111)  (311111)
%e A328172                                                           (2111111)
%e A328172                                                           (11111111)
%p A328172 b:= proc(n, i, s) option remember; `if`(n=0 or i=1, 1,
%p A328172       `if`(andmap(j-> igcd(i, j)=1, s), b(n-i, min(n-i, i-1),
%p A328172            numtheory[factorset](i)), 0)+b(n, i-1, s))
%p A328172     end:
%p A328172 a:= n-> b(n$2, {}):
%p A328172 seq(a(n), n=0..60);  # _Alois P. Heinz_, Oct 13 2019
%t A328172 Table[Length[Select[IntegerPartitions[n],!MatchQ[#,{___,x_,y_,___}/;GCD[x,y]>1]&]],{n,0,30}]
%t A328172 (* Second program: *)
%t A328172 b[n_, i_, s_] := b[n, i, s] = If[n == 0 || i == 1, 1,
%t A328172      If[AllTrue[s, GCD[i, #] == 1&], b[n - i, Min[n - i, i - 1],
%t A328172      FactorInteger[i][[All, 1]]], 0] + b[n, i - 1, s]];
%t A328172 a[n_] := b[n, n, {}];
%t A328172 a /@ Range[0, 60] (* _Jean-François Alcover_, May 10 2021, after _Alois P. Heinz_ *)
%Y A328172 The case of compositions is A167606.
%Y A328172 The strict case is A328188.
%Y A328172 The Heinz numbers of these partitions are given by A328335.
%Y A328172 Cf. A000837, A018783, A178470, A328028, A328170, A328171, A328187, A328188 A328220.
%K A328172 nonn
%O A328172 0,3
%A A328172 _Gus Wiseman_, Oct 12 2019