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 "Pascal's triangle"

(→‎Number Parity)
(Added proof)
 
(26 intermediate revisions by 17 users not shown)
Line 1: Line 1:
−
<div class="thumb tright">
+
'''Pascal's triangle''' is a triangle which contains the values from the [[binomial expansion]]; its various properties play a large role in [[combinatorics]].
−
<div>
 
−
<div>
 
−
<table border="0">
 
−
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td></td><td></td><td>1</td><td></td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td></td><td>1</td><td></td><td>2</td><td></td><td>1</td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td>1</td><td></td><td>3</td><td></td><td>3</td><td></td><td>1</td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td>1</td><td></td><td>4</td><td></td><td>6</td><td></td><td>4</td><td></td><td>1</td><td></td><td></td></tr>
 
−
<tr><td></td><td>1</td><td></td><td>5</td><td></td><td>10</td><td></td><td>10</td><td></td><td>5</td><td></td><td>1</td><td></td></tr>
 
−
<tr><td>1</td><td></td><td>6</td><td></td><td>15</td><td></td><td>20</td><td></td><td>15</td><td></td><td>6</td><td></td><td>1</td></tr>
 
−
</table>
 
−
</div>
 
−
<div class="thumbcaption">First few rows of Pascal's Triangle</div>
 
−
</div>
 
−
</div>
 
−
 
 
−
'''Pascal's Triangle''' is a triangle which contains the values from the [[binomial expansion]]; its various properties play a large role in [[combinatorics]].
 
  
 
== Properties ==
 
== Properties ==
  
 
=== Binomial coefficients ===
 
