1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Martin Erhardt Nov 17 '18 at 18:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Taylor Nov 17 '18 at 18:55
  • $\begingroup$ 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? $\endgroup$ – Martin Erhardt Nov 17 '18 at 19:11
  • 1
    $\begingroup$ 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). $\endgroup$ – Peter Taylor Nov 18 '18 at 8:48
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The base case of the induction is wrong. Trivially, if you only have one bin there's only one way to store the stars. $\endgroup$ – Peter Taylor Nov 17 '18 at 17:45
  • $\begingroup$ 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. $\endgroup$ – Martin Erhardt Nov 17 '18 at 18:09
  • $\begingroup$ So the proof is actually correct, but I confused two different models of the same problem. $\endgroup$ – Martin Erhardt Nov 17 '18 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.