Pascal's triangle

From Math Images

Jump to: navigation, search
Image:inprogress.png

Pascal's Triangle

Depicted on the right are the first 11 rows of Pascal's triangle, one of the best-known integer patterns in the history of mathematics. Each entry in the triangle is the sum of the two numbers above it. Pascal's triangle is named after the French mathematician and philosopher Blaise Pascal (1623-1662), who was the first to write an organized work about the properties and applications of the triangle in his treatise, Traité du triangle arithmétique (Treatise on Arithmetical Triangle) in 1653.[1][2]
Pascal's triangle plays important roles in probability theory, in algebra, in combinatorics, and in number theory.


Contents

Basic Description


History of Pascal's Triangle

Despite the fact that the triangle is named Pascal's triangle, the pattern was known long before Pascal wrote his treatise. The first explicit description of Pascal's triangle was by Halayudha, an Indian commentator in his 10th century commentary on Chandah Shastra, an ancient Indian book. Not long after that, Omar Khayyam (around A.D. 1100), a Persian poet and mathematician, and Yang Hui (1238–1298) , a Chinese mathematician, both discussed this arithmetic triangle. Therefore, Pascal's triangle is also called Khayyam-Pascal triangle in Iran and Yang Hui's triangle in China.[1] Yang Hui's triangle is shown in the image below on the left. Notice that in the second row from last, the 4th character from the left is given incorrectly. It should look exactly the same as the character on its immediate right. Pascal's treatise was published posthumously in 1665. Originally, the triangle was rotated 45°. Each entry is the sum of the preceding entries on the horizontal row and on the vertical column, as shown in the image below on the right.[1]

Yang Hui triangle (Pascal's triangle) using rod numerals (1303 AD).
Yang Hui triangle (Pascal's triangle) using rod numerals (1303 AD).
Pascal's original triangle
Pascal's original triangle


Constructing Pascal's Triangle

To construct Pascal's triangle, first put the number 1 into the top row. For the rows below, the number in a given entry is calculated by adding the number above and left of the entry and the number above and right of the entry. If either of the entries above is not present, treat the missing entry as 0 and take the sum in the usual way. As a result, all the entries on the left and right border of the triangle are 1s. Repeatedly calculating the sum, we get Pascal's triangle.
An illustration of the construction of the first five rows of Pascal's triangle.
An illustration of the construction of the first five rows of Pascal's triangle.


The Combinatorial Approach to Pascal's Triangle

Image 1. The first five rows of Pascal's triangle written in combinatorial form.
Image 1. The first five rows of Pascal's triangle written in combinatorial form.

Conventionally, from top to bottom, the rows of Pascal's triangle are numbered n = 0,1,2,... Within each row, from left to right, the entries are numbered r = 0,1,2,3... It is very important to keep this in mind. All contents below follow this naming convention.


Each entry in the triangle on the left is of the form \tbinom{n}{r}, where n is the row number and r is the position of the entry in the row.

\tbinom{n}{r} or C(n,r) or C_r^n, read "n choose r", denotes the number of possible combinations when someone chooses a set of r items from n distinct objects.

In fact, the triangle in Image 1 and Pascal's triangle are exactly the same. In other words, if you calculate the value of each entry in the image you will get Pascal's triangle. (The calculation method is explained in the hidden section below.)


First, it is necessary to distinguish between permutations and combinations.

A permutation of n things taken r at a time is any arrangement (that is, ordering) of r things from a set of n distinct objects. For the first position, there are n choices; for the second position, n – 1 choices;...; for the r th position, (n – r + 1) choices. Therefore, the total number of possible permutations, denoted P(n,r), is

P(n,r) = n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)!}.

A combination of n things taken r at a time is any set (that is, unordered collection) of r things from a set of n distinct objects. For example, if we are picking 3 numbers from the first ten integers, then the sequences (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) and (3,2,1) are 6 different permutations, but they all correspond to one combination, the set {1,2,3}.

More generally, for each combination of r things, there are r! ways to arrange them to get different permutation. Therefore

C(n,r)  = \binom{n}{r} = \frac{P(n,r)}{r!}= \frac{n!}{r!(n-r)!} = \frac{n(n-1)\cdots(n-r+1)}{r!}

where 0 ≤ r ≤ n.

