|
%I #15 May 10 2021 06:41:13
%S 1,1,1,2,2,3,3,4,5,6,7,8,9,12,15,15,19,23,25,30,35,39,47,52,58,65,75,
%T 86,95,109,124,144,165,181,203,221,249,285,316,352,392,438,484,538,
%U 599,666,737,813,899,992,1102,1215,1335,1472,1621,1776,1946,2137,2336
%N Number of strict integer partitions of n with all pairs of consecutive parts relatively prime.
%H Alois P. Heinz, <a href="/A328188/b328188.txt">Table of n, a(n) for n = 0..1000</a>
%e The a(1) = 1 through a(15) = 15 partitions (A..F = 10..15):
%e 1 2 3 4 5 6 7 8 9 A B C D E F
%e 21 31 32 51 43 53 54 73 65 75 76 95 87
%e 41 321 52 71 72 91 74 B1 85 B3 B4
%e 61 431 81 532 83 543 94 D1 D2
%e 521 432 541 92 651 A3 653 E1
%e 531 721 A1 732 B2 743 654
%e 4321 731 741 C1 752 753
%e 5321 831 652 761 852
%e 921 751 851 951
%e 832 941 A32
%e 5431 A31 B31
%e 7321 B21 6531
%e 5432 7431
%e 6521 7521
%e 8321 54321
%p b:= proc(n, i, s) option remember; `if`(i*(i+1)/2<n, 0, `if`(n=0, 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],UnsameQ@@#&&!MatchQ[#,{___,x_,y_,___}/;GCD[x,y]>1]&]],{n,0,30}]
%t (* Second program: *)
%t b[n_, i_, s_] := b[n, i, s] = If[i(i + 1)/2 < n, 0, If[n == 0, 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]]];
%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 non-strict case is A328172.
%Y The Heinz numbers of these partitions are given by A328335.
%Y Partitions with no pairs of consecutive parts relatively prime are A328187.
%Y Cf. A000837, A018783, A178470, A328028, A328170, A328171, A328187, A328220.
%K nonn
%O 0,4
%A _Gus Wiseman_, Oct 13 2019
|
