# How many differnent ways to pick n marbles of five colors at random?

Suppose you have bag of $$p$$ marbles with $$a$$ marbles of a color $$A$$, $$b$$ of color $$B$$, and so on to $$e$$ marbles of $$E$$ i.e. $$p=a+b+c+d+e$$. Consequentially for any singular type of marble e.g. $$A$$, $$0\le a \le p$$ so long as $$p=a+b+c+d+e$$.

While there are $$\binom{p}{n}$$ ways to pick $$n$$ marbles out of $$p$$ marbles, I am more interested in figuring out, if given $$a$$, $$b$$, $$c$$, $$d$$, and $$e$$ how many unique ways there are to do this. For example, suppose $$n=2$$, $$p=10 = a =10, b=c=d=e=0$$. There are $$\binom{p}{n}$$ ways for me to get two marbles, but no matter which two I choose I will have two marbles of type $$A$$, so there is really only one result.

I guess then my question is more so inverted. Given that I am looking to choose $$n$$ how many ways can I construct $$n$$ from $$a, b, c, d$$, and $$e$$.

My first thought was the multinomial coefficient

$$\frac{n!}{a!b!c!d!e!}$$

but that clearly is incorrect. What am I forgetting? Looking at this question it seems that I have to do this for the variable number of ways this could occur:

$$5(\binom{n}{n} + \binom{n}{n-1}*4\binom{n}{n-n+1} + \binom{n}{n-2}*8\binom{n}{n-n+1}*4\binom{n}{n-n+2} + \dots)$$ but that only works assuming that there are $$n$$ of each type of marble....

You need to be crystal clear about the multinomial coefficients.

For $$10$$ marbles, if you want $$4$$ of a, $$3$$ of b and one each of $$c,d,e,$$

the multinomial coefficient $$\dfrac{10!}{4!3!1!1!1!}$$ indeed gives the answer you desire,

but if you instead specify $$3$$ of one color, $$2$$ of another, and $$1$$ each of the remaining colors, you need to multiply the above by another multinomial coefficient, $$\dfrac{5!}{1!1!3!}$$ to take into account that the pattern could be generated with different colors in many ways.

The answer could, of course, be abbreviated as $$\dfrac{10!}{4!3!}\cdot\dfrac{5!}{3!}$$

but I recommend the full form including $$1!$$ and (if it occurs), $$0!$$ to give a sort of double check that the numerator and denominator tally.

Supposing you want at least one of each color, you will first have to form all patterns, eg $$6,1,1,1,1\quad5,2,1,1,1\quad4,3,1,1,1\;$$(the pattern we discussed), and continue down to $$2,2,2,2,2$$, compute separately for each case and add up

But there is a shortcut using inclusion-exclusion, viz

$$5^{10} - \binom514^{10} + \binom523^{10} - \binom532^{10} + \binom541^{10}$$

An even shorter way (if you know about Stirling numbers of the second kind, and have tables of such numbers) is to compute $$S2(10,5)*5!$$

• So would n!/(a!b!c!d!e!) actually be the general form? Apr 5, 2021 at 11:49
• Sorry what I am specifically asking is how many ways I can make N, given the specific values for a,...,e. Your example (4, 3, 1, 1, 1), is one such outcome for N=10. Apr 5, 2021 at 11:50
• OK, supposing you want at least one of each color, you will first have to form all patterns, eg $6,1,1,1,1\; 5,2,1,1,1\; 4,3,1,1,1\;$(the pattern we discussed), and continue down to $2,2,2,2,2$ compute separately for each case and add up. Or there is another way which I am adding in the answer. Apr 5, 2021 at 12:01
• and if it is ok to have 0 of one or more marble colors? Then differ to user's generating function? Apr 6, 2021 at 12:47
• Well, if you can have $0$ of one or more marble colors, then it'll simply be $5^{10}$ Apr 6, 2021 at 14:34

In terms of generating functions the number you are looking for is: $$[x^n]\prod_{i=1}^k \sum_{j=0}^{N_i}{x^j},$$ where $$k$$ is the number of colors, $$N_i$$ is the number of marbles of the $$i$$-th color, and $$[x^n]$$ denotes the coefficient at $$x^n$$ in the power expansion of the function.

Let us embed the question into a Ordinary Generating Function (OGF). See this related question for EGF in case order matters to you: 4 digit combinations of 12333210, 3 letter combinations of MISSISSIPPI

Simpler Problem: What you need is to find the coefficient of $$x^n$$ in

$$(1+x+x^2+\dots+x^a)\times(1+x+x^2+\dots+x^b)\times\dots\times(1+x+x^2+\dots+x^e)$$

Explanation: The number of ways to pick n marbles of the 5 types, is the same as the number of ways to pick n $$x's$$ from each of the 5 polynomial sub-expressions. This embedding ensures,

• You can't pick more than $$a$$ number of x's of type A, and similarly for the other types.
• You pick a total of n $$x$$'s across the generating polynomials (as you want coefficient of $$x^n$$).
• You cannot pick a negative number of any type.
• The expression is unique and therefore well-defined.
• Each way of picking $$x^n$$ from the 5 sub-polynomials adds 1 to the coefficient of $$x^n$$, and the total number of ways of picking $$x^n$$ is therefore the coefficient of $$x^n$$ in the full expression.

Thus the embedding is valid as these above properties are equivalent to the problem you posed.