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?

  • 1
    Last part doesn't make sense - type $m$ means $m$ things, $k$ zeros and $n-k$ ones means $n$ things.2011-11-13
  • 0
    Does http://mathforum.org/library/drmath/view/56198.html help you answer your (first) question?2011-11-13
  • 0
    See also the last part of 18.2 at http://ocw.mit.edu/courses/mathematics/18-310c-principles-of-applied-mathematics-fall-2007/lecture-notes/countingpatterns.pdf2011-11-13
  • 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
    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).$$2011-11-17
  • 0
    @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.2011-11-18
  • 0
    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.2011-11-18
  • 0
    @Kou: The **text you omitted**, namely "number of m < n having pgcd d with n" is part of the formula.2011-11-18
  • 0
    Thanks, what does "pgcd" mean? I am still curious about how Euler's $\phi$ function appears.2011-11-18
  • 0
    @Kou I am sorry, it should have been gcd, pgcd is the French abbreviation. I have edited an explanation of the equality at the bottom of the post.2011-11-18
  • 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
    It does depend on whether reflections count or not: if you think 001011 is the same necklace as 110100 then [OEIS A052307](http://oeis.org/A052307) may be what you are looking for, but that does not give such a neat formula.2011-11-13
  • 0
    Could you explain this formula? How to get it?2011-11-13
  • 0
    @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.2011-11-13
  • 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