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,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

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

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

Crossrefs

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

Sequence in context: A027069 A238494 A359388 * A362608 A325330 A319160

Adjacent sequences: A325547 A325548 A325549 * A325551 A325552 A325553

Keyword

nonn

Author

Gus Wiseman, May 10 2019

Extensions

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

Status

approved