Difference between revisions of "Pascal Triangle Related Problems"

m (text is staying to the left...)
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
==The triangle==
+
==The Triangle==
  
Here are lines zero through twelve of Pascal's triangle:
+
Here are lines zero through eight of Pascal's triangle:
  
  Row 0:                                                 1                                               
+
  Row
  Row 1:                                             1    1                                           
+
0:                           1                                               
  Row 2:                                           1    2    1                                         
+
  1:                       1    1                                           
  Row 3:                                       1    3    3    1                                       
+
  2:                     1    2    1                                         
  Row 4:                                     1    4    6    4    1                                   
+
  3:                 1    3    3    1                                       
  Row 5:                                 1    5    10    10    5    1                                 
+
  4:               1    4    6    4    1                                   
  Row 6:                               1    6    15    20  15    6   1                             
+
  5:           1    5    10    10    5    1                                 
  Row 7:                           1    7    21    35    35    21    7    1                           
+
  6:         1    6    15    20  15    6     1                             
  Row 8:                         1    8    28    56    70    56    28    8    1                       
+
  7:     1    7    21    35    35    21    7    1                           
Row 9:                     1    9    36    84    126  126  84    36    9    1                     
+
  8:   1    8    28    56    70    56    28    8    1                       
  Row 10:                 1    10    45    120  210  252  210  120  45    10  1                 
+
<!-- 9:     1    9    36    84    126  126  84    36    9    1                     
  Row 11:               1    11    55  165  330    462  462  330  165  55    11  1               
+
  10: 1    10    45    120  210  252  210  120  45    10  1                 
  Row 12:           1    12    66    220  495  792  924  792  495  220  66    12  1          
+
  11:   1    11    55  165  330    462  462  330  165  55    11  1               
 +
  12:1    12    66    220  495  792  924  792  495  220  66    12  1-->       
 
   
 
   
'''Problem 1'''
+
== Introductory ==
 +
=== Problem 1 ===
  
You are given the binomial <math>x+y</math>. Raise it to the 10th power.
+
Given <math>\displaystyle (x + y)^{10}</math>, find:
  
Find:
+
# The coefficient of the <math>x^{4}y^{6}</math> term.
 +
# The sum of the coefficients.
  
1. The coefficient of the <math>x^{4}y^{6}</math> term.
+
<br>'''Solution'''
  
2. The sum of the coefficients.
+
1. You need to find the 6th number (remember the first number in each row is considered the 0th number) of the 10th row in Pascal's triangle.
 
 
'''Solution'''
 
 
 
1. You need to find the 6th number (remember the first column on each row is considered the 0th number) of the 10th row in Pascal's triangle.
 
  
 
The 10th row is:
 
The 10th row is:
  
  Row 10:                  1     10   45   120   210   252   210   120   45   10   1
+
  1 10 45 120 210 252 210 120 45 10 1
  
 
Thus the coefficient is the 6th number in the row or <math>\displaystyle{210}</math>.
 
Thus the coefficient is the 6th number in the row or <math>\displaystyle{210}</math>.
Line 39: Line 38:
 
This can also be found using the binomial theorem:
 
This can also be found using the binomial theorem:
  
<math>(x+y)^{k}=\sum^{k}_{n=0}\displaystyle{k\choose n}x^{n}y^{k-n}</math>
+
::<math>(x+y)^{k}=\sum^{k}_{n=0}\displaystyle{k\choose n}x^{n}y^{k-n}</math>
  
 
Through the summation, the binomial theorem will provide you with the coefficient if each term of the result.  In our particular case, we are only looking for the coefficient of the <math>\displaystyle{x^{4}y^{6}}</math> term.
 
Through the summation, the binomial theorem will provide you with the coefficient if each term of the result.  In our particular case, we are only looking for the coefficient of the <math>\displaystyle{x^{4}y^{6}}</math> term.
Line 49: Line 48:
 
2.  Since all the coefficients are found in the 10th row, we simply need to add the numbers in the 10th row together.  This can be done by hand since there are relatively few numbers, but we could also use the following formula to sum up the numbers:
 
2.  Since all the coefficients are found in the 10th row, we simply need to add the numbers in the 10th row together.  This can be done by hand since there are relatively few numbers, but we could also use the following formula to sum up the numbers:
  
<math>\sum_{n=0}^{k}{k \choose n}=2^k</math>
+
::<math>\sum_{n=0}^{k}{k \choose n}=2^k</math>
  
 
This summation formula simply adds up all the coefficients since <math>\displaystyle{k\choose n}</math> gives us each of the coefficients.  So, the sum is <math>2^{10}=1024</math>.
 
This summation formula simply adds up all the coefficients since <math>\displaystyle{k\choose n}</math> gives us each of the coefficients.  So, the sum is <math>2^{10}=1024</math>.
  
