Combinatorics

Combinatorics

We know that we can choose $r$ objects from $n$ distinct objects in ${n\choose r}$ ways. But why?

$${n\choose r} = \frac{n!}{r!(n-r)!} = \frac{n\times (n-1)\times (n-2) \times \cdots \times (n-r+1)}{r!}$$

This can be thought of as having $r$ empty slots in which we want to arrange the $r$ objects chosen from the $n$ objects.

$$\underbrace{(n)\ (n-1) \cdots(n-r+1)}_{r\ \text{slots to fill}}$$

For the first slot we have all $n$ objects available to choose from, after which we have $n-1$ objects for the second slot and so on until the last slot for which we only have $(n-(r-1))$ choices as $r-1$ slots have already been filled with objects from the total $n$ objects.

$$P_{r}^{n} = (n-0)\times (n-1)\times (n-2) \times \cdots (n-i) \cdots \times (n-(r-1))$$

$$P_{r}^{n} = \frac{n!}{(n-r)!}$$

But here $P_{r}^{n}$ represents the permutations of $n$ objects taken $r$ at a time because we have considered the order to be a distinguishing factor.

But when we just want to choose $r$ objects the order of these $r$ objects should not matter.

So we divide $P_{r}^{n}$ with $r!$ to get ${n\choose r}$, $\ r!$ because that’s the number of ways we can arrange $r$ distinct objects.

Here I had a doubt, why divide by $r!$? how does that work! division $\frac{a}{b}$ can be thought of as asking if $a$ was equally distributed into $b$ boxes, how many would be there in each box. How much larger is $a$ when compared to $b$? Or even how many times do I need to subtract $b$ from $a$ to get $0$.

To understand how this happens I went back to the first time I heard of division being used in this fashion. When I wanted to find all permutations of $n$ objects of which $r$ were identical, it was said to be $\frac{n!}{r!}$.

In $n!$ we overcounted by a factor of $r!$

To see why $\frac{n!}{r!}$ consider 3 numbered balls, $3!$ is $3\times 2\times 1=6$, the $6$ permutations for these balls are shown below,

Now its $6$ different arrangements if we order with respect to the number on the ball. But what if we don’t care about the number instead only about the color? Then we can see that we have counted identical arrangements multiple times.

To put this into perspective we need to group the $n!$ i.e. $6$ permutations such that in each group the $r$ identical objects (yellow balls) occupy the same position (you can think of it as each of the columns having the same color).

Group 1 - position one and two

only counts as,

Group 2 - position one and three

only counts as,

Group 3 - position two and three

only counts as,

We know and can see that each of these groups will have $r!$ i.e. $2!=2\times 1=2$ permutations in them. This is because in each of these groups we can move around the $r$ identical objects in $r!$ ways and yet not change the arrangement.

So here when we divide $n!$ by $r!$ what we are doing is asking how many groups containing $r!$ permutations each exists such that all the arrangements add up to $n!$

Note that in each group the positions held by the $r$ identical objects must be the same.

Now coming back to ${n\choose r}$, when we calculated $P_{r}^{n}$ for every distinct set of $r$ objects that were chosen from $n$ we counted $r!$ extra permutations. So as order doesnt matter in combinations we can just divide with $r!$ and get,

$$\Large {n\choose r} = \frac{P_{r}^{n}}{r!} = \frac{n!}{r!(n-r)!}$$

Written with StackEdit.