|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
Cf. A000031, A000740, A008965, A032153, A318728, A318729, A318748, A328172, A328188, A328220, A328335, A328336, A328601, A328609.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|