How many ways to colour $n$ balls with $k$ colours? Repeating and omitting colours is fine, and order is not important.
$$\sum_{i=1}^k \binom{n-1}{i-1} \binom{k}{i} $$
This is what I came up with. It feels like it is a far more complicated than it needs to be. Here's my proof:
The $i$-composition of $n$ is equal to $\displaystyle \binom{n-1}{i-1}$.
A $3$-composition of $n$ would be $a + b + c = n$, where each term on the LHS is equal to the number of balls with a given colour. Assuming $a \ne b \ne c$, there's other compositions as well, like $b + a + c$ and $c + a + b$. They will constitute different possibilities for the colouring of the balls, as the possibilities are differing in the respective quantities of balls with a certain colour.
Given that one can omit colours, one must first start with the $1$-composition of $n$, before increasing the number of colours included, up to the total number of $k$ colours.
When in the $i$th iteration, one is colouring with $i$ out of $k$ colours, creating $\binom{k}{i}$ possibilities, as one is choosing $i$ colours from a total of $k$ colours.
Is the proof and solution correct? If so, are there simpler solutions and proofs for this? I could construct a pretty similar proof using $k$-bounded weak compositions, but not sure it would differ much in simplicity.
Best Answer
Your work is completely correct. Here is an alternate solution.
Since order does not matter, a color assignment is uniquely specified by how many balls there with each color. Letting $x_1,\dots,x_k$ be the number of balls with each color, this means counting colorings is equivalent to counting nonnegative integer solutions to $$ x_1+\dots+x_k=n, $$ which is easily doable using stars and bars.
Alternatively, if you write the summation you found as $$ \sum_{i=1}^k \binom{n-1}{i-1}\binom k{k-i}=\sum_{i=0}^{k-1}\binom{n-1}{i}\binom{k}{k-1-i}, $$ then you can simplify that summation using Vandemonde's identity to a single binomial coefficient.