To prove that the triangle in Image 1 and Pascal's triangle are actually the same triangle, we can show that the borders of the two triangles are the same, and that the internal entries, all the entries not on the border, follow the same recurrence pattern:

  • Look at the border entries of Pascal's triangle. Notice that they are all 1s. The border entries of the Image 1 triangle are \tbinom{n}{0} and \tbinom{n}{n}, which numerically all equal 1. Thus, we know that the two triangles have identical borders.
  • The internal entry in each row of Pascal's triangle is calculated by summing the two entries above it. If we want to show the triangle in Image 1 follows the same pattern, we just need to prove that
Eq. 1          \binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}
This is called Pascal's identity.


Suppose we want to choose r people from an n-member committee to form a subcommittee. There can be \tbinom{n}{r} different subcommittees in total. Say we have Mr.X as a member of the committee. There are only two sorts of subcommittees: subcommittees that include X and subcommittees that don't include X.

Case 1: Suppose Mr. X belongs to a subcommittee. Then, among the (n–1) other members in the big committee, we need to select (r–1) people to be in the same subcommittee as Mr. X. There are \tbinom{n-1}{r-1} ways to do this.

Case 2: Suppose now we want to form a subcommittee that Mr. X does not belong to. Then there are \tbinom{n-1}{r} ways to select an r-member subcommittee from the remaining (n–1) members.

The total number of possible r-member subcommittees should equal the sum of the numbers in the two cases above.

Hence,  \tbinom{n}{r} = \tbinom{n-1}{r-1}+\tbinom{n-1}{r}


The algebraic proof is as follows:

Note that

n(n-1)!=n! and (n-r)(n-r-1)!=(n-r)!

This is crucial to the understanding of the proof below.

\binom{n-1}{r-1}+\binom{n-1}{r} =\frac{(n-1)!}{(r-1)!(n-1-r+1)!} + \frac{(n-1)!}{r!(n-1-r)!}
=\frac{r\cdot(n-1)!}{r\cdot(r-1)!(n-r)!} + \frac{(n-1)!\cdot(n-r)}{r!(n-r-1)!\cdot(n-r)}
  =\frac{r(n-1)!}{r!(n-r)!} + \frac{(n-1)!(n-r)}{r!(n-r)!}
=\frac{r(n-1)!+(n-r)(n-1)!}{r!(n-r)!}
  =\frac{(r+n-r)(n-1)!}{r!(n-r)!}
  =\frac{n(n-1)!}{r!(n-r)!}
  =\frac{n!}{r!(n-r)!}
  =\binom{n}{r}



As shown above, the borders of the Image 1 triangle and Pascal's triangle consist of all 1s. With Pascal's identity, we know that the internal entries in each row of the two triangles have the same recurrence pattern. Since both triangles are computed row by row using the same recurrence, they must be the same. For instance, the 0th and 1st rows are the same because they consist of border entries only. Then 2nd rows are the same because the one internal entry is computed the same way from the same 2nd rows. And so on. (To be precise, we have done a proof by mathematical induction on the rows.)



Binomial Coefficients in Pascal's Triangle

Pascal's triangle can be used to determine the coefficients in binomial expansions.

