Number of necklaces
There are
different k-ary necklaces of length n, where is Euler's totient function.[1]
When the beads are restricted to particular color multiset , where is the number of beads of color , there are
different necklaces made of all the beads of . [2]
Here and is the multinomial coefficient.
These two formulas follow directly from Pólya's enumeration theorem applied to the action of the cyclic group acting on the set of all functions .
If all k colors must be used, the count is
where are the Stirling number of the second kind.
(sequence A054631 in the OEIS) and (sequence A087854 in the OEIS) are related via the Binomial coefficients:
and