Summation with combinations 
Prove that $n$ divides $$\sum_{d \mid \gcd(n,k)} \mu(d) \binom{n/d}{k/d}$$ for every natural number $n$ and for every $k$ where $1 \leq k \leq n.$ Note: $\mu(n)$ denotes the Möbius function.

I have tried numerous values for this summation and the result seems to hold true. For example, if $n = 20, k = 12$
$$\sum_{d \mid 4} \mu(d) \binom{20/d}{12/d} = \mu(1) \binom{20}{12}+\mu(2) \binom{10}{6}+\mu(4)\binom{5}{3} = \binom{20}{12}-\binom{10}{6}=125760,$$ which is divisible by $20$. Similarly if we tried it for any $k$ with $1 \leq k\leq 20$, we would have $20$ divide the expression.
How do I prove this result in the general case? That is, given any positive integer $n$, for all $k$ with $1 \leq k \leq n$ $$n \mid \sum_{d \mid \gcd(n,k)} \mu(d) \binom{n/d}{k/d}.$$
 A: A Combinatorial Approach (Hint)
Let $G:=C_n$ be the cyclic group of order $n$ generated by $g$ acting on the left on the set $X:=\{0,1\}^n$ by rotation:
$$g\cdot\left(x_1,x_2,\ldots,x_{n-1},x_n\right)=\left(x_n,x_1,x_2,\ldots,x_{n-1}\right)$$
for all $\left(x_1,x_2,\ldots,x_n\right)\in X$.  Then, if $Y\subseteq X$ consisting of $n$-tuples with $k$ occurrences of $1$'s, then $G$ also acts on $Y$.  An asymmetric $G$-orbit in $Y$ is a $G$-orbit in $Y$ that consists of exactly $n$ elements.  Prove that the number of asymmetric $G$-orbits in $Y$ is precisely $\displaystyle \frac{1}{n}\,\sum_{d\mid\gcd(n,k)}\,\mu(d)\,\binom{n/d}{k/d}$.  You may also show that the number of all $G$-orbits in $Y$ is $\displaystyle \frac{1}{n}\,\sum_{d\mid \gcd(n,k)}\,\phi(d)\,\binom{n/d}{k/d}$, where $\phi$ is Euler's totient function. 

Even more generally, the number of ways to arrange $n=k_1+k_2+\ldots+k_r$ objects on a circle, where there are $r$ mutually distinct types and the $j$-th type consists of $k_j$ identical objects, is $$\frac{1}{n}\,\sum_{d\mid\gcd\left(k_1,k_2,\ldots,k_n\right)}\,\phi(d)\,\binom{n/d}{k_1/d,k_2/d,\ldots,k_r/d}\,.$$
There are exactly
$$\frac{1}{n}\,\sum_{d\mid\gcd\left(k_1,k_2,\ldots,k_n\right)}\,\mu(d)\,\binom{n/d}{k_1/d,k_2/d,\ldots,k_r/d}$$
asymmetric arrangements.  For $r=n$ and $k_1=k_2=\ldots=k_n=1$, we retrieve the number of ways to arrange $n$ mutually distinct objects on a circle: $$\frac{1}{n}\,\binom{n}{\underbrace{1,1,\ldots,1}_{n\text{ ones}}}=(n-1)!\,.$$

P.S.  Just saw that arctic tern also posted an essentially the same solution.
A: I  would like  to present  the algebraic  aspects of  this  problem to
facilitate  understanding.   Suppose  we  have $r$  types  of  objects
(e.g. colors) with $k_1 + k_2 +  \cdots + k_r = n$ objects total where
$k_q$ gives  the number of objects of  color $q$ and we  ask about the
number of  necklaces we  can form with  these (rotational  symmetry as
opposed to dihedral symmetry).
Applying  the Polya  Enumeration Theorem  (PET) we  have  the cycle
index of the cyclic group
$$Z(C_n) = \frac{1}{n}\sum_{d|n} \varphi(d) a_d^{n/d}.$$
PET now yields for the  generating function of necklaces using at most
$r$ colors
$$q_n = \frac{1}{n}\sum_{d|n} 
\varphi(d) (A_1^d + A_2^d +\cdots+A_r^d)^{n/d}.$$
We  now  introduce  the  concept  of primitive  necklaces  $p_n$  i.e.
necklaces   on  at  most   $r$  colors   not  having   any  rotational
symmetry. Observe that an ordinary necklace is formed by concatenating
$d$ copies of a primitive necklace of size $n/d.$ (In fact it does not
matter  where we  open  the primitive  necklace ($n/d$  possibilities)
because when  we arrange the copies  of the opened  necklace we always
get  the same  necklace regardless  of where  we opened  the primitive
necklace.)
We   will   use  a   variety   of   Moebius   inversion  which   is
Inclusion-Exclusion on the divisor poset  in order to compute $p_n$ (a
generating function) and extract the desired coefficient. The possible
symmetries  that can  occur  correspond  to the  divisors  $f$ of  $n$
($f|n$).