For example,

 (x+y)^0 = 1

 (x+y)^1 = x + y = 1x^1y^0 + 1x^0y^1

 (x+y)^2 = x^2 + 2xy + y^2= 1x^2y^0 + 2x^1y^1 + 1x^0y^2

 (x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3 = 1x^3y^0 + 3x^2y^1 + 3x^1y^2 + 1x^0y^3

Notice that the coefficients of (x+y)n correspond to numbers in row n of Pascal's triangle. In other words,

Eq. 2        (x+y)^n = {n \choose 0}x^n+{n \choose 1}x^{n-1}y+{n \choose 2}x^{n-2}y^2+ \dots + {n \choose k}x^{n-k}y^k+ \dots + {n \choose {n-1}}xy^{n-1}+{n \choose n}y^n .

If we use summation notation, we have

(x+y)^n = \sum_{i=0}^{n}\binom{n}{i}x^{n-i}y^i

Eq. 2 is known as the binomial theorem and \tbinom{n}{r} is the binomial coefficient.

We can use induction on the power n and Pascal's identity to prove the theorem.

We can use induction on the power n and Pascal's identity to prove the theorem.

It is clear that every term in the expansion of (x + y)n is of the form Ckxn-kyk.

The base case is n = 0:  (x+y)^0 = 1, which indeed equals \tbinom{0}{0}x^{0-0}y^0. So Eq. 2 is true when n = 0.

Now assume our assertion in

Eq. 2         holds true for a given n. Then by the inductive hypothesis, we know that
Eq. 3        (x+y)^n = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + \cdots + \binom{n}{n-1}xy^{n-1} + \binom{n}{n}y^n

Then we need to prove it for case n + 1. Because

 (x+y)^{n+1} = x(x+y)^n + y(x+y)^n

We have

(x+y)^{n+1}
= x \left[ \tbinom{n}{0}x^n + \tbinom{n}{1}x^{n-1}y + \tbinom{n}{2}x^{n-2}y^2 + \cdots + \tbinom{n}{n-1}xy^{n-1} + \tbinom{n}{n}y^n \right]
 + y \left[ \tbinom{n}{0}x^n + \tbinom{n}{1}x^{n-1}y + \tbinom{n}{2}x^{n-2}y^2 + \cdots + \tbinom{n}{n-1}xy^{n-1} + \tbinom{n}{n}y^n \right]
= \left[ \tbinom{n}{0}x^{n+1} + \tbinom{n}{1}x^ny + \tbinom{n}{2}x^{n-1}y^2 + \cdots + \tbinom{n}{n-1}x^2y^{n-1} + \tbinom{n}{n}xy^n \right]
 + \left[ \tbinom{n}{0}x^ny + \tbinom{n}{1}x^{n-1}y^2 + \tbinom{n}{2}x^{n-2}y^3 + \cdots + \tbinom{n}{n-1}xy^n + \tbinom{n}{n}y^{n+1} \right]
= \tbinom{n}{0}x^{n+1} + (\tbinom{n}{1}+\tbinom{n}{0})x^ny + (\tbinom{n}{2}+\tbinom{n}{1})x^{n-1}y^2 + \cdots + (\tbinom{n}{n}+\tbinom{n}{n-1})xy^n + \tbinom{n}{n}y^{n+1}

According to Pascal's identity:

\binom{n}{1}+\binom{n}{0} = \binom{n+1}{1}
\binom{n}{2}+\binom{n}{1}=\binom{n+1}{2}
\vdots
 \binom{n}{n}+\binom{n}{n-1}=\binom{n+1}{n}

Also,

\binom{n}{0}=\binom{n+1}{0}=1
\binom{n}{n}=\binom{n+1}{n+1}=1


Therefore,

(x+y)^{n+1} = \binom{n+1}{0}x^{n+1} + \binom{n+1}{1}x^{n}y + \binom{n+1}{2}x^{n-1}y^2 + \cdots + \binom{n+1}{n-1}x^2y^{n-1} + \binom{n+1}{n}xy^n + \binom{n+1}{n+1}y^{n+1}

Our claim holds true for the case of n + 1. The induction proof is therefore complete.

Hence, Eq. 2 is true for all n.




Applications of Pascal's Triangle

Coin Toss Problems

Besides the applications in combinations and binomial expansions that we have seen in previous sections, Pascal's triangle can also be used to find the probability of having a certain outcome when tossing coins.

For example, if we toss a coin twice, we could have any of the following results: Head-Head, Tail-Head, Head-Tail, and Tail-Tail. If we ignore the order of the results, then Tail-Head and Head-Tail are considered the same combination. Therefore, the probabilities of getting both heads, one head and one tail, and both tails are 1/4, 1/2, and 1/4, respectively. We can see that the ratio among the three probabilities is 1:2:1, which is row 2 of Pascal's triangle. See the table below for an illustration of such a pattern in the cases of tossing 1, 2, 3, or 4 coins.


How Many Times the Coin is Tossed Possible Outcomes (H=head, T=tail)Possible Outcomes (Not Differentiating Orders) Probabilities of Each Outcome The Corresponding Line in Pascal's Triangle
1 H,T 1H, 1T \frac{1}{2}, \frac{1}{2} 1,1
2 HH,HT,TH,TT 2H, 1H1T, 2T \frac{1}{4}, \frac{1}{2}, \frac{1}{4} 1,2,1
3 HHH,HHT,HTH,THH,HTT,THT,TTH,TTT 3H, 2H1T, 1H2T, 3T \frac{1}{8}, \frac{3}{8}, \frac{3}{8}, \frac{1}{8} 1,3,3,1
4 HHHH, HHHT, HHTH, HTHH, THHH,HHTT, HTHT, HTTH, THHT, THTH, TTHH,HTTT, THTT, TTHT, TTTH,TTTT 4H, 3H1T, 2H2T, 1H3T, 4T \frac{1}{16}, \frac{1}{4}, \frac{3}{8}, \frac{1}{4}, \frac{1}{16} 1,4,6,4,1


With Pascal's triangle, we can easily answer questions like this: What is the probability of getting exactly 2 heads with 3 coin tosses?

Adding the entries of the third row of Pascal's triangle, we get 1+3+3+1=8 possible outcomes, where order matters. (Or, calculate 23 and it gives the same result. This is a property we will introduce later in the sum of rows section.) 3 of these 8 possible outcomes give exactly 2 heads, therefore the probability of getting exactly 2 heads from 3 coin tosses is 3/8=37.5%.

More generally, if you toss a coin n times, the probability of having m heads is

\frac{\text{Entry m of row n in Pascal triangle}}{\text{Sum of the entries of row n}}


For example, the chance of tossing the coin 8 times and getting 6 heads can be calculated this way:

Find the entry 6 of row 8 in Pascal's triangle, which is 28.

Divide it by the sum of row 6:

 \frac {28}{2^8} = 10.94%


This way of calculating probability using Pascal's triangle is not limited to coin tosses. It can be used in various similar situations when there are exactly two equally possible outcomes for an event, and you need to calculate the chance of getting a certain combination of results. For example, if a person has a 50% chance of shooting a basketball into a hoop, we can use Pascal's triangle to calculate the probability of him getting the ball into the hoop 3 times out of 10 throws (check the entry in position 3 of row 10).


Patterns and Properties

People have discovered countless relations and patterns in Pascal's triangle. Many discoveries are fairly recent despite the fact that Pascal's triangle has been studied for centuries.

The following patterns and properties are going to be discussed in this section:


The Flash animation on the right allows you to explore some of the patterns present in Pascal's triangle.

Symmetry and Borders

Image:Pascals-triangle-symmetry.gif
  • Every row in Pascal's triangle begins and ends with a 1. This is because \tbinom{n}{0}=\tbinom{n}{n}=1
Conceptually, imagine we are picking people from an n-member committee to form subcommittees. There is only one way to form an empty subcommittee, and one way to include everyone in the subcommittee. That is why \tbinom{n}{0}=\tbinom{n}{n}=1.
  • The triangle is symmetrical. The numbers on the left side of the triangle have identical numbers on the right side. For instance, look at row 5. The element 10, which is the 3rd entry from the left, is also the 3rd entry from the right in the row. This is because \tbinom{n}{r}=\tbinom{n}{n-r}
Recall that \tbinom{n}{r} gives the number of possible r-member subcommittees chosen from an n-member committee. \tbinom{n}{n-r} counts the number of (n – r )-member subcommittees. But in picking an n-member subcommittee, we inevitably pick an (n – r )-member subcommittee at the same time, namely the people we left out. In other words, there is a one-to-one correspondence between r-member subcommittees and (n – r )-member subcommittees. Therefore, \tbinom{n}{r}=\tbinom{n}{n-r}.


Sum of Rows

Look at the horizontal sums of Pascal's triangle. For row n, the horizontal sum equals 2n.

We can prove this property through the combinatorial interpretation of the triangle. One of the properties of combinations is that

\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n-1} + \binom{n}{n} = 2^n