=== Binomial coefficients ===
−
Pascal's Triangle is defined such that the number in row <math>n</math> and column <math>k</math> is <math>\displaystyle{n\choose k}</math>.  For this reason, [[mathematical convention|convention]] holds that both row numbers and column numbers start with 0.  Thus, the apex of the triangle is row 0, and the first number in each row is column 0.  As an example, the number in row 4, column 2 is <math>\displaystyle{4 \choose 2} = 6</math>.  Pascal's Triangle thus can serve as a "look-up table" for binomial expansion values.  Also, many of the characteristics of Pascal's Triangle are derived from [[combinatorial identities]]; for example, because <math>\sum_{k=0}^{n}{{n \choose k}}=2^n</math>, the sum of the values on row <math>n</math> of Pascal's Triangle is <math>2^n</math>.
+
[[Image:Pascaltriangle.jpg|frame|right|110px|These are the first nine rows of Pascal's Triangle.]] Pascal's Triangle is defined such that the number in row <math>n</math> and column <math>k</math> is <math>{n\choose k}</math>.  For this reason, [[mathematical convention|convention]] holds that both row numbers and column numbers start with 0.  Thus, the apex of the triangle is row 0, and the first number in each row is column 0.  As an example, the number in row 4, column 2 is <math>{4 \choose 2} = 6</math>.  Pascal's Triangle thus can serve as a "look-up table" for binomial expansion values.  Also, many of the characteristics of Pascal's Triangle are derived from [[combinatorial identities]]; for example, because <math>\sum_{k=0}^{n}{{n \choose k}}=2^n</math>, the sum of the values on row <math>n</math> of Pascal's Triangle is <math>2^n</math>.
  
 
=== Sum of previous values ===
 
=== Sum of previous values ===
  
−
<div class="thumb tright">
+
One of the best known features of Pascal's Triangle is derived from the combinatorics identity <math>{n \choose k}+{n \choose k+1} = {n+1 \choose k+1}</math>.  Thus, any number in the interior of Pascal's Triangle will be the sum of the two numbers appearing above it.  For example, <math>{5 \choose 1}+{5 \choose 2} = 5 + 10 = 15 = {6 \choose 2}</math>.  This property allows the easy creation of the first few rows of Pascal's Triangle without having to calculate out each binomial expansion.
−
<div>
+
 
−
<div>
+
=== Fibonacci numbers ===
−
<table border="0">
+
 
−
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
+
The [[Fibonacci sequence|Fibonacci numbers]] appear in Pascal's Triangle along the "shallow diagonals."  That is, <math>{n \choose 0}+{n-1 \choose 1}+\cdots+{n-\left\lfloor\frac{n}{2}\right\rfloor \choose \left\lfloor \frac{n}{2}\right \rfloor} = F(n+1)</math>, where <math>F(n)</math> is the Fibonacci sequence.  For example, <math>{6 \choose 0}+{5 \choose 1}+{4 \choose 2}+{3 \choose 3} = 1 + 5 + 6 + 1 = 13 = F(7)</math>.  A "shallow diagonal" is plotted in the diagram.
−
<tr><td></td><td></td><td></td><td></td><td></td><td>1</td><td></td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td></td><td>1</td><td></td><td>2</td><td></td><td>1</td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td>1</td><td></td><td>3</td><td></td><td>3</td><td></td><td>1</td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td>1</td><td></td><td>4</td><td></td><td>6</td><td></td><td>4</td><td></td><td>1</td><td></td><td></td></tr>
 
−
<tr><td></td><td>1</td><td></td><td>'''5'''</td><td></td><td>'''10'''</td><td></td><td>10</td><td></td><td>5</td><td></td><td>1</td><td></td></tr>
 
−
<tr><td>1</td><td></td><td>6</td><td></td><td>'''15'''</td><td></td><td>20</td><td></td><td>15</td><td></td><td>6</td><td></td><td>1</td></tr>
 
−
</table>
 
−
</div>
 
−
<div class="thumbcaption">Sum of previous values</div>
 
−
</div>
 
−
</div>
 
  
−
One of the best known features of Pascal's Triangle is derived from the combinatorics identity <math>{n \choose k}+{n \choose k+1} = {n+1 \choose k+1}</math>.  Thus, any number in the interior of Pascal's Triangle will be the sum of the two numbers appearing above it.  For example, <math>{5 \choose 1}+{5 \choose 2} = 5 + 10 = 15 = {6 \choose 2}</math>, as shown in the diagram.  This property allows the easy creation of the first few rows of Pascal's Triangle without having to calculate out each binomial expansion.
+
=== Hockey-Stick Identity ===
  
−
=== Fibonacci numbers ===
+
The [[Combinatorial identity#Hockey-Stick Identity|Hockey-Stick Identity]] states:
 +
<math>{n \choose 0}+{n+1 \choose 1}+\cdots+{n+k \choose k} = {n+k+1 \choose k}</math>.  Its name is due to the "hockey-stick" which appears when the numbers are plotted on Pascal's Triangle, as shown in the representation of the theorem below (where <math>n=2</math> and <math>k=3</math>).
 +
 
 +
<asy>
 +
int chew(int n,int r){
 +
int res=1;
 +
for(int i=0;i<r;++i){
 +
  res=quotient(res*(n-i),i+1);
 +
  }
 +
return res;
 +
}
 +
for(int n=0;n<9;++n){
 +
for(int i=0;i<=n;++i){
 +
  if((i==2 && n<6)||(i==3 && n==6)){
 +
  if(n==6){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}
 +
  else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}
 +
  }
 +
  else{
 +
  label(string(chew(n,i)),(11+n/2-i,-n));
 +
  }
 +
  }
 +
}
 +
</asy>
 +
 
 +
=== Number Parity ===
 +
Consider writing the row number <math>n</math> in [[base number | base]] two as <math>({n})_{10} = {(a_xa_{x-1} \cdots a_1a_0)}_2</math><math> = a_x 2^x+a_{x-1} 2^{x-1}+\cdots+a_1 2^1+a_0 2^0</math>.  The number in the <math>k</math>th column of the <math>n</math>th row in Pascal's Triangle is [[odd integer | odd]] if and only if <math>k</math> can be expressed as the sum of some <math>a_i 2^i</math>.  For example, <math>(9)_{10} = {(1001)}_{2} = 2^{3}+2^{0}</math>.  Thus, the only 4 odd numbers in the 9th row will be in the <math>{(0000)}_{2} = 0</math>th, <math>{(0001)}_{2} = 2^0 = 1</math>st, <math>{(1000)}_{2} = 2^3 = 8</math>th, and <math>{(1001)}_{2} = 2^3+2^0 = 9</math>th columns.  Additionally, marking each of these odd numbers in Pascal's Triangle creates a [[Sierpinski triangle]].
 +
 
 +
[[Image:Sierpinski.jpg]]
  
−
<div class="thumb tright">
+
==== Generalization ====
−
<div>
+
This is a special case of Kummer's Theorem, which states that given a prime p and integers m,n, the highest power of p dividing <math>\binom{m}{n}</math> is the number of carries in adding <math>m-n</math> and n in base p.
−
<div>
 
−
<table border="0">
 
−
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td></td><td></td><td>1</td><td></td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td></td><td>1</td><td></td><td>2</td><td></td><td>1</td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td>1</td><td></td><td>3</td><td></td><td>3</td><td></td><td>'''1'''</td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td>1</td><td></td><td>4</td><td></td><td>'''6'''</td><td></td><td>4</td><td></td><td>1</td><td></td><td></td></tr>
 
−
<tr><td></td><td>1</td><td></td><td>'''5'''</td><td></td><td>10</td><td></td><td>10</td><td></td><td>5</td><td></td><td>1</td><td></td></tr>
 
−
<tr><td>'''1'''</td><td></td><td>6</td><td></td><td>15</td><td></td><td>20</td><td></td><td>15</td><td></td><td>6</td><td></td><td>1</td></tr>
 
−
</table>
 
−
</div>
 
−
<div class="thumbcaption">Shallow diagonals</div>
 
−
</div>
 
−
</div>
 
  
−
The [[Fibonacci sequence|Fibonacci numbers]] appear in Pascal's Triangle along the "shallow diagonals."  That is, <math>{n \choose 0}+{n-1 \choose 1}+\cdots+{n-\lfloor\frac{n}{2}\rfloor \choose \lfloor \frac{n}{2} \rfloor} = F(n+1)</math>, where <math>F(n)</math> is the Fibonacci sequence.  For example, <math>{6 \choose 0}+{5 \choose 1}+{4 \choose 2}+{3 \choose 3} = 1 + 5 + 6 + 2 = 13 = F(7)</math>.  A "shallow diagonal" is plotted in the diagram.
+
=== Patterns and Properties of the Pascal's Triangle ===
  
−
=== Hockey-stick theorem ===
+
==== Rows ====
 +
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>, which means there are <math>2^n</math> ways to get to that row from the zeroth row.
  
−
<div class="thumb tright">
+
'''Proof''': To find the number of ways to get to the <math>n^{th}</math> row of Pascal's Triangle, let's start with the zeroth row. There are <math>2</math> ways to get to the next row because there are <math>2</math> numbers in the first row. Now to get to the second row, we realize that starting from any number on the first row, we have two options to go to in the second row. This means we need to multiply the number of ways to get to the first row by <math>2</math>, which gives us <math>2 \cdot 2 = 2^2 = 4</math>. This pattern continues, so the number of ways to get to the <math>n^{th}</math> row of Pascal's Triangle is <math>2^n</math>.
−
<div>
 
−
<div>
 
−
<table border="0">
 
−
<tr><td></td><td></td><td></td><td></td><td></td><td></td><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td></td><td></td><td>1</td><td></td><td>1</td><td></td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td></td><td>'''1'''</td><td></td><td>2</td><td></td><td>1</td><td></td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td></td><td>1</td><td></td><td>'''3'''</td><td></td><td>3</td><td></td><td>1</td><td></td><td></td><td></td></tr>
 
−
<tr><td></td><td></td><td>1</td><td></td><td>4</td><td></td><td>'''6'''</td><td></td><td>4</td><td></td><td>1</td><td></td><td></td></tr>
 
−
<tr><td></td><td>1</td><td></td><td>5</td><td></td><td>10</td><td></td><td>'''10'''</td><td></td><td>5</td><td></td><td>1</td><td></td></tr>
 
−
<tr><td>1</td><td></td><td>6</td><td></td><td>15</td><td></td><td>'''20'''</td><td></td><td>15</td><td></td><td>6</td><td></td><td>1</td></tr>
 
−
</table>
 
−
</div>
 
−
<div class="thumbcaption">Hockey-stick Theorem</div>
 
−
</div>
 
−
</div>
 
  
−
The [[Hockey-stick theorem]] states:
+
=== Diagonals ===
−
<math>{n \choose 0}+{n+1 \choose 1}+\cdots+{n+k \choose k} = {n+k+1 \choose k}</math>.  Its name is due to the "hockey-stick" which appears when the numbers are plotted on Pascal's Triangle, as shown in the representation of the theorem to the right (where <math>n=2</math> and <math>k=3</math>).
 
  
−
=== Number Parity ===
+
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]].
−
Consider writing the row number <math>n</math> in base two as <math>({n})_{10} = {(a_xa_{x-1} \cdots a_1a_0)}_2</math><math> = a_x 2^x+a_{x-1} 2^{x-1}+\cdots+a_1 2^1+a_0 2^0</math>.  The number in the <math>k</math>th column of the <math>n</math>th row in Pascal's Triangle is odd if and only if <math>k</math> can be expressed as the sum of some <math>a_i 2^i</math>.  For example, <math>(9)_{10} = {(1001)}_{2} = 2^{3}+2^{0}</math>.  Thus, the only 4 odd numbers in the 9th row will be in the <math>{(0000)}_{2} = 0</math>th, <math>{(0001)}_{2} = 2^0 = 1</math>st, <math>{(1000)}_{2} = 2^3 = 8</math>th, and <math>{(1001)}_{2} = 2^3+2^0 = 9</math>th columns.  Additionally, marking each of these odd numbers in Pascal's Triangle creates a [[Sierpinski triangle]].[[Image:Sierpinski.jpg]]
 
  
 
==See Also==
 
==See Also==
 
*[[Binomial theorem]]
 
*[[Binomial theorem]]
 +
*[[Pascal Triangle Related Problems]]
 +
 +
[[Category:Combinatorics]]
 +
[[Category:Definition]]

Latest revision as of 16:20, 3 January 2023

Pascal's triangle is a triangle which contains the values from the binomial expansion; its various properties play a large role in combinatorics.

Properties

Binomial coefficients

These are the first nine rows of Pascal's Triangle.

Pascal's Triangle is defined such that the number in row $n$ and column $k$ is ${n\choose k}$. For this reason, convention holds that both row numbers and column numbers start with 0. Thus, the apex of the triangle is row 0, and the first number in each row is column 0. As an example, the number in row 4, column 2 is ${4 \choose 2} = 6$. Pascal's Triangle thus can serve as a "look-up table" for binomial expansion values. Also, many of the characteristics of Pascal's Triangle are derived from combinatorial identities; for example, because $\sum_{k=0}^{n}{{n \choose k}}=2^n$, the sum of the values on row $n$ of Pascal's Triangle is $2^n$.

Sum of previous values

One of the best known features of Pascal's Triangle is derived from the combinatorics identity ${n \choose k}+{n \choose k+1} = {n+1 \choose k+1}$. Thus, any number in the interior of Pascal's Triangle will be the sum of the two numbers appearing above it. For example, ${5 \choose 1}+{5 \choose 2} = 5 + 10 = 15 = {6 \choose 2}$. This property allows the easy creation of the first few rows of Pascal's Triangle without having to calculate out each binomial expansion.

Fibonacci numbers

The Fibonacci numbers appear in Pascal's Triangle along the "shallow diagonals." That is, ${n \choose 0}+{n-1 \choose 1}+\cdots+{n-\left\lfloor\frac{n}{2}\right\rfloor \choose \left\lfloor \frac{n}{2}\right \rfloor} = F(n+1)$, where $F(n)$ is the Fibonacci sequence. For example, ${6 \choose 0}+{5 \choose 1}+{4 \choose 2}+{3 \choose 3} = 1 + 5 + 6 + 1 = 13 = F(7)$. A "shallow diagonal" is plotted in the diagram.

Hockey-Stick Identity

The Hockey-Stick Identity states: ${n \choose 0}+{n+1 \choose 1}+\cdots+{n+k \choose k} = {n+k+1 \choose k}$. Its name is due to the "hockey-stick" which appears when the numbers are plotted on Pascal's Triangle, as shown in the representation of the theorem below (where $n=2$ and $k=3$).

[asy] int chew(int n,int r){ int res=1; for(int i=0;i<r;++i){ res=quotient(res*(n-i),i+1); } return res; } for(int n=0;n<9;++n){ for(int i=0;i<=n;++i){ if((i==2 && n<6)||(i==3 && n==6)){ if(n==6){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);} else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);} } else{ label(string(chew(n,i)),(11+n/2-i,-n)); } } } [/asy]

