Vrftjkry

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.

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.

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

Let $|N|=n$, $M=N^{k}/sim$ and:
$$x,yin N^k, x sim yLeftrightarrowexists 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 -1choose k}$

Induction by k:

Trivially: $$|N^1/sim|overset{Burnside}=frac{sum_{sigmain S^1}|N|^1}{1!}=|N|=n={1+n-1choose 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), & hleq 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},sigmamapsto (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 $hneq 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_{sigmain S^k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|+sum_{sigmain 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 $hin {1,...,k-1}$ and $xin 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_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}=frac{sum_{sigmain 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_{sigmain S^{k},sigma(k)neq k}|F_k(sigma)|}{k!}=frac{sum_{sigmain S^{k},sigma(k)= i, i=1}^{k-1}|F_k(sigma)|}{k!}=frac{sum_{i=1}^{k-1}sum_{sigmain 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_{sigmain S^{k},sigma(k)=k}|F_k(sigma)|}{k!}+frac{sum_{sigmain 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}$$