A325550 - OEIS

%I #11 Aug 31 2019 22:26:15

%S 1,2,2,4,5,7,11,16,18,41,86,118,273,465,731,1432,2791,4063,8429,14761,

%T 29465,58654,123799,227419,453229,861909,1697645,3192807,6315007,

%U 11718879,22795272,42965245,83615516,156215020,306561088,587300503,1140650287,2203107028

%N Number of necklace compositions of n with distinct multiplicities.

%C 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.

%H Andrew Howroyd, <a href="/A325550/b325550.txt">Table of n, a(n) for n = 1..100</a>

%F a(n) = Sum_{d|n} phi(d)*(Sum_{k=1..n/d} A242887(n/d, k)/k)/d. - _Andrew Howroyd_, Aug 31 2019

%e The a(1) = 1 through a(8) = 16 necklace compositions:

%e   (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)

%e        (11)  (111)  (22)    (113)    (33)      (115)      (44)

%e                     (112)   (122)    (114)     (133)      (116)

%e                     (1111)  (1112)   (222)     (223)      (224)

%e                             (11111)  (1113)    (1114)     (233)

%e                                      (11112)   (1222)     (1115)

%e                                      (111111)  (11113)    (2222)

%e                                                (11122)    (11114)

%e                                                (11212)    (11222)

%e                                                (111112)   (12122)

%e                                                (1111111)  (111113)

%e                                                           (111122)

%e                                                           (111212)

%e                                                           (112112)

%e                                                           (1111112)

%e                                                           (11111111)

%t neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&UnsameQ@@Length/@Split[Sort[#]]&]],{n,15}]

%o (PARI)

%o 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)}

%o a(n)={sumdiv(n, d, eulerphi(d)*b(n/d)/d)} \\ _Andrew Howroyd_, Aug 31 2019

%Y Cf. A000079, A000740, A008965, A059966, A098504, A098859, A242882, A242887, A325549, A325554.

%K nonn

%O 1,2

%A _Gus Wiseman_, May 10 2019

%E Terms a(26) and beyond from _Andrew Howroyd_, Aug 31 2019