Proof that the combination formula actually gives you the number of combinations

Question

Ok, there's no problem in defining a binomial coefficient the way it this:

$$\binom {a} {b} = \frac{a!}{b!(a-b)!}$$

I can also prove to myself that if I have $n$ elements, like: $\{a_1, a_2, \ldots, a_n\}$ then the ways I can permute this, in $p$ places, this way:

$$\frac{n!}{(n-p)!}$$

I've also read that the combination formula is like this because we divide the many ways we can permute by the number of permutations. I've been able to conjecture this in my drawings, but I couldn't generalize it, so I wanted to know if there's a good way to picture it.

Answer 1

For combinations, you don't care about the order. All the different orders that select the same $p$ items out of $n$ are considered equivalent. How many ways are there to select a set of $p$? Precisely the number of permutations of $p$ items, because that is the number of different orders you might select them. The number of combinations is then $${n \choose p}=\frac {n!}{(n-p)!p!}$$

Answer 2

Each permutation can be rearranged to give the same combination in $p!$ ways. As the word each is used, we divide :

$$^nC_p=\frac{^nP_p}{p!}$$

Answer 3

Another way is :

we want to know coefficient of $x^p $ in $(1+x)^n$.

$(1+x)(1+x)(1+x)...$

Clearly, we can choose any $p$ brackets to multiply $x$ and rest to be multiplied with $p$. Hence, coefficient of $x^p$ is $n\choose p$

Also, let's go back to the world of combinatorics. Suppose for some reason, you want to select $p$ or $p-1$ girls from a group of $n$ girls.

You are smart. You cleverly put a $stone$ among the group and then select $p$ things. If the stone turns up, you can argue that stone isn't a girl and you chose $p-1$ girls. If stone doesn't come, you can say that you chose $p$ girls.

Hence, $\binom{n+1}{p}=\binom{n}{p-1}+\binom{n}{p}$

Now you can read proof of binomial theorem here.