1
$\begingroup$

Here necklace has its common combinatorial sense.

If the type of a necklace is the number of things in the necklace,

1100:1100, 0110, 0011, 1001--type 4

then how many necklaces are there of type n, with k 0's and n-k 1's?

More generally, how many necklaces are there of type m(a divisor of n) with k 0's and m-k 1's?

  • 0
    OK, now the last part makes sense, but how is the question any different from the first part?2011-11-13

2 Answers 2

2

Polya's enumeration formula for the group of rotations $G$ acting on the $n$ beads of an unflippable necklace that is coloured by two colors where one color has weight 1 and one color has weight 0 gives

$\frac{1}{|G|}\sum_{g \in G}(1+x)^{c_1(g)}(1+x^2)^{c_2(g)}\dots,$

since $f(x)=1+x$ is the generating function for the two colors and where $c_i(g)$ denotes the number of cycles of length $i$ of $g$ as permutation of the $n$ beads.

The rotations are all some $m$th power of the rotation that moves each bead to each neighbor.

If the gcd of $m$ and $n$ is $d$, then this rotation has $d$ cycles of length $n/d$ as permutation of the beads.

This gives: $\begin{multline} \frac{1}{n}\sum_{d | n} (1+x^{n/d})^d (\text{number of $m < n$ having greatest common divisor $d$ with $n$})\\ \overset{(*)}{=} \frac{1}{n}\sum_{d|n}(1+x^{n/d})^d \varphi\left(\frac{n}{d}\right)= \frac{1}{n}\sum_{d|n}(1+x^{d})^{n/d} \varphi(d). \end{multline}$

where $\varphi$ denotes the Euler phi function that counts the numbers smaller than $n$ that are relatively prime with $n$.

Picking the coefficient of $x^k$ gives $\frac{1}{n}\sum_{d|n \text{ and } d|k}\binom{n/d}{k/d} \varphi(d),$

which is the formula from the other answer.

If the "common combinatorial sense" includes reflection, the formula can be adapted.

Edited to add an explanation of the equality marked with (*):

The numbers $m$ with $\gcd(m,n)=d$ are all multiples of $d$, so denote this by $m=l\cdot d$. Since $n$ is also a multiple of $d$, we have $\gcd(l d, \frac{n}{d} d)=d$ which is equivalent to $\gcd(l, \frac{n}{d})=1$. Since $m, we have $l<\frac nd$, so putting everything together, we are counting the positive numbers smaller then $\frac nd$ that are relatively prime to $\frac nd$. This is by definition the Euler phi function of $\frac nd$.

  • 0
    Thanks for your great answer!2011-11-18
1

For your question "how many necklaces are there of type n, with k 0's and n-k 1's?" OEIS A047996 gives the formula

$T(n, k)=\frac{1}{n} \sum_{d | (n, k)} \phi(d){n/d \choose k/d}.$

  • 0
    @Kou: I worked out the first 28 terms of the sequence and then looked it up. It is not my formula.2011-11-13