A325550 Number of necklace compositions of n with distinct multiplicities.

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

Author

Gus Wiseman, May 10 2019

Keywords

• nonn

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.

Examples

			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)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100

Crossrefs

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

Programs

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}]

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<Andrew Howroyd, Aug 31 2019

Formula

a(n) = Sum_{d|n} phi(d)*(Sum_{k=1..n/d} A242887(n/d, k)/k)/d. - Andrew Howroyd, Aug 31 2019

Extensions

Terms a(26) and beyond from Andrew Howroyd, Aug 31 2019