Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "A choose b"
m
 
(8 intermediate revisions by 2 users not shown)
Line 27: Line 27:
 
== Pascal's Identity ==
 
== 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>
 
<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>
  
 
Here is the proof:  
 
Here is the proof:  
−
 
−
If <math>k > n</math> then <math>\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}</math> and so the result is trivial.  So assume <math>k \leq n</math>.  Then
 
  
 
<cmath>\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)!}\\
 
<cmath>\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)!}\\
Line 40: Line 38:
 
&=&\frac{n!}{k!(n-k)!}\\
 
&=&\frac{n!}{k!(n-k)!}\\
 
&=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath>
 
&=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath>
 +
 +
== 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:
 +
 +
<math>\binom{0}{0}</math>
 +
 +
<math>\binom{1}{0} \binom{1}{1}</math>
 +
 +
<math>\binom{2}{0} \binom{2}{1} \binom{2}{2}</math>
 +
 +
<math>\binom{3}{0} \binom{3}{1} \binom{3}{2} \binom{3}{3}</math>
 +
 +
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 <math>1=2^0</math>. The first row has a sum of <math>2=2^1</math>. The <math>n^{th}</math> row has a sum of <math>2^n</math>. 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.

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=A_choose_b&oldid=230363"