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"
(Major modifications/addition for entire article)
Line 1: Line 1:
−
== Definition ==
+
<div class="thumb tright">
−
Pascal's triangle is a triangle in which every number is the sum of the two numbers directly above it. The first few rows of Pascal's Triangle are depicted below.
+
<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 ==
 +
 
 +
=== 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, 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 identities involving binomial expansions; 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 ===
 +
 
 +
<div class="thumb tright">
 +
<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">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.
  
−
== Uses ==
+
=== Fibonacci numbers ===
−
Pascal's triangle has many interesting uses and applications.
 
  
 
<div class="thumb tright">
 
<div class="thumb tright">
−
<div style="width:250px;">
+
<div>
−
1
+
<div>
−
1   1
+
<table border="0">
−
  1   2   1
+
<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>
−
'''1'''   '''3'''   3   1
+
<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>
−
1   '''4'''   6  4   1
+
<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>
−
1   5 10 10   5   1
+
<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>
−
<div class="thumbcaption">
+
<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>
−
Pascal's Triangle</div>
+
<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 numbers]] appear in Pascal's Triangle along the [[shallow diagonals]]; explicitly; <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>.  The "shallow diagonal" for this expression is plotted in the diagram.
 +
 
 +
 
 +
=== Hockey-stick theorem ===
 +
 
 +
<div class="thumb tright">
 +
<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>
 
</div>
 
</div>
  
−
=== Binomial Coefficients ===
+
The [[Hockey-stick theorem]] states:
−
It can be noted that the numbers in Pascal's triangles are the [[binomial coefficients]].  This means that every number in Pascal's Triangle can be expressed as <math>\displaystyle{n\choose k-1}</math>, where n is the row number, and k is the place in the row.  For example, <math>\displaystyle{5\choose 3}</math> would represent the 5th row, and the 4th number in it.  It should be noted here that the first row of Pascal's Triangle is considered to be the row 1, 1, meaning that the "[[apex]]" of Pascal's Triangle is considered "Row 0."
+
<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>
  
−
=== Counting & Probability ===
+
=== Number Parity ===
−
If we flip x coins, and want to know what the probability is that y of them are heads, then we go to the xth row, and find the (y+1)th number (call this a).  Then, we find the sum of the numbers in the xth row (call this b).  Then, the probability is simply <math>\frac{a}{b}</math>
+
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]].
  
 
==See Also==
 
==See Also==
 
*[[Binomial theorem]]
 
*[[Binomial theorem]]

Revision as of 23:29, 24 June 2006

1
11
121
1331
14641
15101051
1615201561
First few rows of Pascal's Triangle

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

Pascal's Triangle is defined such that the number in row $n$ and column $k$ is $\displaystyle{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 $\displaystyle{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 identities involving binomial expansions; 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

1
11
121
1331
14641
15101051
1615201561
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}$, 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.

Fibonacci numbers

1
11
121
1331
14641
15101051
1615201561
Shallow diagonals

The Fibonacci numbers appear in Pascal's Triangle along the shallow diagonals; explicitly; ${n \choose 0}+{n-1 \choose 1}+\cdots+{n-\lfloor\frac{n}{2}\rfloor \choose \lfloor \frac{n}{2} \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 + 2 = 13 = F(7)$. The "shallow diagonal" for this expression is plotted in the diagram.


Hockey-stick theorem

1
11
121
1331
14641
15101051
1615201561
Hockey-stick Theorem

The Hockey-stick theorem 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 to the right (where $n=2$ and $k=3$

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.

See Also

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