Using  the variable $f$  we obtain  as explained  a segment  of length
$n/f$  being repeated  $f$ times,  copies  being placed  next to  each
other, thus creating $n/f$ cycles  of length $f.$.  These segments are
themselves  necklaces of  length $n/f.$  This means  that  the maximal
symmetry (smallest  size of  the constituent cycles)  is a  divisor of
$n/f$ because the segment could  itself be a concatenation of repeated
segments.  Ordering these in a poset by division yields an upside-down
instance  of the  divisor  poset  of $n$.   Note  that the  generating
function for the contribution from $f$ is not
$$\frac{1}{n/f}\sum_{d|n/f} 
\varphi(d) (A_1^d + A_2^d + \cdots + A_r^d)^{n/f/d}.$$
but rather
$$\frac{1}{n/f}\sum_{d|n/f} 
\varphi(d) (A_1^{df} + A_2^{df} + \cdots + A_r^{df})^{n/f/d}.$$
which represents the $f$ copies of the source segment.
We thus obtain by Inclusion-Exclusion
$$\sum_{f|n} \mu(f)
\frac{f}{n}\sum_{d|n/f} 
\varphi(d) (A_1^{df} + A_2^{df} + \cdots + A_r^{df})^{n/f/d}.$$
We put $fd=k$ so that $d=k/f$ to get
$$\sum_{f|n} \mu(f)
\frac{f}{n}\sum_{k/f|n/f} 
\varphi(k/f) (A_1^{k} + A_2^{k} + \cdots + A_r^{k})^{n/k}
\\ = \frac{1}{n}
\sum_{f|n} f\mu(f)
\sum_{k|n \wedge f|k} 
\varphi(k/f) (A_1^{k} + A_2^{k} + \cdots + A_r^{k})^{n/k}
\\ = \frac{1}{n}
\sum_{k|n} (A_1^{k} + A_2^{k} + \cdots + A_r^{k})^{n/k}
\sum_{f|k} f\mu(f) \varphi(k/f).$$
There are several ways to simplify the term
$$\sum_{f|k} f\mu(f) \varphi(k/f).$$
E.g. note that if
$$L_1(s) = \sum_{n\ge 1} \frac{n\mu(n)}{n^s}
= \prod_p \left(1-\frac{p}{p^s}\right) = \frac{1}{\zeta(s-1)}$$
and 
$$L_2(s) = \sum_{n\ge 1} \frac{\varphi(n)}{n^s} = 
\frac{\zeta(s-1)}{\zeta(s)}
\quad\text{because}\quad
\sum_{n\ge 1} \frac{1}{n^s} \sum_{d|n} \varphi(d)
= \zeta(s-1)$$
then
$$L_1(s) L_2(s) = \frac{1}{\zeta(s)}
\quad\text{and hence}\quad
\sum_{f|k} f\mu(f) \varphi(k/f) = \mu(k).$$ 
Substitute this into the formula to obtain
$$\frac{1}{n}
\sum_{k|n} \mu(k) (A_1^{k} + A_2^{k} +\cdots + A_r^{k})^{n/k}.$$
We seek
$$[A_1^{k_1} A_2^{k_2} \cdots A_r^{k_r}] \frac{1}{n}
\sum_{k|n} \mu(k) (A_1^{k} + A_2^{k} +\cdots + A_r^{k})^{n/k}.$$
Now observe that  the term in the variables  only produces powers that
are multiples of $k$ so we get the condition that
$$k|\gcd(n,  k_1, k_2,  \ldots k_r)$$
(we see that this produces a divisor of $n$) in which case we obtain a
contribution of (using $d$ for $k$ for readability)
$${n/d\choose k_1/d, k_2/d,\ldots k_r/d}$$
for an end result of
$$\frac{1}{n}\sum_{d|\gcd(k_1, k_2, \ldots k_r)} 
\mu(d) {n/d\choose k_1/d, k_2/d,\ldots k_r/d}.$$
We now  conclude by inspection  that the sum  is indeed a  multiple of
$n.$
A similar problem appeared at this
MSE link.
A: This proof uses symmetry (so, group actions) and a combinatorial interpretation of $v_{n,k}$.
Any group $G$ acts regularly on itself by (say left) multiplication. If $G$ acts on a set $X$, then there is an induced action of $G$ on the collection of $k$-subsets of $X$ (i.e. subsets of $X$ of size $k$). Let $v_{n,k}$ be the number of $k$-subsets of $\mathbb{Z}/n\mathbb{Z}$ with "no symmetry," i.e. no stabilizer with respect to this induced action. This is the collection of subsets $A$ for which $r+A=A$ implies $r=0$ in $\mathbb{Z}/n\mathbb{Z}$.
First, we prove the following:
$$\sum_{d\mid (n,k)}v_{n/d,k/d}=\binom{n}{k}.$$
Suppose $A$ is any subset of $\mathbb{Z}/n\mathbb{Z}$, and that its symmetry group $S$ has size $d=|S|$. (Note that $|S|=d$ is equivalent to $S=\frac{n}{d}\mathbb{Z}/n\mathbb{Z}$.) Since $S$ acts freely on $A$ we know $|S|$ divides $|A|$, and from Lagrange's theorem we know $|S|$ divides $|\mathbb{Z}/n\mathbb{Z}|$, i.e. $d$ divides $n$ and $k$. That $S$ acts freely on $A$ also implies that $A$ is a union of cosets of $S$.
The $k$-subsets of $\mathbb{Z}/n\mathbb{Z}$ with symmetry group of size $d$ correspond bijectively to $\frac{k}{d}$-subsets of $\mathbb{Z}/\frac{n}{d}\mathbb{Z}$ with trivial stabilizer. The correspondence is given in one direction by applying the projection $\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/\frac{n}{d}\mathbb{Z}$ and in the other direction by taking preimages. So if $M(n,k,d)$ denotes the collection of $k$-subsets of $\mathbb{Z}/n\mathbb{Z}$ with symmetry group of size $d$ we get
$$\binom{n}{k}=\sum_d |M(n,k,d)|=\sum_{d\mid n,k}|M(\frac{n}{d},\frac{k}{d},1)|=\sum_{d\mid \gcd(n,k)}v_{n/d,k/d}.$$
Hence my $v_{n,d}$s are the same as your $u_{n,d}$s. Finally, notice $\mathbb{Z}/n\mathbb{Z}$ acts freely on $M(n,d,1)$, so we find that $v_{n,d}$ is divisible by $n$.
