Deriving Combinatorics Formula

There are lots and lots of ways to derive the formula for the number of combinations. For specifically, if X is a set of n-elements how many k-subsets are there? This is a wonderful formula and it is highly elementary. Proofs of it are given in high-school.

I came up with another proof I never seen before. It is complete overkill, but I find group theoretic solutions to be nice. So here is a way to derive this formula by using group theory.

Really the result that we need is Burnside's counting formula. You can read about it here. If you would like to see some nice applications of this formula you can read it here.

Let S be a set of n-elements. And let X be the set of all k-tuples of S. The number of k-tuples is easy to count. It is just $n(n-1)...(n-k+1)=\frac{n!}{(n-k)!}$. Let G, the symmetric group on k numbers. We can define an action of G on X in an obvious manner. If $x=(x_1,...,x_k)$ is a k-tuple and $\sigma$ is a permutation then we can define the action of $\sigma$ on $x$ to be $(x_{\sigma(1)},...,x_{\sigma(n)})$. It is clear from this that the number of orbits is equal to the number of k-subsets. Since $G=k!$ it follows from the Burnside formula that the number of k-subsets is $\frac{n!}{k!(n-k)!}$ which works out to be the combinatorical formula.

That was way too easy. Let us make it more challenging. We can derive, using the same ideas, the generalized cominbatorics formula. Also known as multinomial coefficients. Let me say the problem first. Consider a set S of n elements. Let $k_1,k_2,...,k_r$ be positive integers with $\Sigma_i k_i = n$. We want to find the number of ways to put all elements of S into $r$ boxes so that there are $k_1$ in the first box, $k_2$ in the second box, and so forth.

Clearly, this generalizes the old combinatorics formula. The previous formula was with $r=2$, with $r_1=k$ and $r_2=n-k$. So it is fair to call this the generalized combinatorics formula.

Let us define X to be the set of all r-tuples where the i-th coordinate is an $k_i$-tuple. The intuition here is that the i-th coordinate represents the i-th box, and the i-th box has $k_i$ elements in it. There is a natural one-to-one correspondence between X and the set of all n-tuples of X. Thus, $X=n!$.

Now let $G = S_{k_1}\times S_{k_2}\times ... \times S_{k_r}$ where $S_{k_i}$ is the symmetric group on $k_i$ objects. Then we can define the action of G of X in a generalized manner as above. If $(\sigma_1,...,\sigma_r)$ is an element of G define its action on the r-tuple $(x_1,...,x_r)$ to be $(\sigma_1x_1,...,\sigma_rx_r)$ where $\sigma_ix_i$ is the action of $\sigma_i$ on the $k_i$-tuple defined above. It is clear that no non-trivial element of G fixes all of X. Therefore, by Burnside's formula we get that the number of orbits is given by $$\frac{n!}{G} = \frac{n!}{(k_1)!\cdot ... \cdot (k_r)!}$$. And this proves the generalized binomial theorem because the number of $r$ decompositions of S into $k_1$,...,$k_r$ boxes is in natural one-to-one correspondence with the number of such orbits.

Here is a combinatorics problem that is currently unsolved. How many different ways are there to derive the combinatorics formula?