Why is this true? Suppose we are picking people from the n-member committee again.

The left side of the equation counts the subcommittees by how many people are in the subcommittee: \tbinom{n}{0} counts the number of 0-member subcommittees; \tbinom{n}{1} counts the number of 1-member subcommittees; etc.

One way of forming subcommittees is to ask the committee members one by one, "do you want to join subcommittee X?" Each individual has two choices: "Yes, I will join" and "No, I don't want to join". The total number of possible subcommittees is then 2n, which is the right side of the equation.

Therefore, the sum of the entries of row n in Pascal's triangle should equal 2n.


There is another way to prove that the horizontal sums of row n is 2n:


Let a_0, a_1, a_2, ... , a_n be the sequence of any row n in Pascal's triangle, and let b_0, b_1, b_2, ..., b_n, b_{n+1} be the sequence of the row right below the ai sequence.

Then the sum of the entries of the sequence b_0, b_1, b_2, ... , b_n, b_{n+1} can be written as:

b_0 + b_1 + b_2 + ... + b_n + b_{n+1}

=a_0 + (a_0 + a_1) + (a_1 + a_2) + ... + (a_{n-1} + a_n) + a_n

=2a_0 + 2a_1 + 2a_2 + ... + 2a_{n-1} + 2a_n

=2(a_0 + a_1 + a_2 + ... + a_n)

