Pascal's triangle
From Math Images
Pascal's Triangle 

Pascal's Triangle
 Depicted on the right are the first 11 rows of Pascal's triangle, one of the bestknown 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 (16231662), 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 KhayyamPascal 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]}
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. 
The Combinatorial Approach to Pascal's Triangle

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.
or or , 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
 .
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
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 and , 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
 This is called Pascal's identity.
Suppose we want to choose r people from an nmember committee to form a subcommittee. There can be 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 ways to do this.
Case 2: Suppose now we want to form a subcommittee that Mr. X does not belong to. Then there are ways to select an rmember subcommittee from the remaining (n–1) members.
The total number of possible rmember subcommittees should equal the sum of the numbers in the two cases above.
Hence,
The algebraic proof is as follows:
Note that
 and
This is crucial to the understanding of the proof below.
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,
Notice that the coefficients of (x+y)^{n} correspond to numbers in row n of Pascal's triangle. In other words,
 .
If we use summation notation, we have
Eq. 2 is known as the binomial theorem and 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 C_{k}x^{nk}y^{k}.
The base case is n = 0: , which indeed equals . So Eq. 2 is true when n = 0.
Now assume our assertion in
 holds true for a given n. Then by the inductive hypothesis, we know that
Then we need to prove it for case n + 1. Because
We have
According to Pascal's identity:
Also,
Therefore,
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: HeadHead, TailHead, HeadTail, and TailTail. If we ignore the order of the results, then TailHead and HeadTail 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  1,1  
2  HH,HT,TH,TT  2H, 1H1T, 2T  1,2,1  
3  HHH,HHT,HTH,THH,HTT,THT,TTH,TTT  3H, 2H1T, 1H2T, 3T  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  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 2^{3} 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
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:
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:

Symmetry and Borders
Sum of Rows
Look at the horizontal sums of Pascal's triangle. For row n, the horizontal sum equals 2^{n}.
We can prove this property through the combinatorial interpretation of the triangle. One of the properties of combinations is that Why is this true? Suppose we are picking people from the nmember committee again. The left side of the equation counts the subcommittees by how many people are in the subcommittee: counts the number of 0member subcommittees; counts the number of 1member 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 2^{n}, which is the right side of the equation. Therefore, the sum of the entries of row n in Pascal's triangle should equal 2^{n}.
Let be the sequence of any row n in Pascal's triangle, and let be the sequence of the row right below the a_{i} sequence. Then the sum of the entries of the sequence can be written as:
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 2^{n}.

Hockey Stick Pattern
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 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
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, , 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 .
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
 RHS
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
By the inductive hypothesis, we know that
Substituting this expression of into the equation above for ,
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
Pascal's triangle contains a magic hexagon pattern.
If we look at the nearest six elements around , 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 HoggattHansell 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
The left hand side of Eq. 4 is, Using the formula for combinations, the left hand side becomes Changing the positions of the denominators, this equals Using the notation of combinations, this may be rewritten as 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
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 onedigit 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. 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 Therefore, the units position of 11^{n} is the value of ; the tens position is the value of ; the hundreds position is the value of ... If the value of 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 .
For example, consider the exponents of 101:
101^{0} =  01 
101^{1} =  1 01 
101^{2} =  1 02 01 
101^{3} =  1 03 03 01 
101^{4} =  1 04 06 04 01 
101^{5} =  1 05 10 10 05 01 
101^{6} =  1 06 15 20 15 06 01 
101^{7} =  1 07 21 35 35 21 07 01 
101^{8} =  01 08 28 56 70 56 28 08 01 
101^{9} =  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 101^{9}. Because 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 . After this process, there are no more threedigit 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 downleft diagonals (the diagonals that go between lower left and upper right). However, the downright 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 , so the leftmost downleft 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 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, 3^{2}  1^{2} = (3  1)^{3}, 6^{2}  3^{2} = (6  3)^{3}, 10^{2}  6^{2} = (10  6)^{3}. This property was discovered by V. F. Ivanoff of San Francisco, Califormia, in 1933.^{[3]}
 Why?
 Consider the positive difference between entry 3's from rows two apart. The difference is always a square. For example, 10  1 = 3^{2}, 20  4 = 4^{2}, 35  10 = 5^{2}.
 This is true because
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
Since (p – k)! can be written as [(p – 1) – (k – 1)]!, we have
Therefore,
Now let p be a prime, and 0 ≤ k ≤ p. Then entry 1 in row p is p, and the internal entries are .
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 . Because p is not a factor of k, it has to be a factor of . So, p divides . 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 p^{n} 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 is divisible by p, where 0 < k < p^{n}.
Changing the p in Eq. 5 to p^{n}, we have
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, p^{n} has (n + 1) factors, namely 1, p, p^{2}, p^{3}, ..., p^{n}.
Since k < p^{n}, we know that k and p^{n} can have at most n common factors (including 1). Therefore, there is at least one factor of p^{n} besides 1 that divides . This factor is definitely an exponent of p, as shown above in the list of factors of p^{n}. Hence, p divides all , or in other words, all the internal entries of row p^{n}.
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 = 11_{two}, and all entries in row 3 (1 3 3 1) are odd. 15 = 1111_{two}. 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, 012, 72135, and 100120023003. 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, .
 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.0} ^{1.1} ^{1.2} Wikipedia (Pascal's Triangle). (n.d.). Pascal's Triangle. Retrieved from http://en.wikipedia.org/wiki/Pascal%27s_triangle
 ↑ Pickover, Clifford A.(2009). The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics Sterling. ISBN 9781402757969
 ↑ ^{3.0} ^{3.1} ^{3.2} ^{3.3} Koshy, Thomas(2011). Triangular Arrays With Applications. Oxford University Press. ISBN 9780199742943
 ↑ 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
 ↑ 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
 ↑ 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 9780199742943
[2]Edwards, A.W.F.(1987). Pascal's Arithmetical Triangle. Charles Griffin & Company Limited, Oxford University Press. ISBN 0852642830
[3]Maurer, Stephen B., Ralston, Anthony(2004). Discrete Algorithmic Mathematics. A K Peters, Ltd. ISBN 1568811667
[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/pascalstriangle.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.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.