# Understanding $n\choose k$ in terms of sum and product rules

This is a follow up on my earlier question. To put some values and context, let me say I am trying to justify the number of possibilities of choosing 2 chapters out of 10 in a book i,e $10 \choose 2$. At this point this is just notation.

One way to enumerate the possibilities:

$$\underbrace{\underbrace{(1,2),(1,3)\cdots,(1,10)}_{9}\underbrace{(2,1),(2,3)\cdots,(2,10)}_{9}\cdots\underbrace{(10,1),(10,2)\cdots,(10,9)}_{9}}_{10}$$

So we have $10\cdot 9$ possibilities but we've double counted pairs such as $(n,m)$ and $(m,n)$ so we have $\frac{10\cdot 9}{2}$.

Now I try to reason with the sum and product rules I've learnt and once again Im confused, which might become detrimental if I go further.

Say I select chapter $1$. I can select chapter $2$ OR $3$ etc. Once I have selected one chapter, the selection of the other chapter is independent w.r.t one another, so using the sum rule I can make total $9$ possible selections once I have selected the first chapter. But then, I can make $10$ different choices of the first chapter. Now it is clear in my mind that each one of these ten possible selections come bundled with 9 possibilities, so multiply the two. But when I read the definition many times and try to bring in a "product-rule argument" and I just cannot. It should come as easily as the thought that I should multiply it, so I've only understood the product rule in words. Please enlighten me.

Another thing I noticed, was that this could be achieved using a purely sum rule argument. Consider the enumeration scheme where we avoid repetition altogether

$$\underbrace{(1,2),(1,3),\cdots,(1,10)}_{9},\underbrace{(2,3),(2,4),\cdots,(2,10)}_{8}\underbrace{(3,4),(3,5),\cdots,(3,10)}_{7},\cdots\underbrace{(9,10)}_1$$

$$=9+8+\cdots+1=\frac{10\cdot 9}{2}$$

Only the sum rule has been used in this argument. And it is much easier for me to understand. So, a parenthetical query: can a purely product rule argument be used for selections? It does not seem so for me. It appears the sum rule is fundamental and product rule is a special case of it. Which might seem like saying that multiplication is a special case of addition in discrete case. Once again, this last paragraph is just a parenthetical query and not my immediate concern at the moment.

-
"Now it is clear in my mind that each one of these ten possible selections come bundled with 9 possibilities, so multiply the two." Sure. This will give you the number of ordered pairs (m,n) you can select, so then you divide by 2 because you don't care about the order. What's your confusion exactly? – ShreevatsaR May 12 '11 at 9:36
To reframe the thought process in terms of the product rule. – kuch nahi May 12 '11 at 9:42
But multiplying 10 by 9 to get 90 is the product rule, and it counts the number of ordered pairs. If you want the division-by-2 also in terms of the product rule, then as Qiaochu said you can use "number of ordered pairs = (number of unordered pairs) * (two ways of ordering each)" — this is the product rule — to get 90 = (Answer)*2 or Answer = 45. – ShreevatsaR May 12 '11 at 12:54

You shouldn't be so dramatically holding on to those rules ; notice that they are not called theorems, but rules ; that is because they are principles that we did not prove but stated so that students could help themselves to count stuff. I am usually comfortable with basing myself on axioms to prove theorems, but what you are trying to do here is not to prove a theorem, but to count stuff. To do so, use whatever you feel comfortable with, and do not bother about "rules" whose name seem to govern your mind... because you can get confused very quickly.

Once you have understood that to choose $k$ items amongst $n$ possible items, you have $n \choose k$ ways of doing so, it doesn't matter the rule you used to understand how to do so, because once you did, this becomes a new "rule" you can apply as free as you want. What I'm saying is, do not try to "fit in the name of the rules" ; understanding why $10 \choose 2$ finds the correct number is a good thing, but trying to fit in the name of the rules in the calculations you do is not something important.

A purely product rule can be applied if you still wish to "fit in the names of the rules" in your calculation" : you have to choose 2 chapters among 10, now there are 10 choices for your first chapter, and 9 choices for your second, since everytime you're about to choose your second chapter, one chapter's gone. Hence there is 90 choices of first and second chapter by the product rule (The number of choices in each case is independent of each other, even though the choices available are dependent, but the counting does not differ.). Since you do not wish to distinguish a pair of chapters by whether one of the two is first or second, you've noticed you've counted the double of what you wished to count, hence you divide 90 by 2 to get ${10 \choose 2} = 45$ and you never "added" stuff in here.

I hope this helped.

-
If something is given a name perhaps it would be crucial in solving much harder problems, right? For example the pigeonhole principle seems pretty obvious when stated but it can be applied to a lot of problems which are not-as-obvious. – kuch nahi May 12 '11 at 9:45
@yayu What I'm saying is, focus on understanding how to count beside stating what principle you use, that's the important in counting. The pigeonhole principle is not a counting principle, its a tool in methods of proof, we're speaking of different types of principle. The counting principles need to be understood and applied, not described, that's my opinion. In combinatorics we barely even mention the sum and product rule when it's considered understood because the names are not important, it's what they allow us to do that is. – Patrick Da Silva May 13 '11 at 4:01

The likeliest interpretation of your confusion is that you have learned a very constrictive version of the product rule that it is not appropriate for counting non-trivial things.

You multiply things not only when the choices are independent, but also when the number of the second choices are independent of the first choices.

If you have learned a more restrictive version of product rule, then there is no point in trying to fit things into this arbitrary definition.

-

If you're asking what I think you're asking, here is an argument that only uses the "product rule":

First, establish that the number of ways to order the numbers $\{ 1, 2, ... n \}$ is $n!$. Next, let ${n \choose k}$ denote the number of ways to choose $k$ numbers (not in any particular order) out of $\{ 1, 2, ... n \}$. Then:

• On the one hand, the number of ways to order $\{ 1, 2, ... n \}$ is $n!$.
• On the other hand, given any such order, the first $k$ elements of that order are a set of $k$ numbers (which we can choose in ${n \choose k}$ ways) together with an ordering of those numbers (which we can choose in $k!$ ways) together with an ordering of the rest of the numbers (which we can choose in $(n-k)!$ ways).

It follows that $n! = {n \choose k} k! (n-k)!$.

-

The product rule is that if we have x ways of doing something and y ways of doing another thing, then there are xy ways of performing both actions. Here's how you can think of the product rule. The things in question are choosing a first chapter and choosing a second chapter.

First consider each of the ways of choosing a first chapter. There are 10 such ways, namely chapter 1 to 10. Put all these ways in a set A. $A=\{way_1,way_2,...,way_{10}\}$

Now each of the ways of choosing a second chapter can be considered. There are nine such ways determined after leaving out an unknown chapter. (Whichever chapter was selected earlier, the number of ways will always be 1 less) Put all these ways in the set B. $B=\{Way_1,Way_2,...,Way_9\}$

By the product rule, total number of ways is the number of elements in A x B i.e. 90.

In general if you have to choose k chapters out of n, where order is important, we can extend the same logic to see that the number of ways is $n(n-1)...(n-(k-1))$. If we are not bothered about the order then note that any such way appears exactly k! times in the above (since k chapters may be permuted in k! ways). So if ways without regard to order are considered, and we suppose there are X such ways then, $(k! + k! + .... + k!)$(X times) $= n(n-1)...(n-(k-1))$ or

$X=\frac{n(n-1)...(n-k+1)}{k!}=\frac{n!}{k!(n-k)!}$

As you are aware the usual way to denote X is by the symbol $\tbinom{n}{k}$

Hope this helps.

-