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

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.

• Stars and Bars is the usual way that I see this shown. – robjohn Nov 17 '18 at 16:59
• The wikipedia-proof is taking advantage of Multisets if it were to be formalised, isn't it? – Martin Erhardt Nov 17 '18 at 19:56
• It is counting the number of ways to arrange $n$ stars and $k-1$ bars among each other. – robjohn Nov 17 '18 at 20:08

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.

• Could you please elaborate on the set you are operating on and how? Operating with a cyclic group is obviously way more elegant, than with the Symmetric group -even though you do not seem to use burnside's lemma. – Martin Erhardt Nov 17 '18 at 18:30
• Strictly I'm using Pólya's enumeration theorem, which is a generalisation of not-Burnside's lemma. $G$ contains only the identity element of $S_k$, so the sum is trivial. – Peter Taylor Nov 17 '18 at 18:55
• I'am reliefed to see, that I could not have come up with that with my limited knowledge :). I wonder: Would it be possible to stay that short, without this strong theorem? – Martin Erhardt Nov 17 '18 at 19:11
• qchu.wordpress.com/2009/06/16/… might achieve that, although I personally could use an extra step or two of explanation. (The next two posts in the series may also interest you). – Peter Taylor Nov 18 '18 at 8:48

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

• The base case of the induction is wrong. Trivially, if you only have one bin there's only one way to store the stars. – Peter Taylor Nov 17 '18 at 17:45
• Oh I thought about pulling n balls out of an urn k - times neglecting sequence with replacement. This is dual in a way to the stars-bins-approach. – Martin Erhardt Nov 17 '18 at 18:09
• So the proof is actually correct, but I confused two different models of the same problem. – Martin Erhardt Nov 17 '18 at 18:13