Pascal & Pizza
Patterns with Mathematical Techniques of Counting
Washington University Middle School Mathematics Teachers’ Circle
Richard Lodholz, March 4, 2008
History records that Egyptians, Babylonians, and Romans played with dice. According to Amir D. Aczel, in his book, Chance, the Etruscans played with dodecahedron dice around 1000 B.C. However, the Greeks have no history recorded with the concept of chance. They only used dice for dealing with addition of numbers. The mathematical theories for probability came in the seventeenth century by correspondence between Blaise Pascal and Pierre de Fermat, stimulated by the famous question posed to Pascal by Chevalier de Mere (see handout Ideas with Probability, Feb. 6).
Probability is such a worthy mathematics topic, even for elementary school youngsters, because determining probabilities of events simply requires counting. The count of the number of success divided by the total number of possibilities gives the probability measure and connects probability to other mathematical domains as well as to other subjects. Later mathematics curriculum can extend the manual counting into mathematical counting techniques. Both this arithmetic and symbolic manipulation is appropriate for middle school mathematics.
Question 1. What is a mathematical technique for counting all possible arrangements for a number of objects?
For example: In how many different ways is it possible to arrange all the letters in the word, BLAKE? We can think of 5 different places to put the B, and for each of those we have 4 different places to put the L, and for each of those 3 different places to arrange the A, and so on. One example is KELBA. This gives the familiar “permutation” of 5 different items as =
Question 2. What is a mathematical technique for finding the number of different arrangements of 5 objects if 3 look alike?
For example: Suppose Blake’s parents wanted to name him Billy with a French twist (Bille), but the hospital computer made the i's and L’s look alike. In how many different ways is it possible to arrange all the letters in the name BIIIE?
Obviously, the number from needs to be decreased. Using that marvelous algebraic concept, let’s suppose the answer to the question is x. One possible arrangement could be IIBIE. Since the three I’s look alike we could think of them as I1, I2, I3 and these 3 could be arranged in ways. The same thing would be true for any of the x arrangements. So, the total arrangements of the 5 letters we already know is 5!. So, 3!(x) = 5! Then the technique for this situation is determined mathematically by solving for x, or =
If we generalize this example using the same reasoning to determine a rule for finding all possible arrangements of n objects if r of them look alike, we get:
Question 3. What is a mathematical technique for counting the number of selections (choices) of 2 items taken from a possible 5 things?
For example: How many different choices of two letters are possible from the 5 letters in the name BLAKE. Two selections would be (L & E), & (B & K). How many in total?
We could build on the previous situation and think that the 3 letters not taken could be arranged in ways. In addition, it would not matter if we first took L and then the E, or took E and then L. The order of the letters would not matter in a selection. This requires dividing also by . So the rule for determining the count of selections of 2 letters from 5 letters in BLAKE would be given by:
= =
In general the number of different ways to select r things from a total of n things is given by . Mathematically, it is called the number of combinations of n things taken r at a time, and usually written .
One of the connections of this counting technique is with binomial expansion. Al Otto has already pointed out that the coefficients in the binomial expansion of the term (a + b), if organized, forms the Pascal Triangle.
(a + b)0 1
(a + b)1 1 1
(a + b)2 1 2 1
But why does this work? Consider the binomial cubed (assuming we do not have the coefficients memorized) we could obtain them by working Pascal’s Triangle, if we knew the row above. But, let’s see if we can find out what’s going on.
The term (a + b)3 means (a + b) (a + b) (a + b). The possible terms are a3, a2b, ab2, b3
To determine a rule for finding how many of each term, think about the number of b’s in each term. We could have 0, 1, 2, or 3. The number of ways to select 0 b’s from the 3 binomials is determined by and for 1 b, , for 2, and 3,
For the fourth power we have 4 binomials from which to choose 0, 1, 2, 3, or 4 b’s.
For the fifth power, 5 binomials from which to select 0, 1, 2, 3, 4, or 5 b’s.
And so on.
With this concept, Pascal’s Triangle can be expanded in mathematical symbols with the notation of combinations. Look at Pascal’s Triangle in a more mathematical form with the combination notation for the coefficients of the terms.
(a + b)0
(a + b)1
(a + b)2
(a + b)3
(a + b)4
(a + b)5
. . .
. . .
. . .
See if the rule for Pascal’s Triangle holds with this notation. For instance check to see if + = So, + = +
= 4 + 6 = 10
And = = 10. It seems to work.
How could we prove it for the general case? Consider the nth row and two consecutive terms that would determine the rth term in the next row, or (n + 1) row.
Mathematically we need to show that + =
Solution: + = + find the common denominator and do the rational expression addition.
= +
= = = =
Manipulating the numbers arithmetically with the rule builds the Pascal Triangle row by row. Manipulating the symbols with the combination notation verifies mathematically why this arithmetic works, and also permits us to find the coefficient for any term in any expansion.
Rumor has it that Pascal really liked pizza. Some doubt this, since he was French and pizza was later created in America, but let’s follow the rumor for the time being.
Suppose we have a nice crust with sauce and cheese and have the option of adding pepperoni, mushrooms, onion, garlic, tomato, and olives.
Question 4: How many different pizzas are possible?
Solution: We can try to write an organized listing but this is quickly determined to be a huge task. One way is to consider each extra item separately. For instance, if we consider pepperoni we could have it or not have it (take it or leave it). Two choices. For each of those 2 choices of pepperoni we could consider mushrooms (take it or leave it). Again 2 choices, but 2 choices for mushrooms for each of the two pepperoni options. Continue this line of reasoning, and we have 2 choices for each of the 6 items, or possibilities.
= = 64
Our solution to the pizza problem seems to be really a selection model. We could have reasoned that we could take none of the toppings, or 1, or 2, and so forth. Let’s make a connection to Pascal’s Triangle with the selection (combination) model.
Look at the sixth row (really the seventh) of the triangle. The coefficients of the expansion would be: and their sum would be given by: 1 + 6 + 15 + 20 + 15 + 6 + 1, which is 64, the same as . Conjecture seems to be that this works for any row. Al Otto has already stated it would. But can we prove it?
Verify that the sum of all the coefficients on any row (say n) of Pascal’s Triangle is equal to 2n. That is, show that: + + + + + + = 2n
or using summation notation =
Think of 2 written as a binomial (1 + 1), so a (1 + 1)n expansion has every possible term equal to 1 with the respective coefficients the same as the left side of the equation above, and we have justified the concept mathematically.
Perhaps Pascal did like pizza.
Consider the arrangement of Pascal’s Triangle as shown below. For the following discussion we will think of the row number as the exponent in the binomial expansion. For example the first row is 1 1, second (n=2) is 1 2 1
Triangular numbers in this column.
1
1 1
21 Fibonacci numbers come from the sum on these diagonals
1 2 1
34
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
In general the triangular numbers appear in the nth row for r = 2, so the term is = = = = , which is the formula
for generating triangular numbers.
Ann Podleski has already shown us that the Fibonacci numbers are found by summing the oblique diagonals as shown above. The pairs of diagonals go from nth row to half of the nth row and as she pointed out use the greatest integer function for odd numbered rows.
The 9th, and 10th Fibonacci numbers would be given by starting with the diagonal on the 8th and 9th rows of the triangle. As illustrated
= 1 + 7 + 15 + 10 + 1 = 34
= 1 + 8 + 21 + 20 + 5 = 55
Using mathematical notation these sums can be expressed as:
= the (n+1)st Fibonacci number, if n is odd then the sum goes to the greatest integer of n/2, , so the result is for n a positive integer.
There are many more interesting patterns with the numbers in Pascal’s Triangle.
The pentagonal numbers are found with a little searching.
1 The sum of these numbers is 12. Move the pattern down a row.
1 1
The next pattern would produce 3 + 3 + 6 + 10 = 22
1 2 1
Move it down another row. To get 4 + 6 + 10 + 15 = 35
1 3 3 1
1 4 6 4 1
This sum is 51. What type of numbers are these?
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
Generalizing this pattern gives us the following combination notation rule.
=
==
Which is a formula that produces the pentagonal numbers. Test it.
The hexagonal numbers you might recall are connected to the triangular numbers, simply every other one. Find these in the Pascal’s Triangle.
1 With an illustration of triangular numbers, hexagons are obvious.
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
These generalize as: , since the hexagonal numbers only occur in even rows.
And, simplifying, we get
For n = 1 à 1, 2 à 6, 3 à 15, 4 à 28, 5 à 45, … which are the hexagonal numbers.
Finding the square numbers also takes some investigation to locate and simplify the patterns. If you recall from the discussion with figurative numbers the sum of any two consecutive triangular numbers was a square, you can find the square numbers.
The r term is always 2 less than the row number or n term. So we could generalize it as
This simplifies as: =
=
=
=
=
= = =
The square numbers also pop up in another way by adding four numbers in 2 consecutive rows.
To find square numbers use the pattern below. Place this zigzag pattern along the hypotenuse of the ‘Right’ Pascal Triangle.
Add the numbers in the enclosed box to find a square number.
Illustrate this with combination notation. For instance with the middle box the notation would be shown as:
=
= 10 + 5 + 15 + 6
= 36
In general terms we have
=
=
= A square number
1