Difference between revisions of "Pascal's triangle"

(See Also)
(categorize and get rid of tables)
Line 1: Line 1:
<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">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]].
 
'''Pascal's Triangle''' is a triangle which contains the values from the [[binomial expansion]]; its various properties play a large role in [[combinatorics]].
  
Line 21: Line 4:
  
 
=== 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>.
+
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">
 
<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.
 
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.
  
 
=== Fibonacci numbers ===
 
=== Fibonacci numbers ===
 
<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">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.
 
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.
  
 
=== Hockey-stick theorem ===
 
=== 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>
 
  
 
The [[Hockey-stick theorem]] states:
 
The [[Hockey-stick theorem]] states:
Line 93: Line 25:
 
*[[Binomial theorem]]
 
*[[Binomial theorem]]
 
*[[Pascal Triangle Related Problems]]
 
*[[Pascal Triangle Related Problems]]
 +
 +
[[Category:Combinatorics]]
 +
[[Category:Definition]]

Revision as of 13:35, 8 December 2007

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 ${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}$, 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

The Fibonacci numbers appear in Pascal's Triangle along the "shallow diagonals." That is, ${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)$. A "shallow diagonal" is plotted in the diagram.

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.Sierpinski.jpg

See Also

Invalid username
Login to AoPS