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