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.
 A: 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}$$
A: 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.
