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
(Propose for deletion)
 
Line 1: Line 1:
 
Here is the formula for a choose b: <math>\binom{a}{b}=\frac{a!}{b!(a-b)!}</math>. This is assuming that of course <math>a \ge b </math>.
 
Here is the formula for a choose b: <math>\binom{a}{b}=\frac{a!}{b!(a-b)!}</math>. This is assuming that of course <math>a \ge b </math>.
 
   
 
   
−
== Why is it important? ==
+
== Uses ==
−
a choose b counts the number of ways you can pick b things from a set of a things. For example <math>\binom{8}{2}=\frac{8!}{2!(8-2)!}=\frac{8(7)}{2}=\frac{42}{2}=21</math>. More at
 
−
https://artofproblemsolving.com/videos/counting/chapter4/64.
 
  
−
== a choose 2 ==
+
a choose b counts the number of ways you can pick b things from a set of a things. For example <math>\binom{8}{2}=\frac{8!}{2!(8-2)!}=\frac{8(7)}{2}=\frac{42}{2}=21</math>. More [{{SERVER}}/videos/counting/chapter4/64 here.]
 +
 
 +
== Choose 2 ==
 
Here is a list of n choose 2's
 
Here is a list of n choose 2's
−
 
 
<math>\binom{2}{2}=1</math>
 
<math>\binom{2}{2}=1</math>
−
 
 
<math>\binom{3}{2}=3</math>
 
<math>\binom{3}{2}=3</math>
−
 
 
<math>\binom{4}{2}=6</math>
 
<math>\binom{4}{2}=6</math>
−
 
 
<math>\binom{5}{2}=10</math>
 
<math>\binom{5}{2}=10</math>
−
 
+
These are triangle numbers! My proof uses induction (assuming something is true unless proved true or false).  
−
These are triangle numbers! My proof uses induction (assuming something is true unless proofed true or not true).  
 
 
<math>\binom{n}{2}=1+2+3...+(n-1)</math> Then Simplify:  
 
<math>\binom{n}{2}=1+2+3...+(n-1)</math> Then Simplify:  
−
 
+
<math>\frac{n!}{2!(n-2)!}=\frac{n(n+1)}{2}</math> Simplify further:
−
<math>\frac{n!}{2!(n-2)!}=\frac{n(n+1)}{2}</math> More Simplify:
+
<math>\frac{n(n+1)}{2}=\frac{n(n+1)}{2} \square</math>
−
 
+
If you don't get what I did on the second step go to Proof Without Words on this wiki.
−
<math>\frac{n(n+1)}{2}=\frac{n(n+1)}{2}</math>
 
−
 
 
−
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 ==
  
−
[[Pascal's Identity]] states that
+
{{main|Pascal's Identity}}
  
 +
===Statement===
 
<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:
+
===Proof===
  
 
<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 41: Line 34:
 
== Binomial Theorem and Pascal's Triangle ==
 
== Binomial Theorem and Pascal's Triangle ==
  
−
Pascal's triangle is an array of numbers that represent binomial coefficients. It looks something like this:
+
Pascal's triangle is an array of numbers that represent binomial coefficients. It looks like this:
 
   
 
   
−
                  1
+
      1
−
                1   1
+
    1 1
−
              1   2   1
+
  1 2 1
−
            1   3   3   1
+
  1 3 3 1
−
          1   4   6   4   1
+
1 4 6 4 1
  
−
And on and on...
+
And so on...
  
−
You may ask the question: What does this have to do with a choose b. Well, this triangle is the same as this:  
+
This triangle can be rewritten like this:  
  
 
<math>\binom{0}{0}</math>
 
<math>\binom{0}{0}</math>
Line 68: Line 61:
 
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.
 
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.
 
There are many interesting applications of pascals triangle, I encourage you to explore the patterns.
 +
 +
{{delete|unnecessary page, Duplicate of [[Combination]]}}

Latest revision as of 12:56, 19 February 2025

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

Uses

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 here.

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 proved true or false). $\binom{n}{2}=1+2+3...+(n-1)$ Then Simplify: $\frac{n!}{2!(n-2)!}=\frac{n(n+1)}{2}$ Simplify further: $\frac{n(n+1)}{2}=\frac{n(n+1)}{2} \square$ If you don't get what I did on the second step go to Proof Without Words on this wiki.

Pascal's Identity

Main article: Pascal's Identity

Statement

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

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 like this: 

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

And so on...

This triangle can be rewritten like 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.

This article has been proposed for deletion. The reason given is: unnecessary page, Duplicate of Combination.

Sysops: Before deleting this article, please check the article discussion pages and history.

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