# How many combinations of $n$ balls of up to $n$ different colors are there?

How many ways can I select a set of $n$ colored balls if I have $n$ different colors to choose from and order does not matter? They can all be the same color or all different. I have no limit on the number of balls of any color.

For example, if I have $3$ colors, then there are $10$ possibilities: $$\{aaa, aab, aac, abb, abc, bbb, bbc, bcc, cca, ccc\}$$

The pattern seems to match OEIS A133148 for the first few values of $n$, but I'm not sure why.

Edit: I believe the binomial $\binom{2n-1}{n-1}$ proposed is the correct answer. I realized I was double counting some of the elements when I went to write out everthing.

• See stars and bars. – Arthur Mar 12 '18 at 22:05
• So, you're asking for the sequence of the number of solutions to $x_1+x_2+\dots+x_n=n$ where $x_i\geq 0$. This is $\binom{2n-1}{n-1}$. – Michael Burr Mar 12 '18 at 22:08

As proposed by the question you can consider the question to be asking for the non negative integral solutions of the equation $$x_1+x_2+x_3+\cdots+x_n=n$$
By star and bars method the answer reveals to be $$\binom {2n-1}{n-1}$$