Thus, the sum of entries of any row is twice the sum of the entries in the previous row.

Since the sum of entries for row 0 is 1, the sum of the entries of row n in the triangle equals 2n.



Hockey Stick Pattern

Hockey stick patterns in Pascal's triangle
Hockey stick patterns in Pascal's triangle

As illustrated in the picture on the left, we can find figures that look like hockey sticks in Pascal's triangle.

One end of the hockey stick lies on the border of the triangle -- in other words, on any entry of 1 in the triangle.

The handle of the stick consists of numbers inside the boundaries colored in the picture, which are located in different rows of Pascal's triangle so that the hockey stick does not lie horizontally.

The head of the hockey stick, or the colored cell, should not be aligned in the same direction as the handle.

The sum of all the numbers in the handle equals the number in cell that is the head of the hockey stick. For instance, look at the blue hockey stick. When we add the numbers positioned on the straight line, we get 1+3+6=10, which is the number at the head of the blue stick.

We use mathematical induction to prove this property.

Recall that we can use C_m^n = \tbinom{n}{m} to denote entry m in row n of Pascal's triangle.

First, we want to prove the blue case, when the stick tilts to the right, that

\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-2}{m-1} + \cdots + \binom{m-1}{m-1}

The left hand side (LHS) of the equation above is the head of the hockey stick, and all the elements on the right hand side (RHS) of the equation are from the handle. The first element, \tbinom{n-1}{m-1}, is the entry adjacent to the head. As we can see from the image, if the position of the head is entry m of row n, the closest entry that is part of the handle would be entry m – 1 of row n – 1. Since the handle tilts to the right, all the entries on the handle are at position m – 1 of their individual rows. The end of the handle lies on the border. Therefore, the last element on the right side of the equation should be \tbinom{m-1}{m-1}.

We can use induction on n, the row of the hockey stick head, to prove this property.

The base case is when n = 1. (If n = 0, there is no hockey stick handle possible). In this case, m = 1. Because

LHS=\tbinom{1}{1} = 1
RHS=\tbinom{0}{0} = 1

we know our assertion is true for the base case.

Next, we will show that if the assertion holds true for n = k, then it also holds true for n = k + 1. Because of Pascal's identity, we know that

\binom{k+1}{m} = \binom{k}{m-1} + \binom{k}{m}

By the inductive hypothesis, we know that

\binom{k}{m} = \binom{k-1}{m-1} + \binom{k-2}{m-1} + \cdots + \binom{m-1}{m-1}

Substituting this expression of \tbinom{k}{m} into the equation above for \tbinom{k+1}{m},

\binom{k+1}{m} = \binom{k}{m-1} + \binom{k-1}{m-1} + \binom{k-2}{m-1} + \cdots + \binom{m-1}{m-1}

Hence, the hockey stick assertion holds true for m = k + 1 when it is true for m = k. The induction is complete.

Now, we have proved the property for the blue stick case. The red stick case can be proven in a similar way since Pascal's triangle is symmetrical.



Hidden Hexagon Squares

An example of the Star of David property in Pascal's triangle Pascal's triangle contains a magic hexagon pattern.

If we look at the nearest six elements around \tbinom{n}{r}, which follow a hexagonal pattern, we will find that the product of the elements at every other vertex equals the product of the three remaining elements.

This property was discovered by V.E. Hoggatt, Jr. and W. Hansell in 1971 and is called the Hoggatt-Hansell identity. Later, Gould called it the Star of David property.[3]

The image on the left contains selected elements in row 5, 6, and 7 of Pascal's triangle. They can be the six vertices of a hexagon, and 5 × 20 × 21 = 6 × 10 × 35 = 2100.

Algebraically, this pattern means that
Eq. 4        \binom{n-1}{r-1}\binom{n}{r+1}\binom{n+1}{r} = \binom{n-1}{r}\binom{n+1}{r+1}\binom{n}{r-1}


The left hand side of Eq. 4 is,

\binom{n-1}{r-1}\binom{n}{r+1}\binom{n+1}{r}

Using the formula for combinations, the left hand side becomes

\frac{(n-1)!}{(r-1)!(n-r)!}\cdot\frac{(n)!}{(r+1)!(n-r-1)!}\cdot\frac{(n+1)!}{r!(n-r+1)!}

