# Number of combinations of size $k$ of elements in a multiset with finite multiplicites

Suppose I have 3 types of balls each in varying amounts, e.g. 3 Red (R) balls, 3 Green (G) balls, and 2 Blue (B) balls. How many combinations of size $$k, k\leq n$$ where $$n$$ is the total number of balls (in this case 8), can be made?

For example, suppose $$k = 2$$, then we can make the combinations: RR, RG, RB, GG, GB, and BB of which there are 6. Note that the set RG and GR are the same in my example.

It seems almost like a stars and bars problem, but I don't think it applies here. Is there a closed form solution to this problem or a way to calculate the number of combinations that doesn't involve exhaustively generating every possible $$k$$-combination?

My ultimate goal is to sum over all $$1\leq k\leq n$$, if it's easier to calculate that number rather than for a specific $$k$$, that would be useful to know too.

You can use generating functions which are not difficult to learn at a rudimentary level.

Generating function for $$0-3$$ red balls = $$1+x +x^2 +x^3$$

Generating function for $$0-3$$ green balls = $$1+x +x^2 +x^3$$

Generating function for $$0-2$$ blue balls = $$1+x +x^2$$

Next, find the coefficient of $$[x^k]$$ in the expansion of $$(1+x +x^2 +x^3)^2(1+x+x^2)$$

eg for $$k=3$$ the answer is $$9$$

Finally, you can sum up the answers for $$k = 1\; to\; n$$

Actually, you can get all the information you need by simply expanding the generating function at one go, and extracting whatever coefficients you need

• This worked out beautifully. It turns out that one doesn't even need to find in general the coefficient of $[x^k]$, just evaluating the polynomial at $1$ does the trick. Moreover, it follows that simply the product of the number of balls of each color plus one gives you the sum of the coefficients from $k=1$ to $n$. (3+1)(3+1)(2+1) = 48. Thank you! Commented Jun 14, 2023 at 19:04
• You're welcome, Glad to have been of help ! $\;\;$ ;) Commented Jun 14, 2023 at 19:33