Pascal's Triangle2

Pascal's Triangle
Field: Algebra
Image Created By: The Math Forum @ Drexel

Pascal's Triangle

Pascal's Triangle

Basic Description

Pascal's triangle is a triangular arrangement of certain numbers that show interesting patterns. We start out with 1 on the top row, which we will label as row 0. Every entry from the next row is the sum of the two numbers above it. If a number is absent on the diagonal left or the right, replace that empty entry with 0 and find the sum. We can repeat this process endlessly.

Image 1

For instance, let's look at a row $1, 4, 6, 4, 1$. This row can be seen as $0, 1, 4, 6, 4, 1, 0$. We can find the entries for the next row by following the method above. The next row will be $0+1=1, 1+4=5, 4+6=10, 4+1=5, 1+0=1$.

Pascal's triangle was first introduced in Pascal's paper Treatise on the Arithmetic Triangle published posthumously in 1665. In his original paper, the the triangle was rotated 45° so that each entry is the sum of the two preceding entries on the horizontal row and the vertical column, as shown in Image 1.

A More Mathematical Explanation

[Click to view A More Mathematical Explanation]

Constructing Pascal's Triangle

There is a mathematical rule to constructing Pascal's triangle. [...]

[Click to hide A More Mathematical Explanation]

Constructing Pascal's Triangle

There is a mathematical rule to constructing Pascal's triangle. This general rule is not necessary for the readers' understanding of the following sections, but it is helpful for the readers' understanding of the proofs of certain sections.

[Click here to show more.]

Let ${\color{Gray}\alpha}$ be a sequence ${\color{Gray}a_0, a_1, \dots, a_n}$ for some ${\color{Gray}n=0, 1, 2}$ Then we can

[Click here to hide]

Let $\alpha$ be a sequence $a_0, a_1, \dots, a_n$ for some $n=0, 1, 2, \dots$. Then we can generate a new sequence $b_0, b_1, \dots, b_n, b_{n+1}$ that is in Pascal's relations with the original sequence according to the following rule:

Eq. (1)        $\begin{cases} b_0=a_0\\ b_k=a_{k-1}+a_k \quad (1\leq k \leq n)\\ b_{k+1}=a_k \end{cases}$

as shown in Image 2.

Image 2

For instance, if we have a sequence $1, 2, 1$, we can produce a new sequence by following the rule above and get the sequence $1, 3, 3, 1$.

Now, we can construct Pascal's triangle starting from a sequence that consists of one term, 1. We can use Pascal's relations to generate further sequences and place these new sequence below the original sequence.

Before we proceed, we will define the terms rows and places that are used in Pascal's Triangle. The rows proceed as row 0, row 1, row 2, ..., as we start from the top. Places are given to each entry starting from the first number after 1, from the left to the right. 6, for example, would be identified as row 4, place 3.

We will use the notation:

${T_m}^n$

for the entry that is on the $n$th row and $m$th place.

Patterns within Pascal's Triangle

Fibonacci Sequence

Image 4

The Fibonacci sequence is the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... where the first two numbers are 1s and every later number is the sum of the two previous numbers. The Fibonacci numbers can also be found in Pascal's triangle by adding the entries of diagonals as shown in image 4. You can try this at animation demonstrating patterns.

An easier way to show the Fibonacci numbers is to list the numbers on the diagonals on a triangular arrangement. Then, we get Image 5, and adding all the numbers in the same row gives the Fibonacci Sequence.

Image 5

Sierpinski Triangle

If we are to color the odd and even numbers in Pascal's triangle with two distinct colors, we would observe an interesting recursive pattern seen in the Sierpinski triangle.

We can construct a Sierpinski triangle according to the following rule :

(1) Draw an equilateral triangle, as shown in the first step of Image 6.

(2) Then, connect the midpoints of each side of the triangle and remove the triangle in the center, as shown in step 2 of Image 6.

(3) For the remaining three black triangles, repeat step 2.

(4) Repeat step 2 for any remaining triangles.

In fact, if we repeat this process until the number of rows in the triangle approaches infinity, we get Sierpinski's triangle. You could try this out in the animation and see what happens.

Hockey Stick Pattern

[Click to see more.]

Image 2

When we look at Pascal's triangle, we can find figures that look like hockey sticks as we start from a [...]

[Click here to hide.]

 

Image 2

When we look at Pascal's triangle, we can find figures that look like hockey sticks as we start from any 1 in the triangle. The handle of the hockey stick, or the numbers shown inside colored loops in Image 2, should start from any 1 in the border. The head of the hockey stick, or the colored cell in Image 2, should not be aligned in the same direction as the handle, and all numbers in the hockey stick should be on different rows of the Pascal's triangle.

