Difference between revisions of "A choose b"

Latest revision as of 18:00, 22 October 2024

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}$

I'll encourage you to prove it by yourself

Another way to build it is to start with two diagonal rows of one and then the rest of the numbers are the sum of the two numbers above it.

The zeroth row has a sum of $1=2^0$ . The first row has a sum of $2=2^1$ . The $n^{th}$ row has a sum of $2^n$ . This is because in the second way we build the tr The 1st downward diagonal is a row of 1's, the 2nd downward diagonal on each side consists of the natural numbers, the 3rd diagonal the triangular numbers, and the 4th the pyramidal numbers. There are many interesting applications of pascals triangle, I encourage you to explore the patterns.

Page

Toolbox

Search