Number Parity

Consider writing the row number $n$ in base two as $({n})_{10} = {(a_xa_{x-1} \cdots a_1a_0)}_2$$= a_x 2^x+a_{x-1} 2^{x-1}+\cdots+a_1 2^1+a_0 2^0$. The number in the $k$th column of the $n$th row in Pascal's Triangle is odd if and only if $k$ can be expressed as the sum of some $a_i 2^i$. For example, $(9)_{10} = {(1001)}_{2} = 2^{3}+2^{0}$. Thus, the only 4 odd numbers in the 9th row will be in the ${(0000)}_{2} = 0$th, ${(0001)}_{2} = 2^0 = 1$st, ${(1000)}_{2} = 2^3 = 8$th, and ${(1001)}_{2} = 2^3+2^0 = 9$th columns. Additionally, marking each of these odd numbers in Pascal's Triangle creates a Sierpinski triangle.

Sierpinski.jpg

Generalization

This is a special case of Kummer's Theorem, which states that given a prime p and integers m,n, the highest power of p dividing $\binom{m}{n}$ is the number of carries in adding $m-n$ and n in base p.

Patterns and Properties of the Pascal's Triangle

Rows

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$, which means there are $2^n$ ways to get to that row from the zeroth row.

Proof: To find the number of ways to get to the $n^{th}$ row of Pascal's Triangle, let's start with the zeroth row. There are $2$ ways to get to the next row because there are $2$ numbers in the first row. Now to get to the second row, we realize that starting from any number on the first row, we have two options to go to in the second row. This means we need to multiply the number of ways to get to the first row by $2$, which gives us $2 \cdot 2 = 2^2 = 4$. This pattern continues, so the number of ways to get to the $n^{th}$ row of Pascal's Triangle is $2^n$.

Diagonals

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.

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Pascal%27s_triangle&oldid=185643"