An interesting fact about the hockey stick figures is that the sum of all the numbers in the handle is equal to the number that is at the head of the hockey stick. For instance, let's look at the blue hockey stick. When we add the numbers positioned at a straight line, we get :

$1+3+6=10$,

which is the number that is at the head of the same hockey stick. We can prove this property using mathematical induction.

[Click to here to show proof.]

Let ${\color{Gray}{X_m}^n}$ denote for the ${\color{Gray}n}$th row and the ${\color{Gray}m}$th entry

[Click here to hide proof.]

Let ${X_m}^n$denote for the entry in the $n$th row and $m$th column. We want to prove that

${X_m}^n={X_0}^{n-1}+{X_1}^{n-1}+\dots+{X_m}^{n-1}$

First, we show the base case that the assertion works for when $m=0$. In other words, we want to show that:

${X_0}^n={X_0}^{n-1}$.

Because ${X_0}^n={X_0}^{n-1}=1$, we have shown the base case.

Next, we will show that if the assertion holds true for $m=k$, then it also holds true for $m=k+1$. Because every number in the triangle is a sum of the numbers to its left and top, we know that

${X_{k+1}}^n={X_k}^n+{X_{k+1}}^{n-1}$

$={X_0}^{n-1}+{X_1}^{n-1}+\dots{X_k}^{n-1} +{X_{k+1}}^{n-1}$.

The assertion is true for $m=k+1$ when it is true for $m=k$, and we have proved the first property. The second property can also be proved in a similar way.

Horizontal Sum

[Click to see more.]

We can add the numbers in each row horizontally. We can see that the sum of entries in each row is twice the sum o [...]

[Click here to hide.]

 

We can add the numbers in each row horizontally. We can see that the sum of entries in each row is twice the sum of entries in the previous row. In fact, the sum of all entries on the $n$th row is $2^n$.

[Click here to show proof.]

Let the sequence ${\color{Gray}a_0, a_1, a_2, \dots, a_n}$ be a sequence of any row in the Pascal's triangle, and let

[Click here to hide]

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

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

$b_0+b_1+b_2+\dots+b_n+b_{n+1}$

$=a_0+(a_0+a_1)+(a_1+a_2)+\dots+(a_{n-1}+a_n)+a_n$

$=2a_0+2a_1+2a_2+\dots+2a_{n-1}+2a_n$

$=2(a_0+a_1+a_2+\dots+a_n)$

Thus, the sum of entries of any row is twice the sum of the entries in the previous row. In fact, the sum of entries for each row is :

$\rm {row} \quad 0=1=2^0$

$\rm{row} \quad 1=1*2=2=2^1$

$\rm{row} \quad 2=2*2=4=2^2$

$\rm{row} \quad 3=4*2=8=2^3$

$\dots$

$\rm{row} \quad n=2^n$

Other Patterns and Properties

• The triangle is symmetrical. The numbers on the left side of the triangle have identical numbers on the right side. In other words, the $k$th number from the left at any row $n$ is the same as the $k$th number from the right at the same row; thus, ${T_k}^n=T_{n-k}^n$. For instance, look at the 5th row. 10, which is the 3rd from the left, is also 3rd from the right in the 5th row.
• The triangle is bordered by 1's on the right and left edges.
• The next line of numbers in diagonal order after the edge numbers are natural numbers $1, 2, 3, 4, 5, \dots$
• The next set of numbers inwards after the natural numbers are triangular numbersA number $n$ is a triangular number if $n$ number of dots can be arranged into an equilateral triangle evenly filled with the dots. As shown in theimage below, the sequence of triangular numbers continue as $1, 3, 6, 10, 15, 21, \dots$. Triangular numbers are given by the formula : $\frac{n(n+1)}{2}$ that continues as $1, 3, 6, 10, 15, 21,\dots$

• After the triangular numbers we have tetrahedral numbersTo understand what we mean by tetrahedral numbers, look at the stack of marbles in the image. Let each layer correspond to h=1,2,3...from the top to the bottom. For h=1, we need 1 marble. For h=2, we need 4 marbles (one at the top and three below it). For h=3, we need 10 marbles et cetra. The numbers $1, 4, 10, 20, 35, \dots$are in a sequence referred to as tetrahedral numbers, owing to the tetrahedron arrangement like that shown in the image of the marbles. that continue as $1, 4, 10, 20, 35, \dots$.
• The next d-diagonal contains the next higher dimensional "d-simplex" numbers.

• The first number after 1 in each row divides all the other numbers in that row if and only if it is prime.

Animation Demonstrating Patterns

The Flash animation below allows you to explore some of the patterns present in Pascal's Triangle:

Applications of Pascal's Triangle

Heads and Tails

Image

