A choose b

Revision as of 21:02, 15 June 2019 by Colball (talk | contribs)

Here is the formula for a choose b: $\binom{a}{b}=\frac{a!}{b!(a-b)!}$. This is assuming that of course $a \ge b$.

Why is it important?

a choose b counts the number of ways you can pick b things from a set of a things. For example $\binom{8}{2}=\frac{8!}{2!(8-2)!}=\frac{8(7)}{2}=\frac{42}{2}=21$. More at https://artofproblemsolving.com/videos/counting/chapter4/64.

a choose 2

Here is a list of n choose 2's

$\binom{2}{2}=1$

$\binom{3}{2}=3$

$\binom{4}{2}=6$

$\binom{5}{2}=10$

These are triangle numbers! My proof uses induction (assuming something is true unless proofed true or not true). $\binom{n}{2}=1+2+3...+(n-1)$ Then Simplify:

$\frac{n!}{2!(n-2)!}=\frac{n(n+1)}{2}$ More Simplify:

$\frac{n(n+1)}{2}=\frac{n(n+1)}{2}$

So now we have proved it. If you don't get what I did on the second step go to Proof Without Words on this wiki.

Pascal's Identity

Pascal's Identity states that

${n \choose k}={n-1\choose k-1}+{n-1\choose k}$

Here is the proof:

\begin{eqnarray*}\binom{n-1}{k-1}+\binom{n-1}{k}&=&\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\ &=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\ &=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\ &=&\frac{n!}{k!(n-k)!}\\ &=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}


Binomial Theorem and Pascal's Triangle

Pascal's triangle is an array of numbers that represent binomial coefficients. It looks something like this:

                  1
                1   1
              1   2   1
            1   3   3   1
         1   4    6    4   1

And on and on...

You may ask the question: What does this have to do with a choose b. Well, this triangle is the same as this:

$\binom{0}{0}$

$\binom{1}{0} \binom{1}{1}$

$\binom{2}{0} \binom{2}{1} \binom{2}{2}$

$\binom{3}{0} \binom{3}{1} \binom{3}{2} \binom{3}{3}$