1
$\begingroup$

Please prove this result:

If there are m items of one kind,n items of another kind and so on, then the number of ways of choosing r items of these items is

=Coefficient of $x^r$ in $(1+x+x^2+...+x^m)$$(1+x+x^2+...+x^n)$$...$

If there are $m$ items of one kind,$n$ items of another kind and so on, then the number of ways of choosing $r$ items of these items such that at least one item of each kind is included in every $s$ selection is:

=Coefficient of $x^r$ in $(x+x^2+...+x^m)$$(x+x^2+...+x^n)$$...$



In my textbook only this result is given but not the proof.Maybe because Binomial Theorem is our chapter next to Permutations. But I want to know this proof because I am not able to memorize math results or formulae without knowing it's proof.Please help!!!

My attempt: I have no clue about Binomial Chapter I just know basic results and formulae.That's why I can't move even a step.Please don't close my question.

$\endgroup$
1
$\begingroup$

Expanding the product $(1+ax+a^2x^2+...+a^mx^m)(1+bx+b^2x^2+...+b^nx^n)\ldots\ $ results in a sum of $(m+1)(n+1)\ldots\ $ terms of the type $a^kb^l\ldots\ x^r$ with $k+l+\ldots=r$.

For a fixed $r$ the coefficients of the $x^r$-terms correspond with the ways of choosing $k$ items of the first kind plus $l$ items of the second kind plus $\ldots$ etcetera for a total of $r$ items.

Setting $a=b=\ldots=1$ gives all these coefficients the value $1$ and the $x^r$-terms can be combined into $c_rx^r$, where $c_r$ is the number of different selections for $r$ items.

$\endgroup$
1
$\begingroup$

I will not prove it, but I will try to give you some intuition about what's going on. Let me simplify the first formula into

$$(\textrm{# of 1st items})\cdot(\textrm{# of 2nd items})\cdot\dots\cdot(\textrm{# of last items})$$

Say there are $n$ different kinds in total. Imagine each "$(\textrm{# of _ items})$" as a panel, once you decide how much amount you want for that kind, you press a button on that panel. (here "press" a button is analogy for choosing a term in the parenthesis/panel) Say you want $k$ copies of that kind, then you press the button $x^k$. (and for some kind(s) you don't want any, press $x^0=1$.) So in your second formula those "$1$"(, which actually means $x^0$) buttons are missing so you have to choose at least one for each kind (so sad.) This mechanism includes all the possibility.


The details behind this are two simple(but important) ideas of combinatorics, and an algebra rule you must be familiar with:

  • Product rule: Once you press any button, you just decide the amount for that kind, no effect to any other panels.
  • Distribution law: Notice that all coefficients of $x^k$ are $1$'s, so once you "expand" the formula each term still has $1$ as its coefficient. This is good because each round of $n$-decisions represent one way of choosing. (and these ways are also mutually independent!)

Assume you have expanded the formula, and for each term notice that $x^ax^b=x^{a+b}$, let us just focus on the exponent part, it's actually count the total items you got "in this way", regardless of which kind(s) of item you've chosen. Finally, the rule I like the most

  • Addition rule: Now all terms with the same "label" $x^k$ are simply summed up, since all "ways" are mutually independent(no need to subtract the repetition(s)), the coefficient of $x^k$ means: How many possible "ways" that end up with $k$ items chosen out.

And I left the formal proof for your textbook.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.