Help to understand formulas on general counting methods I don't understand why the folowwing formulas must be true:

I do understand the sum rule, the product rule, ${^nC_r}$ and ${^nP_r}$. How do I express the two formulas in terms of these concepts?
 A: The product rule says that if you have $n$ ways to make one choice, and $m$ ways to make a second, independent choice, then you have $n\cdot m$ ways to make the two choices together.
Now suppose you have $n$ ways to make a choice, but you are going to choose $r$ times, again and again  You can make the first choice in $n$ ways, the second choice in $n$ ways, the third choice in $n$ ways, and so on.  By the product rule, the number of ways of making all the choices together is $$\underbrace{n\cdot n\cdot n\cdots n}_{\text{$r$ times}}$$and this is exactly $n^r$.
Your book says for (d) “choose $r$ objects from $n$ distinct objects if the same object could be chosen repeatedly”.  So you get to make $r$ choices.  In the first choice you can choose any of $n$ objects, the second choice again any of the $n$ objects, and so on, so $n^r$.

For (e), imagine that the $k$ categories are $k$ bins, and we want to take the $n$ objects and put exactly $n_1$ of them into bin 1, $n_2$ of them into bin 2, and so forth, up to bin $k$.
We first get to choose which $n_1$ of the $n$ objects should go into bin 1, and there are exactly $n\choose n_1$ ways to make this choice.  Then we need to pick which objects go into bin 2.  We need to choose $n_2$ objects from the $n-n_1$ that have not already gone into bin 1, so there are $n-n_1\choose n_2$ ways to make this second choice.  Then we need to pick which objects go into bin 3.  Of the $n$ objects, $n-n_1-n_2$ remain to pick, since $n_1$ are already in bin 1 and $n_2$ are already in bin 2, so we have $n-n_1-n_2\choose n_3$ ways to make this third choice.  We repeat for each of the $k$ bins, and then by the product rule the number of ways of making all the choices together is the product of the number of ways of making the separate choices: $$\binom{n}{n_1}\binom{n-n_1}{n_2}\binom{n-n_1-n_2}{n_3}\cdots  \binom{n-n_1-\cdots-n_{k-1}}{n_k} .$$
(It may not have been obvious that the intention here is that $n = n_1 + \cdots + n_k$, so that the last factor, $\binom{n-n_1-\cdots-n_{k-1}}{n_k}$, is actually equal to 1. it represents the number of ways of selecting all the remaining $n_k$ objects and putting them into bin $k$.)
Now we have the question of why this last expression is equal to $${n!\over n_1!n_2!\cdots n_k! }.$$  We can do an algebraic proof, or we can just try to understand the situation. 
To understand the situation, let's consider a concrete example.  Say $n = 6$ and $n_1 = 2, n_2 = 3,$ and $n_3=1$.
Imagine we are putting all 6 objects into the 3 bins, as before.  One way to do this is to make a list of the 6 objects in some order, then put the first 2 objects from the list into bin 1, the next 3 into bin 2, and the last one in bin 3.  There are $6! = 720$ ways to line them up in order. But not every order gives a different distribution into the bins. It doesn't matter how the first $2$ of the objects are listed, because once they are thrown into bin 1 they are  jumbled up.  For example, the list $A B\, P Q R \,Z$ gives the same distribution into bins as $B A \,P Q R \,Z$.  We mustn't count all $720$ possible lists of the 6 objects, because that counts every distribution twice, once with the bin 1 objects listed first and second, and once with them listed second and first.  So we need to divide by 2.  Similarly, the order of the next 3 objects on the list doesn't matter, since the next three are going into bin 2 regardless of how they were listed.  Of the 720 lists, every six correspond to an equivalent distribution of objects into bin 2.  For example, these six lists all represent the same distribution of balls to bins:
$$
B A \,P Q R\, Z \\
B A \,P R Q\, Z \\
B A \,Q P R\, Z \\
B A \,Q R P\, Z \\
B A \,R P Q\, Z \\
B A \,R Q P\, Z
$$
In this example, the total number of distributions is $n!$, divided by 2 to correct for balls getting mixed up in the first bin, divided by 6 to correct for balls getting mixed up in the second bin, and then divided by 1 to correct for balls getting mixed up in the third bin; that is $${6!\over2!3!1!} = 60.$$ In the general case you have $n!$ orders for the objects, but that overcounts by a factor  of $n_1!$ for the bin 1 objects, a factor of $n_2!$ for the bin 2 objects, and so on, so the correct number of distributions is $${n!\over n_1!n_2!\cdots n_k!} .$$
Now we have counted the number of ways of putting the objects into bins in two ways, and gotten $$\binom{n}{n_1}\binom{n-n_1}{n_2}\binom{n-n_1-n_2}{n_3}\cdots  \binom{n-n_1-\cdots-n_{k-1}}{n_k}$$ and $${n!\over n_1!n_2!\cdots n_k!} .$$  So we had better hope that these are equal, if not there is some mistake.  But expanding the first expression we get:
$$\frac{n!}{n_1!(n-n_1)!}\cdot
\frac{(n-n_1)!}{n_2!(n-n_1-n_2)!}\cdot
\frac{(n-n_1-n_2)!}{n_2!(n-n_1-n_2-n_3)!}\cdots
\frac{(n-n_1-\cdots-n_{k-1})!}{n_k!(n-n_1-\cdots-n_{k})!}$$
and if you are not frightened by the notation, you will be able to see that the $(n-n_1)!$ in the first denominator will cancel the $(n-n_1)!$ in the second numerator; the $(n-n_1-n_2)!$ in the second denominator will cancel the $(n-n_1-n_2)!$ in the second numerator, and so on, leaving you with just 
$$\frac{n!}{n_1!n_2!\cdots n_k!}\frac{1}{(n-n_1-\cdots-n_{k})!}$$
So the only thing left over is  the $(n-n_1-\cdots-n_{k})!$ in the denominator.  But $n = n_1+\cdots+n_k$, so this factor is $0! = 1$ and cancels too.
