Combination With Finite Replacements

We have a pool of N number of balls.

There are: A number of white balls (W), B number of green balls (G), C number of blue balls (B), and D number of pink balls (P)

In how many ways (combinations) we can pick X number of balls from this pool? Is there a formula for something like this?

This is similar to combinations with replacement, but there are limitations to how many times a certain object can be replaced.

Solution 1:

The fully generalized problem is tedious to type out, so I will solve a simplified version of the problem for you and let you see the technique so that you can generalize further.

Suppose we have just three colors for balls instead of amounts $A,B,C$ respectively.

If we did not care about the limitations on the number of balls available, this becomes a traditional stars-and-bars problem, asking us to find the number of non-negative integer solutions to the system:

$$\begin{cases}x_1+x_2+x_3=X\\0\leq x_1\\0\leq x_2\\0\leq x_3\end{cases}$$

The solution of which would be $\binom{3+X-1}{3-1}$. (The $3$ here is in reference to the number of colors available)

Now, among these solutions we counted are some "bad" ones where we would have violated one or more of the conditions on the limitations on the number of available balls. So, for each individual available upper bound condition, calculate how many outcomes violate it and remove it from the total.

For example, if the upper bound condition were violated for the first color, then the number of outcomes violating that condition is the same as the number of non-negative integer solutions to the system

$$\begin{cases}x_1+x_2+x_3=X\\ A<x_1\\0\leq x_2\\0\leq x_3\end{cases}$$

After a change of variable, letting $y_1=x_1-A-1$ and $y_2=x_2$ and $y_3=x_3$ we see this is the same as the number of solutions to the system

$$\begin{cases}y_1+y_2+y_3=X-A-1\\0\leq y_1\\0\leq y_2\\0\leq y_3\end{cases}$$

to which the number of outcomes is $\binom{3+(X-A-1)-1}{3-1}$

Now... it could be possible that we had violated multiple conditions simultaneously, not just one at a time, so we must account for this in our calculations in the usual inclusion-exclusion style. Since we had just subtracted outcomes which violated at least one upper bound condition for each available upper bound condition, we must then add back the number which violate two upper bound conditions for each pair of upper bound conditions, then subtract again those which violate at least three, adding back those which violate four, and so on.

For this smaller problem then we get as a final answer:

$$\binom{3+X-1}{3-1} - \binom{3+(X-A-1)-1}{3-1}-\binom{3+(X-B-1)-1}{3-1}-\binom{3+(X-C-1)-1}{3-1}+\binom{3+(X-A-B-2)-1}{3-1}+\binom{3+(X-A-C-2)-1}{3-1}+\binom{3+(X-B-C-2)-1}{3-1} - \binom{3+(X-A-B-C-3)-1}{3-1}$$

Now you see why I didn't want to do the original problem where it has four colors instead of three, but the technique to solve would be essentially the same. If you were wanting to write down a generalized formula for this, you may want to play with notations for summing over elements of a set of sets, but given the way in which your question was written I wasn't sure that using that notation would be appropriate here.

Fully generalized with sigma-sum notation since you requested it...

First, some notation... let $[n]$ where $n$ is a natural number represent the $n$-element set $\{1,2,3,\dots,n\}$. (note: some authors prefer this to be the $n$-element set $\{0,1,2,\dots,n-1\}$ instead. It doesn't change anything here which interpretation you use)

Next, let $\binom{X}{k}$ where $X$ is a set and $k$ is a natural number represent the set of $k$-element subsets of $X$. That is to say $\binom{X}{k}=\{x\subseteq X~:~|x|=k\}$.

Finally, remember that you can iterate over an indexing set. For example, if $\Delta$ is an indexing set, then $\sum\limits_{\delta \in \Delta} f(\delta)$ represents the sum of $f(\delta)$ for each possible $\delta$ in the set. For example if $\Delta = \{1,5,7\}$ then $\sum\limits_{\delta\in \Delta} \delta^2 = 1^2 + 5^2 + 7^2$

Now... on to the generalized formula:

Let $A_1, A_2, A_3, \dots, A_k$ be the numbers of available balls of colors $a_1,a_2,a_3,\dots, a_k$ respectively. Let $X$ be the total number of balls that we select. Let all balls be indistinguishable apart from color and let order of selection of balls not matter. Then the total number of possible selections is:

$$\sum\limits_{i=0}^k \left((-1)^i\sum\limits_{\Delta \in \binom{[k]}{i}}\binom{\left(X-\sum\limits_{\delta\in\Delta}(A_\delta + 1)+k - 1\right)}{k-1}\right)$$