Changing the positions of the denominators, this equals

\frac{(n-1)!}{r!(n-r-1)!}\cdot\frac{(n+1)!}{(r+1)!(n-r)!}\cdot\frac{n!}{(r-1)!(n-r+1)!}

Using the notation of combinations, this may be rewritten as

\binom{n-1}{r}\binom{n+1}{r+1}\binom{n}{r-1}

which is the right hand side of Eq. 4


This identity also implies that the product of all the numbers at the vertices of the hexagon is a square.


Sierpinski Triangle

The distribution of odd and even numbers in Pascal's triangle
The distribution of odd and even numbers in Pascal's triangle
When we color the odd and even numbers in Pascal's triangle with two different colors, we observe an interesting recursive pattern that resembles Sierpinski's triangle.

The more rows we consider, the more accurate the resemblance is.

More generally, numbers in Pascal's triangle can be colored differently according to whether or not they are divisible by 3[4], 4[5],5[6] etc.; this results in similar patterns.


Exponents of 11

As we can see in the image, each line in Pascal's triangle is a power of 11.

This pattern is clear for the first four rows, but starting at row 5, it becomes harder to see. The reason is:

In order to keep the one-digit format, we carry the 1 in the second 10 to the left to yield 11 and carry the 1 in 11 to its left to yield 6.

Image:Pascals-triangle-powers-11-overlap.gif

More generally speaking, look at the cells horizontally from right to left. If the number in the cell has two digits, add the number in the tens position of this number to the number on its left.


This pattern holds for all n ≥ 0 because

11^n = (10+1)^n = \binom{n}{0}10^n + \binom{n}{1}10^{n-1} + \cdots + \binom{n}{n-1}10 + \binom{n}{n}

Therefore, the units position of 11n is the value of \tbinom{n}{n}; the tens position is the value of \tbinom{n}{n-1}; the hundreds position is the value of \tbinom{n}{n-2}...
For example,

 11^4 = \binom{4}{0}10^4 + \binom{4}{1}10^3 + \binom{4}{2}10^2 + \binom{4}{3}10 + \binom{4}{4} = 1\cdot10^4 + 4\cdot10^3 + 6\cdot10^2 + 4\cdot10 + 1 = 14641

If the value of \tbinom{n}{r} has more than one digit, then we would have to go through the carrying procedure illustrated in the image above.



Similarly, Pascal's triangle can be used to compute the powers of 101, 1001, 10001, and more generally numbers of the form 1\underbrace{00...0}_{\text{all zeros}}1.

For example, consider the exponents of 101:

1010 = 01
1011 = 1 01
1012 = 1 02 01
1013 = 1 03 03 01
1014 = 1 04 06 04 01
1015 = 1 05 10 10 05 01
1016 = 1 06 15 20 15 06 01
1017 = 1 07 21 35 35 21 07 01
1018 = 01 08 28 56 70 56 28 08 01
1019 = 01 09 36 85 27 26 84 36 09 01

The various powers of 101 corresponds to the rows in Pascal's triangle nicely until 1019. Because \tbinom{9}{4}=\tbinom{9}{5}=126 has three digits, we carry the 1 in the right 126 to the left to get 127, and carry the 1 in 127 to its left to get \tbinom{9}{3}+1 = 85. After this process, there are no more three-digit entries. Therefore, we get the answer 1093685272684360901.

The mathematical proof works in a similar way as the proof for exponents of 11.


Fibonacci Sequence

By adding the diagonal entries of Pascal's triangle in the way shown on the left, we can find Fibonacci numbers.


Diagonals

In this section, we will focus on the down-left diagonals (the diagonals that go between lower left and upper right). However, the down-right diagonals have the same patterns and properties since Pascal's triangle is symmetrical.

Note: Keep in mind that the top row is called row 0, and the very left entry of each row is entry 0, or position 0.

  • Entry 0 in each row is always 1 because \tbinom{n}{0}=1, so the leftmost down-left diagonal is all 1's.
  • After the edge numbers, the next diagonal line of numbers (formed by the entries in the 1 positions of each row) are the natural numbers: 1, 2, 3, 4, 5, ...
  • The next set of diagonal numbers after the natural numbers (formed by entries in the 2 positions of each row) are the triangular numbers
As illustrated in the image below, the sequence of triangular numbers begins as 1, 3, 6, 10, 15, 21, ...

image:Triangular.jpg

