Also known as Balls-and-urns, stars-and-bars. How many ways can one distribute $k$ indistinguishable balls into $n$ distinguishable urns? > [!NOTE] Lemma > The number of equivalence classes in the set of functions from $[k]$ to $[n]$, where two functions $f_{1},f_{2}$ are considered equivalent if $f_{1}=f_{2}\circ \pi$ for some $\pi\in \text{Sym}([k])$; is given by $\left( \binom{n}{k} \right) := \binom{n+k-1}{k}.$ ###### Combinatorial proof There is a bijection to the strings of $k$ stars and $n-1$ bars: the solutions to $a_{1}+a_{2}+\dots +a_{n}=k$ where $a_{i}$ are non-negative integers. ###### Generating function proof ^0c2f94 Let $f(k,n)$ denote the number of $\mathfrak{S}_{k}$-inequivalent $n$-colourings of $[k]$. Then [^1] $\sum_{k\geq 0 } f(k,n) x^{k} = \frac{1}{(1-x)^n}.$ The RHS can be expanded [^2] using Taylor's theorem as $\frac{1}{(1-x)^{n}} = \sum_{k\geq 0} \binom{n+k-1}{k}x^{k}$so $f(n,k) = \binom{n+k-1}{k}.$ # Bibliography [^1]: [[Pólya's Enumeration Theorem.pdf]] (p. 11). [^2]: [[(Undergraduate Texts in Mathematics) Richard P. Stanley - Algebraic Combinatorics_ Walks, Trees, Tableaux, and More-Springer (2013).pdf]] (p. 87).