We can use Pascal's triangle to find the probability of having a certain outcome of tossing coins.

For example, if we toss a coin twice, we could have the any of the following results: Head-Head once, Tail-Head twice and Tail-Tail once. (Here, we do not differentiate the coins. Thus, Tail-Head and Head-Tail are considered the same combination.) The number of each possible outcome is 1, 2, 1, which is also the same as the second row of Pascal's triangle.

In general, if we toss a coin $x$ times, the number of each possible outcome is the same as the horizontal entries in the $x$th row of the Pascal's triangle.

Image

What is the probability of getting exactly 2 heads with 3 coin tosses?

To answer this, we could use Pascal's triangle. Adding the entries of the third row of Pascal's triangle, we get $1+3+3+1=8$ possible outcomes. Therefore we have 8 possible outcomes. 3 of the possible 8 outcomes give exactly 2 heads, therefore the probility of getting exactly 2 heads from 3 coin tosses is $3/8=37.5%$.

Binomial Coefficients in Pascal's Triangle

Pascal's triangle can be used to determine binomial coefficients A binomial coefficient ${n \choose k}$ is the coefficient of $x^k$ in the expansion of $(1+x)^n$. The exact value can be found by ${n \choose k}=\frac{n!}{k!(n-k)!}$in binomial expansions. For example, when we consider the expansion of $(x+y)^n$ for $n=0, 1, 2, 3, \dots,$ we get:

$(x+y)^0=1$

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

$(x+y)^2=x^2+2xy+y^2$

$(x+y)^3=x^3+3x^2y+3xy^2+y^3$

$\dots$.

Notice that the coefficients in the expansion are the entries in the $n$th row in Pascal's triangle. In general, we can use binomial coefficients to describe the coefficient of the expansion as :

