login
A328602
Number of necklace compositions of n where no pair of circularly adjacent parts is relatively prime.
6
0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 20, 9, 35, 2, 69, 3, 111, 24, 190, 13, 384, 31, 646, 102, 1212, 113, 2348, 227, 4254, 613, 7993, 976, 15459, 1915, 28825, 4357, 54988, 7868, 105826, 15760, 201115, 33376, 385590, 63974, 744446, 128224, 1428047, 262914, 2754037
OFFSET
1,4
COMMENTS
A necklace composition of n (A008965) is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.
Circularity means the last part is followed by the first.
LINKS
EXAMPLE
The a(2) = 1 through a(10) = 8 necklace compositions:
(2) (3) (4) (5) (6) (7) (8) (9) (10)
(2,2) (2,4) (2,6) (3,6) (2,8)
(3,3) (4,4) (3,3,3) (4,6)
(2,2,2) (2,2,4) (5,5)
(2,2,2,2) (2,2,6)
(2,4,4)
(2,2,2,4)
(2,2,2,2,2)
The a(19) = 3 necklace compositions are: (19), (3,6,4,6), (2,2,6,3,6).
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&And@@Not/@CoprimeQ@@@Partition[#, 2, 1, 1]&]], {n, 10}]
PROG
(PARI)
b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q, ]}
seq(n)={my(v=sum(k=1, n, k*b(n, k, (i, j)->gcd(i, j)<>1))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 26 2019
CROSSREFS
The non-necklace, non-circular version is A178470.
The version for indivisibility (rather than co-primality) is A328600.
The circularly coprime (as opposed to anti-coprime) version is A328597.
Partitions with no consecutive parts relatively prime are A328187.
Sequence in context: A328187 A331885 A298971 * A218970 A216952 A114326
KEYWORD
nonn
AUTHOR
Gus Wiseman, Oct 25 2019
EXTENSIONS
Terms a(26) and beyond from Andrew Howroyd, Oct 26 2019
STATUS
approved