Intereting Posts

Proof that the real numbers are countable: Help with why this is wrong
Area of convex n-gon using triangles
Android devices for reading textbooks and writing math by hand?
The image of an ideal under a homomorphism may not be an ideal
Any two points in a Stone space can be disconnected by clopen sets
How to write $\aleph$ by hand
Show that a convex compact set in $R^2$ can be cut into 4 sets of equal area by 2 perpendicular lines
Prove that the extreme point of a function is at x = n?
Does there exist an integer $x$ satisfying the following congruences?
shortest distance between two points on $S^2$
Calculation of $x$ in $x \lfloor x\lfloor x\lfloor x\rfloor\rfloor\rfloor = 88$
Can the isometry group of a metric space determine the metric?
$A ⊂ B$ if and only if $A − B = ∅$
How many copies of $C_4$ are there in $K_n$
Set of All Groups

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.

- (Alternate Answer To) How Many Binary Strings Of At most Length $6$ have no consecutive zeros
- Mathematical proof for long-term behavior of a sequence of integer vectors
- Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
- How do I tackle this combinatorics problem about married couples around a table?
- In how many ways can $10$ letters be placed in $10$ addressed envelope such that exactly $9$ letters are in correct envelope?
- Decorate Tables

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

- Transforming Diophantine quadratic equation to Pell's equation
- Possible areas for convex regions partitioning a plane and containing each a vertex of a square lattice.
- Why do we use this definition of “algebraic integer”?
- An identity involving the Pochhammer symbol
- Using floor, ceiling, square root, and factorial functions to get integers
- How this operation is called?
- Building on work from previous MSE question 2306650 (Re: Odd Perfect Numbers)
- Why do graph degree sequences always have at least one number repeated?
- Sum of an infinite series of fractions
- Non-squarefree version of Pell's equation?

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

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

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.

- parallel postulate of Euclidean geometry and curvature
- Integer Solutions to $x^2+y^2=5z^2$
- Cohomology group of free quotient.
- The limit of binomial distributed random variable
- Link between Gram Matrix and volume of parallelpiped question – Determinant
- Pairs of points exactly $1$ unit apart in the plane
- Divisibility by Quadratics
- Uniqueness of compact topology for a group
- Almost sure convergence of random variables
- How to plot a phase portrait for this system of differential equations?
- What operations is a metric closed under?
- Are derivatives defined at boundaries?
- Generalizing $\sum \limits_{n=1}^{\infty }n^{2}/x^{n}$ to $\sum \limits_{n=1}^{\infty }n^{p}/x^{n}$
- Intuition behind negative combinations
- The empty function and constants