This property of Pascal's triangle can be written in an algebraic equation:
t_n = \frac{n(n+1)}{2} = \binom{n+1}{2}
that is, the nth triangular number (denoted as tn) appears as entry 2 in row n + 1 of Pascal's Triangle.
  • After the triangular numbers, we have tetrahedral numbers, formed by entries in position 3 of each row.
The tetrahedral numbers begin as 1, 4, 10, 20, 35, ... and the image on the right depicts the 5th tetrahedral number.
The algebraic form of this property of Pascal's triangle is:
 T_n = \frac{n(n+1)(n+2)}{6} = \binom{n+2}{3},
that is, the nth tetrahedral number (denoted as Tn) appears as entry 3 in row n + 2 of Pascal's Triangle.
  • The next d-diagonal contains the next highest dimensional "d-simplex" numbers.
Image:tetrahedral.jpg
  • The sum of entries at the 2 positions from two adjacent rows is a square. For example, 1 + 3 = 22, 3 + 6 = 32, 6 + 10 = 42. This result was discovered by Theon of Smyrna around A.D.100, but he stated it in terms of triangular numbers, that the sum of two consecutive triangular numbers is a square.[3] The property holds true because
t_n + t_{n+1} =  \frac{n(n+1)}{2} + \frac{(n+1)(n+2)}{2} = \frac{2n^2 + 4n + 2}{2} = (n+1)^2
This property can be demonstrated visually. An illustration is provided on the right.
Imagine you have two right triangles consisting of tn and tn+1 dots respectively. The dots in both triangles are arranged in a similar pattern to those in the illustrations shown when we introduced triangular numbers, except that the equilateral triangles are now distorted to be right isosceles triangles. Put these two triangles side by side and flip one of them upside down, and you get a square consisting of dots. Each side of the square has n + 1 dots. The total number of dots is a square number.
  • The difference between the squares of the entries at 2 positions from adjacent rows is the cube of the difference of the entries themselves. For example, 32 - 12 = (3 - 1)3, 62 - 32 = (6 - 3)3, 102 - 62 = (10 - 6)3. This property was discovered by V. F. Ivanoff of San Francisco, Califormia, in 1933.[3]
Why?
This pattern exists because for triangular numbers, we have t_n = \tbinom{n+1}{2}. Therefore,
t_{n+1}-t_n=n+1
t_{n+1}+t_n=(n+1)^2
Hence,
t_{n+1}^2 - t_n^2 = (t_{n+1}+t_n)(t_{n+1}-t_n) = (n+1)^3 = (t_{n+1}-t_n)^3
  • Consider the positive difference between entry 3's from rows two apart. The difference is always a square. For example, 10 - 1 = 32, 20 - 4 = 42, 35 - 10 = 52.
This is true because
T_n-T_{n-2} = \binom{n+2}{3} - \binom{n}{3}
  = \binom{n+1}{2} + \binom{n+1}{3} - \binom{n}{3}
  = \binom{n+1}{2} + \binom{n}{2}
  = t_n+t_{n-1} = n^2


Patterns about Primes

  • Given a row, if entry 1, let's call it p, is a prime, then all the internal entries (entries excluding the 1's) in that row are divisible by p. For example, entry 1 in row 7 is 7, which is a prime, and all the internal numbers in the row, namely, 7 , 21 and 35, are divisible by 7.


From combinatorics, we know that

\binom{p}{k}=\frac{p!}{(p-k)!k!}=\frac{p(p-1)!}{(p-k)!k(k-1)!}=\frac{p}{k} \cdot \frac{(p-1)!}{(p-k)!(k-1)!}

Since (p – k)! can be written as [(p – 1) – (k – 1)]!, we have

\binom{p}{k}=\frac{p}{k} \cdot \frac{(p-1)!}{[(p-1)-(k-1)]!(k-1)!} = \frac{p}{k}\binom{p-1}{k-1}

Therefore,

Eq. 5        k\binom{p}{k}=p\binom{p-1}{k-1}

Now let p be a prime, and 0 ≤ kp. Then entry 1 in row p is p, and the internal entries are \tbinom{p}{k}.

Since k < p (we are only considering internal entries now) and p is a prime, p and k share no common factor except 1. Eq. 5 shows that p is a factor of k\tbinom{p}{k}. Because p is not a factor of k, it has to be a factor of \tbinom{p}{k}. So, p divides \tbinom{p}{k}. In other words, all the internal entries in row p are divisible by p.


  • If p is a prime, then every internal entry in row pn is divisible by p, where n is any positive integer. For example, p = 2 and n = 3. Row 8 of Pascal's triangle is 1 8 28 56 70 56 28 8 1. We can see that all the internal entries are divisible by 2. Similarly, if p = 5 and n = 3, we will find that all internal entries in row 125 are divisible by 5.