For your information, the final polynomial which results from <math>(x+y)^{10}</math> is:
+
For your information, the final polynomial which results from <math>(x+y)^{10}</math> is <math>\displaystyle x^{10} + 10x^9y + 45x^8y^2 + 120x^7y^3 + 210x^6y^4 + 252x^5y^5</math><math> + 210x^4y^6 + 120x^3+y^7 + 45x^2+y^8+10x^1y^9+y^{10}</math>
<math>x^{10} + 10x^9y + 45x^8y^2 + 120x^7y^3 + 210x^6y^4 + 252x^5y^5 + 210x^4y^6 + 120x^3+y^7 + 45x^2+y^8+10x^1y^9+y^{10}</math>
+
 
 +
== Intermediate ==
 +
=== Problem 1 ===
 +
<div style="text-align:right;">[[1992 AIME Problems/Problem 4|1992 AIME, # 4]]</div>
 +
In Pascal's Triangle, each entry is the sum of the two entries above it. In which row of Pascal's Triangle do three consecutive entries occur that are in the ratio <math>3: 4: 5</math>?
 +
 
 +
[[1992 AIME Problems/Problem 4|Solution]]
 +
 
 +
=== Problem 2 ===
 +
<div style="text-align:right;">Source: [[2007 AIME II Problems/Problem 13|2007 AIME II, # 13]]</div>
 +
A [[triangle|triangular]] [[array]] of [[square]]s has one square in the first row, two in the second, and in general, <math>k</math> squares in the <math>k</math>th row for <math>1 \leq k \leq 11.</math> With the exception of the bottom row, each square rests on two squares in the row immediately below (illustrated in given diagram). In each square of the eleventh row, a <math>0</math> or a <math>1</math> is placed. Numbers are then placed into the other squares, with the entry for each square being the sum of the entries in the two squares below it. For how many initial distributions of <math>0</math>'s and <math>1</math>'s in the bottom row is the number in the top square a [[multiple]] of <math>3</math>?
 +
 
 +
[[Image:2007 AIME II-13.png]]
 +
 
 +
[[2007 AIME II Problems/Problem 13|Solution]]
 +
 
 +
== Olympiad ==
 +
{{stub}}
 +
 
 +
[[Category:Introductory Combinatorics Problems]] [[Category:Intermediate Combinatorics Problems]]

Revision as of 17:46, 4 May 2007

The Triangle

Here are lines zero through eight of Pascal's triangle:

Row
0:                           1                                              
1:                        1     1                                           
2:                     1     2    1                                         
3:                  1     3     3    1                                      
4:               1     4     6     4    1                                   
5:            1     5     10    10    5    1                                
6:         1     6     15    20   15    6     1                             
7:      1     7     21    35    35    21    7    1                          
8:   1     8     28    56    70    56    28    8    1                       

Introductory

Problem 1

Given $\displaystyle (x + y)^{10}$, find:

  1. The coefficient of the $x^{4}y^{6}$ term.
  2. The sum of the coefficients.


Solution

1. You need to find the 6th number (remember the first number in each row is considered the 0th number) of the 10th row in Pascal's triangle.

The 10th row is:

1  10  45  120  210  252  210  120  45  10  1

Thus the coefficient is the 6th number in the row or $\displaystyle{210}$.

This can also be found using the binomial theorem:

$(x+y)^{k}=\sum^{k}_{n=0}\displaystyle{k\choose n}x^{n}y^{k-n}$

Through the summation, the binomial theorem will provide you with the coefficient if each term of the result. In our particular case, we are only looking for the coefficient of the $\displaystyle{x^{4}y^{6}}$ term.

Since you are looking for $\displaystyle{x^{4}y^{6}}$ term in $\displaystyle{(x+y)^{10}}$, then $\displaystyle{n=4}$ and $\displaystyle{k=10}$.

So the coefficient of the $\displaystyle{x^{4}y^{6}}$ term is $\displaystyle{10\choose 4}=210$.

2. Since all the coefficients are found in the 10th row, we simply need to add the numbers in the 10th row together. This can be done by hand since there are relatively few numbers, but we could also use the following formula to sum up the numbers:

$\sum_{n=0}^{k}{k \choose n}=2^k$

This summation formula simply adds up all the coefficients since $\displaystyle{k\choose n}$ gives us each of the coefficients. So, the sum is $2^{10}=1024$.

For your information, the final polynomial which results from $(x+y)^{10}$ is $\displaystyle x^{10} + 10x^9y + 45x^8y^2 + 120x^7y^3 + 210x^6y^4 + 252x^5y^5$$+ 210x^4y^6 + 120x^3+y^7 + 45x^2+y^8+10x^1y^9+y^{10}$

Intermediate

Problem 1

In Pascal's Triangle, each entry is the sum of the two entries above it. In which row of Pascal's Triangle do three consecutive entries occur that are in the ratio $3: 4: 5$?

Solution

Problem 2

A triangular array of squares has one square in the first row, two in the second, and in general, $k$ squares in the $k$th row for $1 \leq k \leq 11.$ With the exception of the bottom row, each square rests on two squares in the row immediately below (illustrated in given diagram). In each square of the eleventh row, a $0$ or a $1$ is placed. Numbers are then placed into the other squares, with the entry for each square being the sum of the entries in the two squares below it. For how many initial distributions of $0$'s and $1$'s in the bottom row is the number in the top square a multiple of $3$?

2007 AIME II-13.png

Solution

Olympiad

This article is a stub. Help us out by expanding it.