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

139 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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$$

As already proposed by @Michael Burr in his comment

By star and bars method the answer reveals to be $$\binom {2n-1}{n-1}$$