Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Last part doesn't make sense - type $m$ means $m$ things, $k$ zeros and $n-k$ ones means $n$ things. –  Gerry Myerson Nov 13 '11 at 2:28
    
Does mathforum.org/library/drmath/view/56198.html help you answer your (first) question? –  Gerry Myerson Nov 13 '11 at 2:32
    
See also the last part of 18.2 at ocw.mit.edu/courses/mathematics/… –  Gerry Myerson Nov 13 '11 at 2:36
    
OK, now the last part makes sense, but how is the question any different from the first part? –  Gerry Myerson Nov 13 '11 at 3:17
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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).$$ –  Kou Nov 17 '11 at 23:57
    
@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. –  Phira Nov 18 '11 at 0:01
    
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. –  Kou Nov 18 '11 at 0:56
    
@Kou: The text you omitted, namely "number of m < n having pgcd d with n" is part of the formula. –  Phira Nov 18 '11 at 11:37
    
Thanks, what does "pgcd" mean? I am still curious about how Euler's $\phi$ function appears. –  Kou Nov 18 '11 at 14:00
show 2 more comments

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

share|improve this answer
    
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. –  Henry Nov 13 '11 at 2:43
    
Could you explain this formula? How to get it? –  Kou Nov 13 '11 at 3:12
    
@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. –  Gerry Myerson Nov 13 '11 at 3:20
    
@Kou: I worked out the first 28 terms of the sequence and then looked it up. It is not my formula. –  Henry Nov 13 '11 at 3:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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