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

Solution 1:

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.

Solution 2:

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.

Solution 3:

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