Proving the combinatorial expression
Ok I've been reading in my probability book about the different methods on how to count and I'm just trying to dissect the usual combinatorial formula: $$\binom {a} {b} = \frac{a!}{b!(a-b)!}$$
Everything makes sense excpet I can't figure out how the $(a-b)!$ term arises. The other two terms are fine with $a!$ being the number of ordered samples while $b!$ is the number of permutations for each sample, but that difference is throwing me for a loop.
$\endgroup$3 Answers
$\begingroup$If you order your $a$ items, there will be $a!$ ways. However for choosing a subset of size $b$ (which is the first $b$ items in your ordering), not only does the ordering of the first $b$ items not matter, but also the ordering of the remaining $a-b$ items outside the chosen subset does not matter. This is why you divide by both factorials.
$\endgroup$ 1 $\begingroup$a-b is the number of samples left. Think about it.
Selecting 5 red balls from an urn with 5 red balls and 9 blue balls is equivalent to selecting 9 blue balls from an urn with 5 red balls and 9 blue balls.
$\endgroup$ $\begingroup$sampling $b$ from $a$:
$1^\text{st}$.may be chosen in $a$ ways
$2^\text{nd}$.may be chosen in $a-1$ ways
${}\,\vdots$
$b^\text{th}$. may be chosen in $a-b+1$ ways
total possible samples $a(a-1)\cdots(a-b+1)$
equivalence
the $b$ sampled items give the same sample when chosen in any of the $b!$ different possible orders.
hence number of samples of $b$ things from $a$ is $$ \frac{a(a-1)\cdots(a-b+1)}{b!} = \frac{a(a-1)\cdots(a-b+1)(a-b)!}{b!(a-b)!}=\frac{a!}{b!(a-b)!} $$
$\endgroup$
