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.

  • $\begingroup$ See stars and bars. $\endgroup$ – Arthur Mar 12 '18 at 22:05
  • 2
    $\begingroup$ 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}$. $\endgroup$ – 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$$

As already proposed by @Michael Burr in his comment

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.