Choosing $r$ things from a set containing $l$ things of one kind, $m$ things of a different kind, $n$ things of a third kind,...

Question

Here is a statement from a textbook that I'm referring to:

From a set containing $l$ things of one kind, $m$ things of a different kind, $n$ things of a third kind and so on, the number of ways of choosing $r$ things out of this set of objects is the coefficient of $x^r$ in the expansion of $$(1+x+x^2+x^3+...+x^l)(1+x+x^2+x^3+...+x^m)(1+x+x^2+x^3+...+x^n).$$

Can someone please explain the intuition behind this? How can it be derived?

Answer 1

The expansion of that expression does the same as picking items from the groups. You can expand the expression in one huge step: choosing one sub-expression from each bracket and summing up all possibilities of how you can do it. Each sub-expression refers to how many things you choose from given group. $1$ means not choosing anything, $x$ means choose 1 thing, $x^2$ means choose two things etc.. And the exponent of x will show you how many things you have already picked.

Noone forces you to perform the expansion in one step, so you can do it in multiple steps and you will receive the same.

This formula allows you to add more constraints. For example, if you don't want the things l being selected exactly three times, you delete the $x^3$ from corresponding bracket. Or if you want each item being chosen at least once, you delete the $1$ from all brackets.

Answer 2

Look at it in this way:

"Multiplication means 'and' and addition means 'or'". Now let's have a look at the given expression:

$$(1+x+x^2+x^3+...+x^l)(1+x+x^2+x^3+...+x^m)(1+x+x^2+x^3+...+x^n).$$

So read it as you have to select $r$ elements from a set of $l$ objects $*$ (i.e. and) a set of $m$ objects $*$ (i.e. and) a set of $n$ objects combined. Now every power represents the number of things you have chosen. Power of $0$ (i.e. $x^0$=$1$) means that you selected $0$ object, $x^1$ means $1$ object selected and so on. Your aim is to chose a total of r objects. For that you will have to think of all possible ways of making a total power of $r$. This can be done by either expanding the whole expression or by simply using combinations.

For example, if $r=3$, you can choose powers $3$ from all brackets and then use combinations of lowers powers to add up to 3. the total coefficient that you will recieve is the same as the coefficient of $x^3$ after the expansion of the given expression.