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


3 Answers 3


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

  • $\begingroup$ So would n!/(a!b!c!d!e!) actually be the general form? $\endgroup$
    – SumNeuron
    Apr 5, 2021 at 11:49
  • $\begingroup$ 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. $\endgroup$
    – SumNeuron
    Apr 5, 2021 at 11:50
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 5, 2021 at 12:01
  • $\begingroup$ and if it is ok to have 0 of one or more marble colors? Then differ to user's generating function? $\endgroup$
    – SumNeuron
    Apr 6, 2021 at 12:47
  • $\begingroup$ Well, if you can have $0$ of one or more marble colors, then it'll simply be $5^{10}$ $\endgroup$ 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.


Adding some explanation to the answer of @user.

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


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .