(Elementary?) combinatorial identity expressing binomial coefficients as an alternating sum over permutations.

Question

Background

I came up with this while trying to find a sort of high-level exposition of the exterior algebra of a vector space. Let $V$ be a vector space of dimension $n$ over $\mathbb{C}$, and let $k \in \mathbb{N}$. One picture of $\Lambda^k(V)$, the $k^{th}$ exterior power of $V$, is as the space of totally antisymmetric tensors in $V^{\otimes k}$.

This can be constructed as follows. Let $$ \rho : S_k \to \mathrm{End}(V^{\otimes k})$$ be the representation given by $$ \rho_\pi (v_1 \otimes \dots \otimes v_k) = v_{\pi(1)} \otimes \dots \otimes v_{\pi(k)},$$ and then let $\sigma$ be the alternating form of this representation, i.e. $\sigma_\pi = sgn(\pi) \rho_\pi$. The total antisymmetrizer is the map $$A_k = \frac{1}{k!} \sum_{\pi \in S_k} \sigma_\pi.$$ This is the projection onto the space of totally antisymmetric tensors, and so we can calculate the dimension of $\Lambda^k(V)$ simply by taking the trace of the map $A_k$. It turns out that $$\mathrm{tr}(\rho_\pi) = n^{cyc(\pi)},$$ where by $cyc(\pi)$ I mean the number of cycles in the factorization of $\pi$ into disjoint cycles (including cycles of length 1). This can be shown as follows. Take a basis $\{ e_1, \dots, e_n \}$ of $V$ and then form the basis for $V^{\otimes k}$ consisting of all vectors $ e_{i_1} \otimes \dots \otimes e_{i_k}$ such that $1 \le i_1, \dots, i_k \le n $. Then $$ \rho_\pi(e_{i_1} \otimes \dots \otimes e_{i_k}) = e_{i_{\pi(1)}} \otimes \dots \otimes e_{i_{\pi(k)}},$$ so this basis vector contributes 1 to the trace of $\rho_\pi$ if and only if $i_j = i_{\pi(j)}$ for all $1 \le j \le k$, i.e. if and only if all labels are constant over cycles of $\pi$. Since there are $n$ choices for each label, this gives $$\mathrm{tr}(\rho_\pi) = n^{cyc (\pi)},$$ and thus $$ \mathrm{tr}(A_k) = \frac{1}{k!} \sum_{\pi \in S_k} sgn(\pi) n^{cyc (\pi)}.$$

---

Question: does anybody know a simple combinatorial proof that $$ \frac{1}{k!} \sum_{\pi \in S_k} sgn(\pi) n^{cyc (\pi)} = \binom{n}{k},$$ where (in case you didn't read the long-winded background that I wrote), $cyc(\pi)$ is the number of cycles in the disjoint cycle factorization of $\pi$.

Answer 1

$n(n-1)...(n-(k-1))$ is the number of injective functions from a set of size $k$ to a set of size $n$. We can count these using inclusion-exclusion: first include all such functions, of which there are $n^k$. Then, for each transposition $(ij)$ in $S_k$, exclude all the functions such that $f(i) = f(j)$, of which there are $n^{k-1}$. And so forth. This alternating sum cancels out all functions which are invariant under a permutation of the domain, so the only ones left are the injective ones.

There's a much easier way to prove an equivalent identity, which is

$$\frac{1}{k!} \sum_{\pi \in S_n} n^{\text{cyc}(\pi)} = {n+k-1 \choose k}.$$

This identity is equivalent because the sign of a permutation is determined by the parity of its number of cycles, and it corresponds to replacing "antisymmetric" by "symmetric" everywhere in your question. But this identity has an obvious proof by Burnside's lemma: the LHS and RHS both count the number of orbits of functions $[k] \to [n]$ under permutation of the domain. (This is a special case of a result I call the baby Polya theorem.)

Both identities are in turn a special case of the exponential formula, which one can state as a generating function identity for the cycle index polynomials of the symmetric groups. I explain some of this here. The relevant specializations are

$$\frac{1}{(1 - t)^n} = \exp \left( nt + \frac{nt^2}{2} + ... \right)$$

and

$$(1 + t)^n = \exp \left( nt - \frac{nt^2}{2} \pm ... \right).$$