$(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$.

This is called the binomial theorem. Indeed, the binomial coefficient ${n \choose k}$ is the entry of the $n$ row and $k$th place in Pascal's triangle, and we can find the value by:

${n \choose k}=\frac{n!}{k!{(n-k)}!}$

[Click here to show proof.]

We know that

${\color{Gray}(x+y)^n={n \choose 0}x^n+{n \choose 1}x^{n-1}y+ \dots + {n \choose k}x^{n-k}y^k+ \dots + {n \choose {n-1}}xy^{n-1}+{n \choose n}y^n}$.

Now, let's consider the expansion of ${\color{Gray}(x+y)^{n+1}}$.

This can be written as :

[Click here to hide proof.]

We know that

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

Now, let's consider the expansion of $(x+y)^{n+1}$.

$(x+y)^{n+1}$ can be written as :

Eq. (2)        $(x+y)^{n+1}=(x+y)^n(x+y)$

We can find the binomial expansion of $(x+y)^{n+1}$ by expanding the right side and left side of Eq. (2), and the expansion of either side of the equation must give the same result.

Expanding the left side of Eq. (2), we get:

$(x+y)^{n+1}={n+1 \choose 0}x^{n+1}+{n+1 \choose 1}x^ny+ \dots +{n+1 \choose k}x^{n+1-k}y^k+\dots+{n+1 \choose n}xy^n+{n+1 \choose n+1}y^{n+1}$

Expanding the right side of Eq. (2), we get:

$(x+y)^n(x+y)=\Bigg( {n \choose 0}x^n+{n \choose 1}x^{n-1}y+ \dots + {n \choose k}x^{n-k}y^k+ \dots + {n \choose {n-1}}xy^{n-1}+{n \choose n}y^n\Bigg) (x+y)\,$

$={n \choose 0}x^{n+1}+{n \choose 0}x^ny+{n \choose 1}x^ny+{n \choose 1}x^{n-1}y^2+\dots+{n \choose k}x^{n+1-k}y^k+{n \choose k}x^{n-k}y^{k+1}+\dots +{n \choose n-1}x^2y^{n-1}+{n \choose n-1}xy^n+ {n \choose n}xy^n +{n \choose n}y^{n+1}$

The left side expansion and right side expansion must be the same. Thus, the coefficients for terms with same powers of $x$ and $y$ must also be the same. Thus,

$\begin{cases} \displaystyle {n+1 \choose 0}={n \choose 0}\\ \displaystyle {n+1 \choose k}={n \choose k-1} +{n \choose k} \quad (1 \leq k \leq n )\\ \displaystyle {n+1 \choose n+1}={n \choose n} \end{cases}$

This is the same form as Pascal's relations in Eq. (1). We can see that the sequence of coefficients of the expansion of $(x+y)^{n+1}$ is in Pascal's relations with the sequence of coefficients of the expansion of $(x+y)^n$. The very first sequence for $n=0$ is :

${0 \choose 0}=1$,

which is the sequence in the $0$th row of Pascal's triangle. Thus, all other sequences of coefficients of binomial expansion also coincide with the entries of Pascal's triangle.

Combinations in Pascal's Triangle

Let $S$ be a set of $n$ elements. Then, we can find a subset of $S$ that contains $k$ different elements. This subset is called a k-combination. The number of k-combination of an $n$ element set is equal to the number of $n$ things taken $k$ at a time. This number is denoted by $C_{(n,k)}$, ${C_k}^n$, or ${}_nC_k$, and is equal to the binomial coefficient:

${n \choose k}=\frac{n!}{k!{(n-k)}!}$

Thus, we can find the number of k-combinations from Pascal's triangle.

Teaching Materials

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

References

Uspenskii, V. A. (1974) Pascal's Triangle. Chicago : The University of Chicago Press.

Posamentier, Alfred S & Lehmann Ingmar. (2007) The Fabulous Fibonacci Numbers. New York : Prometheus Books.

Wikipedia (Combination). (n.d.). Combination. Retrieved from http://en.wikipedia.org/wiki/Combination.

Wikipedia (Pascal's Triangle). (n.d.). Pascal's Triangle. Retrieved from http://en.wikipedia.org/wiki/Pascal's_triangle.

Future Directions for this Page

• New Definition of Pascal's Triangle in the more mathematical explanation

-Current definition is based on Pascal's relations given by the sequence $\alpha, \beta$. Maybe change the definition using Combinations. Pascal's triangle is an arrangement of binomial coefficients. For instance, the 0th row is ${0 \choose 0}$, the 1st row is ${1 \choose 0}, {1 \choose 1}$ and so forth. -With the new definition, come up with new proofs for the properties

• New Structure/ Organization

-In the think alouds, people were more interested in the application of Pascal's triangle (ex, the coin toss) more than to the properties and patterns within Pascal's triangle. Maybe think about moving the application section to the top.

• number Images, anchor them

• rewrite the coin-toss section to make everything clear

• Add an why interesting section, if possible

To see a detailed suggestion for this page, click below

[Click to see more.]

• Make the "combinations" interpretation of Pascal's Triangle more central

We may want to *define* Pascal's Triangle this way, and describe the Pasca [...]

[Click here to hide.]

 

• Make the "combinations" interpretation of Pascal's Triangle more central

We may want to *define* Pascal's Triangle this way, and describe the Pascal's Relations rule as a *property*, if I'm right that this is the standard view today. In any case, we almost certainly want to put this definition near the beginning of the page (see threads about large-scale restructuring of patterns and large-scale restructuring of applications, below).(Abram, 7/22)

• Large-scale restructuring of patterns

Right now, it seems like everything that has a proof is in the more mathematical section, while everything that doesn't have a proof is not. This organization probably doesn't make sense, because there's no intrinsic reason why the Fibonacci sequence pattern is less mathematical than the hockey stick pattern and if we do eventually include proofs for these properties, the whole page will be the more mathematical explanation. This is silly, because all the patterns, and even some of the applications, are perfectly understandable for any reader. It's just the proofs that are harder. Here are a couple ideas we came up with:

Don't have *any* section called the More Mathematical Explanation (except maybe the Binomial Coefficents). Just hide all the proofs and make sure to tell the reader that there's no harm in skipping over these proofs. One good reason for doing this is that many of these patterns can be proven without any equations by using the "combinations" interpretation of Pascal's Triangle, so those proofs can be made available to every reader. Have the basic description consist of a description of all the patterns, and perhaps eventually a non-equation based proof, while all the equation-based proofs are in the more mathematical explanation. (Abram, 7/22)

• Large-scale restructuring of applications

It seems like we definitely want the "combinations" interpretation of Pascal's Triangle put near the beginning of the page because it eventually makes way for non-equation-based proofs of just about everything. It's also possible that the heads/tails application should be put before the patterns. It seems that more readers are interested in applications than are interested in patterns (because they often see the patterns as kind of cheap carnival tricks). Finally, the combinations interpretation should definitely definitely come before the heads and tails section. (Abram, 7/22)

Think of ways of getting interesting stuff into the basic description or a why it's interesting section Possibilities include: moving some of the patterns to the why it's interesting section (the math isn't very complicated); giving an overview in the basic description of the types of things the triangle is useful for or why Pascal invented it; anything else you can think of. (Abram, 7/15)

Hmm, actually, this issue has probably been replaced by the issues above. (Abram, 7/22)

• Rewrite the coin-tossing section

I know you were trying to work with what was already there, but most of those sentences are kind of confusing. You can decide whether it's easier to fix it sentence-by-sentence or to just rewrite the whole section. (Abram, 7/15)

---

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.