login
A328188
Number of strict integer partitions of n with all pairs of consecutive parts relatively prime.
10
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, 86, 95, 109, 124, 144, 165, 181, 203, 221, 249, 285, 316, 352, 392, 438, 484, 538, 599, 666, 737, 813, 899, 992, 1102, 1215, 1335, 1472, 1621, 1776, 1946, 2137, 2336
OFFSET
0,4
LINKS
EXAMPLE
The a(1) = 1 through a(15) = 15 partitions (A..F = 10..15):
1 2 3 4 5 6 7 8 9 A B C D E F
21 31 32 51 43 53 54 73 65 75 76 95 87
41 321 52 71 72 91 74 B1 85 B3 B4
61 431 81 532 83 543 94 D1 D2
521 432 541 92 651 A3 653 E1
531 721 A1 732 B2 743 654
4321 731 741 C1 752 753
5321 831 652 761 852
921 751 851 951
832 941 A32
5431 A31 B31
7321 B21 6531
5432 7431
6521 7521
8321 54321
MAPLE
b:= proc(n, i, s) option remember; `if`(i*(i+1)/2<n, 0, `if`(n=0, 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], UnsameQ@@#&&!MatchQ[#, {___, x_, y_, ___}/; GCD[x, y]>1]&]], {n, 0, 30}]
(* Second program: *)
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]]];
a[n_] := b[n, n, {}];
a /@ Range[0, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)
CROSSREFS
The case of compositions is A167606.
The non-strict case is A328172.
The Heinz numbers of these partitions are given by A328335.
Partitions with no pairs of consecutive parts relatively prime are A328187.
Sequence in context: A366853 A076678 A029024 * A358637 A106244 A029023
KEYWORD
nonn
AUTHOR
Gus Wiseman, Oct 13 2019
STATUS
approved