|
| |
|
|
A328600
|
|
Number of necklace compositions of n with no part circularly followed by a divisor.
|
|
10
|
|
|
|
0, 0, 0, 0, 1, 0, 2, 1, 3, 5, 5, 7, 10, 18, 20, 29, 40, 58, 78, 111, 156, 218, 304, 429, 604, 859, 1209, 1726, 2423, 3462, 4904, 7000, 9953, 14210, 20270, 28979, 41391, 59253, 84799, 121539, 174162, 249931, 358577, 515090, 739932, 1063826, 1529766, 2201382, 3168565
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,7
|
|
|
COMMENTS
|
A necklace composition of n 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
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
The a(5) = 1 through a(13) = 18 necklace compositions (empty column not shown):
(2,3) (2,5) (3,5) (2,7) (3,7) (2,9) (5,7) (4,9)
(3,4) (4,5) (4,6) (3,8) (2,3,7) (5,8)
(2,4,3) (2,3,5) (4,7) (2,7,3) (6,7)
(2,5,3) (5,6) (3,4,5) (2,11)
(2,3,2,3) (2,4,5) (3,5,4) (3,10)
(2,3,2,5) (2,4,7)
(2,3,4,3) (2,6,5)
(2,8,3)
(3,6,4)
(2,3,5,3)
|
|
|
MATHEMATICA
|
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&And@@Not/@Divisible@@@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)->i%j<>0))); vector(n, n, sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 26 2019
|
|
|
CROSSREFS
|
The non-necklace version is A328598.
The version with singletons is A318729.
The case forbidding multiples as well as divisors is A328601.
The non-necklace, non-circular version is A328460.
The version for co-primality (instead of divisibility) is A328602.
Partitions with no part followed by a divisor are A328171.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
