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?


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<n$, 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$.

  • $\begingroup$ I was wondering why$$\frac{1}{n}\sum_{d | n} (1+x^{n/d})^d = \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).$$ $\endgroup$ – Kou Nov 17 '11 at 23:57
  • $\begingroup$ @Kou In the first equality, the written text that you omitted is part of the formula, in the second equality, I have made a variable change from $d$ to $n/d$ to get to the expression from the other answer. $\endgroup$ – Phira Nov 18 '11 at 0:01
  • $\begingroup$ Well, could you show me that why the first equality is true? I put in some particular n and k, and found it not working. $\endgroup$ – Kou Nov 18 '11 at 0:56
  • $\begingroup$ @Kou: The text you omitted, namely "number of m < n having pgcd d with n" is part of the formula. $\endgroup$ – Phira Nov 18 '11 at 11:37
  • $\begingroup$ Thanks, what does "pgcd" mean? I am still curious about how Euler's $\phi$ function appears. $\endgroup$ – Kou Nov 18 '11 at 14:00

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}.$$

  • $\begingroup$ It does depend on whether reflections count or not: if you think 001011 is the same necklace as 110100 then OEIS A052307 may be what you are looking for, but that does not give such a neat formula. $\endgroup$ – Henry Nov 13 '11 at 2:43
  • $\begingroup$ Could you explain this formula? How to get it? $\endgroup$ – Kou Nov 13 '11 at 3:12
  • $\begingroup$ @Henry, the way I learned it, necklaces can only be rotated, bracelets can also be reflected (turned over). I'm not sure that convention is universal. $\endgroup$ – Gerry Myerson Nov 13 '11 at 3:20
  • $\begingroup$ @Kou: I worked out the first 28 terms of the sequence and then looked it up. It is not my formula. $\endgroup$ – Henry Nov 13 '11 at 3:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.