Difference between revisions of "A choose b"

Revision as of 19:03, 25 July 2021

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

@@ Line 27: / Line 27: @@
 == Pascal's Identity ==
-Pascal's Identity states that
+[[Pascal's Identity]] states that
 <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>

Page

Toolbox

Search