Applying Burnside's lemma to show there are $k+n-1 \choose k-1$ ways to store n stars in k bins?

Question

Usually it is proven using multisets I think, but I wondered how Burnside's lemma could be applied. Everytime I tried to wrap it around my head the indices didn't seem to fit. So I TeXed it and eventually I found out.

Answer 1

EDIT: Substitute n=k, k=n. This proof follows the urn model -intuition.

Let $|N|=n$, $M=N^{k}/\sim$ and: $$x,y\in N^k, x \sim y\Leftrightarrow\exists \sigma \in S^k: (x_1,...,x_k)=(y_{\sigma(1)},...,y_{\sigma(k)})$$ Obviously M is the orbital space of a group action: $\sigma.(x_1,...,x_k)=(x_{\sigma(1)},...,x_{\sigma(k)})$.

To proof: $|N^k/\sim|={k+n -1\choose k}$

Induction by k:

Trivially: $$|N^1/\sim|\overset{Burnside}=\frac{\sum_{\sigma\in S^1}|N|^1}{1!}=|N|=n={1+n-1\choose 1}$$

$k-1 \rightarrow k:$

Each $\sigma$ in $S^{k-1}$ can be naturally identified by $\sigma'\in S^k$ $$\sigma'(h)=\left\{\begin{array}{cl} \sigma(h), & h\leq k-1\\ k, & h=k \end{array}\right.$$ $$ \forall h \in \{1,...,k\}:\omega_h:S^{k-1}\rightarrow \{ \sigma'' \in S^k:\sigma''(h)=k\},\sigma\mapsto (\sigma'(h), k) \circ \sigma' $$ $(\sigma(h) k)$ is the transposition, that swaps $\sigma(h)$ with k. $\omega_h$ is bijective(trivially injective, surjective with inverse $\sigma \mapsto ((\sigma(h),\sigma(k))\sigma)|_{\{1,...,k-1\}}$, which is well defined, because $\sigma(h)=k$ and $\sigma(k) \in \{1,..k-1\}$ for $h\neq k$)

Let $F_k$ be: $S^k \rightarrow N^k, F_k(\sigma)=\{x \in N^k: \sigma(x)=x\}$

$$|N^k/\sim|=\frac{\sum_{\sigma\in S^k}|F_k(\sigma)|}{k!}=\frac{\sum_{\sigma\in S^{k},\sigma(k)=k}|F_k(\sigma)|+\sum_{\sigma\in S^{k},\sigma(k)\neq k}|F_k(\sigma)|}{k!}$$

Moreover: $$F_k(\omega_k(\sigma))=F_{k-1}(\sigma)\times N \Rightarrow |F_{k}(\omega_k(\sigma))|=|F_{k-1}(\sigma)|n$$

Bijectivity of transposition leads to: $x \in F_k(\omega_h(\sigma)) \Rightarrow (x_1,...,x_{k-1})\in F_{k-1}(\sigma)$. For each $h\in \{1,...,k-1\}$ and $x\in F_{k-1}(\sigma)$ the k-th compononent is uniquely determined, by $x_{\omega_h(\sigma(k))}$.Since $\omega_h(\sigma(k))=\sigma(h)$ and $x_{(\omega_h \circ sigma)^{-1}(k)}=x_h=x_{\sigma(h)}=x_{\omega_h(\sigma(k))}=x_k$, $(x,x_{\omega_h(\sigma(k))})$ is actually in $F_k(\omega_h(\sigma))$. It follows, that: $$F_k(\omega_h(\sigma))=\{(x,x_{\omega_h(\sigma(k))}) : x \in F_{k-1}(\sigma)\} \Rightarrow |F_{k}(\omega_h(\sigma(k)))|=|F_{k-1}(\sigma)|$$

This yields: $$\frac{\sum_{\sigma\in S^{k},\sigma(k)=k}|F_k(\sigma)|}{k!}=\frac{\sum_{\sigma\in S^{k-1}}|F_{k-1}(\omega_k(\sigma))|n}{k!}$$ $$\overset{IH}{=}\frac{n(k-1)!{k+n-2 \choose k-1}}{k!}=\frac{n-1}{k}{k+n-2 \choose k-1}+\frac{1}{k}{k+n-2 \choose k-1}$$$$={k+n-2 \choose k}+\frac{1}{k}{k+n-2 \choose k-1}$$ Now we are taking a closer look at the latter guys $\forall h \in\{1,..k-1\}:$ $$\frac{\sum_{\sigma\in S^{k},\sigma(k)\neq k}|F_k(\sigma)|}{k!}=\frac{\sum_{\sigma\in S^{k},\sigma(k)= i, i=1}^{k-1}|F_k(\sigma)|}{k!}=\frac{\sum_{i=1}^{k-1}\sum_{\sigma\in S^{k-1}}|F_{k-1}(\omega_i(\sigma))|}{k!}$$

$$\overset{IH}{=}\frac{\sum_{i=1}^{k-1}(k-1)!{k+n-2 \choose k-1}}{k!}=\frac{k-1}{k}{k+n-2 \choose k-1 }$$ We conclude: $$|N^k/\sim|=\frac{\sum_{\sigma\in S^{k},\sigma(k)=k}|F_k(\sigma)|}{k!}+\frac{\sum_{\sigma\in S^{k},\sigma(k)\neq k}|F_k(\sigma)|}{k!}$$ $$={k+n-2 \choose k}+\frac{1}{k}{k+n-2 \choose k-1}+ \frac{k-1}{k}{k+n-2 \choose k-1 }$$ $$={k+n-2 \choose k}+{k+n-2 \choose k-1 }={k+n-1 \choose k}$$

Answer 2

The $k$ bins can all be distinguished, so we're dealing with the trivial group whose one element is the identity permutation over $k$ elements.

Thus the cycle index is $Z = t_1^k$. There's one way of putting one star in a bin, one way of putting two stars, etc. so the final generating function is $f(z) = \left(\frac{1}{1-z}\right)^k = (1-z)^{-k}$. Then the term with $z^n$ is $\frac{(-k)^{\underline n}}{n!}(-z)^n$ with coefficient $$\frac{(-k)^{\underline n}}{n!}(-1)^n = \frac{(k+n-1)^{\underline n}}{n!} = \binom{k+n-1}{n}$$

---

Note that this is also $\binom{k+n-1}{k-1}$, so maybe the reason the indexes always came out wrong for you is that you were trying to prove a statement with an out-by-one error.