login
A178470
Number of compositions (ordered partitions) of n where no pair of adjacent part sizes is relatively prime.
27
1, 1, 1, 1, 2, 1, 5, 1, 8, 4, 17, 3, 38, 5, 67, 25, 132, 27, 290, 54, 547, 163, 1086, 255, 2277, 530, 4416, 1267, 8850, 2314, 18151, 4737, 35799, 10499, 71776, 20501, 145471, 41934, 289695, 89030, 581117, 178424, 1171545, 365619, 2342563, 761051, 4699711
OFFSET
0,5
COMMENTS
A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter.
a(0) = 1 vacuously for the empty composition. One could take a(1) = 0, on the theory that each composition is followed by infinitely many 0's, and thus the 1 is not relatively prime to its neighbor; but this definition seems simpler.
LINKS
EXAMPLE
The three compositions for 11 are <11>, <2,6,3> and <3,6,2>.
From Gus Wiseman, Nov 19 2019: (Start)
The a(1) = 1 through a(11) = 3 compositions (A = 10, B = 11):
1 2 3 4 5 6 7 8 9 A B
22 24 26 36 28 263
33 44 63 46 362
42 62 333 55
222 224 64
242 82
422 226
2222 244
262
424
442
622
2224
2242
2422
4222
22222
(End)
MAPLE
b:= proc(n, h) option remember; `if`(n=0, 1,
add(`if`(h=1 or igcd(j, h)>1, b(n-j, j), 0), j=2..n))
end:
a:= n-> `if`(n=1, 1, b(n, 1)):
seq(a(n), n=0..60); # Alois P. Heinz, Oct 23 2011
MATHEMATICA
b[n_, h_] := b[n, h] = If[n == 0, 1, Sum [If[h == 1 || GCD[j, h] > 1, b[n - j, j], 0], {j, 2, n}]]; a[n_] := If[n == 1, 1, b[n, 1]]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Oct 29 2015, after Alois P. Heinz *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !MatchQ[#, {___, x_, y_, ___}/; GCD[x, y]==1]&]], {n, 0, 20}] (* Gus Wiseman, Nov 19 2019 *)
PROG
(PARI) am(n)=local(r); r=matrix(n, n, i, j, i==j); for(i=2, n, for(j=1, i-1, for(k=1, j, if(gcd(i-j, k)>1, r[i, i-j]+=r[j, k])))); r
al(n)=local(m); m=am(n); vector(n, i, sum(j=1, i, m[i, j]))
CROSSREFS
The case of partitions is A328187, with Heinz numbers A328336.
Partitions with all pairs of consecutive parts relatively prime are A328172.
Compositions without consecutive divisible parts are A328460 (one way) or A328508 (both ways).
Sequence in context: A178472 A337667 A331888 * A093127 A115123 A132081
KEYWORD
nonn
AUTHOR
STATUS
approved