login
A325550
Number of necklace compositions of n with distinct multiplicities.
2
1, 2, 2, 4, 5, 7, 11, 16, 18, 41, 86, 118, 273, 465, 731, 1432, 2791, 4063, 8429, 14761, 29465, 58654, 123799, 227419, 453229, 861909, 1697645, 3192807, 6315007, 11718879, 22795272, 42965245, 83615516, 156215020, 306561088, 587300503, 1140650287, 2203107028
OFFSET
1,2
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.
LINKS
FORMULA
a(n) = Sum_{d|n} phi(d)*(Sum_{k=1..n/d} A242887(n/d, k)/k)/d. - Andrew Howroyd, Aug 31 2019
EXAMPLE
The a(1) = 1 through a(8) = 16 necklace compositions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (111) (22) (113) (33) (115) (44)
(112) (122) (114) (133) (116)
(1111) (1112) (222) (223) (224)
(11111) (1113) (1114) (233)
(11112) (1222) (1115)
(111111) (11113) (2222)
(11122) (11114)
(11212) (11222)
(111112) (12122)
(1111111) (111113)
(111122)
(111212)
(112112)
(1111112)
(11111111)
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&UnsameQ@@Length/@Split[Sort[#]]&]], {n, 15}]
PROG
(PARI)
b(n)={((r, k, b, w)->if(!k||!r, if(r, 0, (w-1)!), sum(m=0, r\k, if(!m || !bittest(b, m), self()(r-k*m, k-1, bitor(b, 1<<m), w+m)/m!))))(n, n, 1, 0)}
a(n)={sumdiv(n, d, eulerphi(d)*b(n/d)/d)} \\ Andrew Howroyd, Aug 31 2019
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 10 2019
EXTENSIONS
Terms a(26) and beyond from Andrew Howroyd, Aug 31 2019
STATUS
approved