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?

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

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

-
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

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

-
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