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
Alois P. Heinz, Table of n, a(n) for n = 0..1000
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
Partitions with all pairs of consecutive parts relatively prime are A328172.
KEYWORD
nonn
AUTHOR
Franklin T. Adams-Watters, May 28 2010
STATUS
approved