We need to prove that if p is a prime and n is a positive integer, then \tbinom{p^n}{k} is divisible by p, where 0 < k < pn.

Changing the p in Eq. 5 to pn, we have

k\binom{p^n}{k}=p^n\binom{p^n-1}{k-1}

This equation still holds true because Eq. 5 is a general property of combinations no matter what values p, n and k are chosen.

Because p is a prime, pn has (n + 1) factors, namely 1, p, p2, p3, ..., pn.

Since k < pn, we know that k and pn can have at most n common factors (including 1). Therefore, there is at least one factor of pn besides 1 that divides \tbinom{p^n}{k}. This factor is definitely an exponent of p, as shown above in the list of factors of pn. Hence, p divides all \tbinom{p^n}{k}, or in other words, all the internal entries of row pn.



Other Patterns and Properties

  • All entries in row n are odd if and only if the binary representation of n consists of 1s. For example, 3 = 11two, and all entries in row 3 (1 3 3 1) are odd. 15 = 1111two. Consequently, all entries in row 15 (1 15 105 455 1365 3003 5005 6435 5005 3003 1365 455 105 15 1) are odd.
  • Rows 2, 7 and 14 have triplets containing consecutive elements that form an arithmetic progression. For example, 0-1-2, 7-21-35, and 1001-2002-3003. In fact, there are infinitely many such triples of consecutive binomial coefficients that form an arithmetic progression. This result was established in 1946 by T. Motzkin of Jerusalem.[3]
  • We can compute Catalan numbers from Pascal's triangle. We can divide the entry in the center of row 2n in Pascal's triangle by n + 1 and get the nth Calatan number. For example,  C_4 = \frac{1}{5} \binom{8}{4} =\frac{70}{5} =14.
There are many more ways to extract Catalan numbers from Pascal's triangle. Refer to the Catalan Numbers page for more information.







Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.




References

  1. 1.0 1.1 1.2 Wikipedia (Pascal's Triangle). (n.d.). Pascal's Triangle. Retrieved from http://en.wikipedia.org/wiki/Pascal%27s_triangle
  2. Pickover, Clifford A.(2009). The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics Sterling. ISBN 978-1-4027-5796-9
  3. 3.0 3.1 3.2 3.3 Koshy, Thomas(2011). Triangular Arrays With Applications. Oxford University Press. ISBN 978-0-19-974294-3
  4. English Wikipedia:Pascal's triangle with those numbers not divisible by 3 shaded. Found at http://en.wikipedia.org/wiki/File:Pascal%27s_Triangle_divisible_by_3.svg
  5. Pascal's triangle with those numbers not divisible by 4 shaded. Found at http://lt.wikipedia.org/wiki/Vaizdas:Pascal%27s_Triangle_divisible_by_4.svg
  6. Pascal's triangle with those numbers not divisible by 5 shaded. Found at http://lt.wikipedia.org/wiki/Vaizdas:Pascal%27s_Triangle_divisible_by_5.svg


[1]Koshy, Thomas(2011). Triangular Arrays With Applications. Oxford University Press. ISBN 978-0-19-974294-3
[2]Edwards, A.W.F.(1987). Pascal's Arithmetical Triangle. Charles Griffin & Company Limited, Oxford University Press. ISBN 0-85264-283-0
[3]Maurer, Stephen B., Ralston, Anthony(2004). Discrete Algorithmic Mathematics. A K Peters, Ltd. ISBN 1-56881-166-7
[4]Wikipedia (Binomial Theorem). (n.d.). Binomial Theorem. Retrieved from http://en.wikipedia.org/wiki/Binomial_theorem
[5]Wikipedia (Yang Hui). (n.d.). Yang Hui. Retrieved from http://en.wikipedia.org/wiki/Yang_Hui
[6]Pierce, Rod.(10 May 2012). "Pascal's Triangle". Math Is Fun. Retrieved from http://www.mathsisfun.com/pascals-triangle.html

Future Directions for this Page

  • Make an image page for combinations and move some of the information about binomial coefficients, combinations, combinatorial notations, or proofs about combinatorial properties there so that this page can be shorter.



If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Personal tools