I was eating dessert after dinner with my wife and three boys crowded around the kitchen table in the late 1970s, when it hit me–the sum of the n odd integers equals n squared. Excited, I rushed down stairs to my office in the basement to confirm my insight. Not only did the relationship prove true, but I also developed some corollaries
.
[To understand what this is all about, consider the following:
size
of the old matrix plus 1–by definition an odd number.
Matrix 2 × 2 3 × 3 4 × 4 5 × 5
Count 4 9 16 25
Difference 5 7 9
O O O O O O O O O O O O O O
O O O O O O O O O O O O O O
O O O O O O O O O O O O
O O O O O O O O O
O O O O O
The differences between:
0 × 0 and 1 × 1 is 1;
1 × 1 and 2 × 2 is 3;
2 × 2 and 3 × 3 is 5;
3 × 3 and 4 × 4 is 7;
4 × 4 and 5 × 5 is 9; etc.]
I could hardly wait until I got to work the next day and explained my amazing discovery. One of my coworkers with more formal mathematical training replied, Yah, they used this relationship to solve square roots hundreds of years ago before the development of machine calculators.
Crushed! Foiled again!
But I was determined to claim my rightful place in the Sun, even if I was a member of the over-the-hill gang
as I approached my 40th birthday. It is historical fact that most great mathematical discoveries have been made by mere lads still wet behind the ears (whatever that means). Albert Einstein was 26 when he published his Special Theory of Relativity. Isaac Newton was a 24-year-old college kid when he developed the laws of physics Which govern the planets and invented calculus to compute their movements.
And the story is told about 9 year old Carl Friedrich Gauss, who was something of a smart-ass
in school. One day the teacher tried reduce the disruptions by telling Karl to add up all the numbers between 1 and 100. Moments later Karl was again instigating commotion. When the teacher called him to account, Karl presented his slate with the number 5050 written in chalk. Challenged to explain, Karl said he realized that the numbers between 1 and 100 are 50 pairs of numbers which add to 101 (1 + 100, 2 + 99 .... 49 + 52, 50 + 51). So the answer is 50 × 101 or 5050. (The general formula is: The sum of whole numbers from 1 upto n is n × (n + 1) / 2.)
[You may have noticed that this is somewhat related to my centuries-too-late discovery of the sums of odd integers and squares:
The sum of integers between 1 and n | = n × (n + 1) / 2 |
The sum of squares of integers, 1 to n | = n × (n + 1) × (2n + 1) / 6 |
The sum of cubes of numbers, 1 to n | = n × (n + 1) × n × (n + 1) / 4 |
There are more, but the relationship is evident. Everything is related to everything. Mathematics is so incestuous.]
Searching for mathematical immortality, I decided to take on a problem I had promised myself to solve back in high-school–twenty years earlier. Father Deno, an obese diabetic always sucking a Lifesaver with a matching roly-poly personality, was everyone's favorite algebra teacher. In the process of teaching us about the Binomial Theorem, he explained its connections to Pascal's Triangle and showed us a short-cut
to performing Binomial Expansion. As a devotee of the Carl Friedrich Gauss code of conduct, I shouted out, What about Trinomial Expansion?
The reply was, Sorry kiddo, there isn't any connection or short-cut.
Right then and there I determined to find the trinomial short-cut. Although 20 years later I rededicated myself to Trinomial Expansion at the time of my centuries-too-late discovery, it would be another decade before I would find the time to unlock the secret
of Trinomial Expansion.
Binomial Expansion is an algebraic operation in which a binomial expression (two variables), such as (A + B)2, is simplified
into its constituent terms: A2 + 2AB + B2. (A
and B
are two variables and could be X
and Y
or some other symbols.) [Remember that any number equals itself raised to the first power: A1 = A. So the convention is not to show the exponent when it is 1. Further, any number raised to zero power equals 1: A0 = 1. And finally, when the coefficient is 1, it is not shown: 1A = A.] Here are some Binomial Expansions (for n
from 0 upto 4, where n
is the power of the expansion):
Power | Full expansion | Normally written
0 | 1A0B0 | 1
| 1 | 1A1B0 + 1A0B1 | A + B
| 2 | 1A2B0 + 2A1B1 + 1A0B2 | A2 + 2AB + B2
| 3 | 1A3B0 + 3A2B1 + 3A1B2 + 1A0B3 | A3 + 3A2B + 3AB2 + B3
| 4 | 1A4B0 + 4A3B1 + 6A2B2 + 4A1B3 + 1A0B4 | A4 + 4A3B + 6A2B2 + 4AB3 + B4
| |
The expansions on the left show all coefficients and exponents explicitly; the expansions on the right omit implicit coefficients and exponents. [Note that (A + B)n+1 = (A + B)n × (A + B)1, etc. When multiplying like terms with exponents, the exponents are added.]
There are several interesting properties of these expansions. But before detailing them, let us turn to another mathematical genius.
Blaise Pascal was a mathematician (among other occupations), who put his knowledge to practical use–making money
with gambling. He did a lot of work on probability theory to improve his odds of winning. One of his legacies is a
triangular table known as Pascal's Triangle (hereafter The Triangle
). These are the top nine lines of The
Triangle:
There are a number of interesting
things that can be seen about the full-expansion terms and The Triangle. I am sure you have already noticed the most obvious: The numbers of The Triangle are the same as the coefficients of the Binomial Expansions. (To have the lines of The Triangle match up exactly with the Binomial Expansions, the top line of The Triangle must be labeled the zero
line to correspond with the 0th power expansion.) The Binomial Expansions without the variables and exponents are referred to as detached coefficients
. This is why these numbers are called the binomial coefficients
, the binomial probability distribution
numbers, and the combinatorial numbers
. For the remainder of this section, we will use them interchangeably.
In discussing the properties of Binomial Expansion and The Triangle in the following paragraphs, I will make frequent reference to n
, which in mathematics is the last number in a sequence. I will use it to refer to the power of expansion or line of The Triangle. I will not redefine it each time unless it means something else.
0.
nthings taken
mat a time, where
mis the exponent of either A or B. The function is: C(n,m) = n! / (m! × (n – m)!). [The symbol
!indicates factorial.
N!is the product of all the numbers from 1 to N.]
no-brainer–just follow the rules of increasing and decreasing exponents.) This is the short-cut to which I have been referring.
ratios between adjacent pairs of coefficients, discussed above.)
And now back to our exciting story–the hunt for a short-cut to Trinomial Expansion. [Trinomial Expansion is like Binomial Expansion, except that there are three variables. I use A, B, C here, but they could be X, Y, Z or three other symbols.] I knew that binomials have two variables, triangles are two-dimensional figures, and The Triangle is a two-dimensional array of numbers. Since trinomials have three variables, it makes sense that I was looking for a three-dimensional array of numbers. The three-dimensional equivalent of a triangle is a pyramid. [More precisely a tetrahedron–a pyramid with four triangular surfaces. This is in contrast to the pyramids of Egypt, which have five surfaces–a square base and four triangular sides.]
So I was looking for a three-dimensional array of numbers, shaped like a pyramid, in which a number is related to the numbers above
. Not having any brilliant insights, I had to take the brute force approach–manually calculate the Trinomial Expansion for several powers and then look for a pattern. Manually calculating the Binomial Expansion is tedious; manually calculating the Trinomial Expansion is messy–very messy. First, multiply two trinomials by multiplying each term in one trinomial by each term in the other trinomial. Then, consolidate terms by adding the coefficients of like terms–terms with the same variables and exponents.
To expand
a trinomial, multiply the previous expansion by the basic trinomial.
First, I computed (A + B + C)2:
Next, I computed (A + B + C)3:
Then, I computed (A + B + C)4:
I stopped at (A + B + C)5:
The secret does not exactly jump off the page or screen, now does it. So I put on my Management Science hat, which I used to wear at General Foods in the good ol' days
. We featured ourselves management consultants, but we were little more than glorified computer programmers. Although we did employ complex algorithms which used matrix algebra to optimize economic problems, much of our time was spent structuring
problems. That's a fancy word for fiddling with the numbers and pushing them around on a piece of paper until they made some sense. Yup, that's why they paid me the big bucks–I was very adept at playing with numbers.
I played with (A + B + C)5 until I got this:
[I have deliberately inverted the arrangement so that The Pyramid
will not be confused with The Triangle.]
To see the structure of this Trinomial Expansion more clearly, let me show all the implicit coefficients, variables, and exponents. (Remember: 1A = A, B1 = B, C0 = 1, etc.)
As with Binomial Expansion, Trinomial Expansion can be stated in detached coefficient form by removing the variables (A, B, C) and the exponents. The detached coefficient matrix has the same relationship to The Pyramid as the two-dimensional detached matrix has to The Triangle–they are the same numbers. I will get into this in great detail below. (See: Detached Coefficients).
The properties of The Pyramid are analogous to The Triangle. As before, I will make frequent reference to n
, which in mathematics is the last number in a sequence. I will use it to refer to the power of expansion or the level of The Pyramid. I will not redefine it each time unless it means something else. I will also draw most of my examples from the expansion of (A + B + C)5.
Each Trinomial Expansion is a slice through The Pyramid. In other words:
The expansion of (A + B + C)0 is the top layer or level of The Pyramid.
The expansion of (A + B + C)1 is the 1st layer or level below the top.
The expansion of (A + B + C)2 is the 2nd layer or level below the top.
The expansion of (A + B + C)3 is the 3rd layer or level below the top.
And so on, as far down as you choose to go. Each level or layer is equivalent to one line of The Triangle.
To appreciate this better, let's examine The Pyramid in what is called detached coefficient
form (no variables or exponents, just coefficients). We will study the first nine slices or levels of The Pyramid:
Level 0
Level 1
Level 2
Level 3
Level 4
Level 5
Level 6
Level 7
Level 8
The numbers on each level are the sum of the three adjacent numbers in the level above; although this might be a little hard to see. To show this relationship more clearly, I have super-imposed or interspersed Level 4 on Level 5. The Level 4 numbers are in a lighter font to distinguish them from the Level 5 numbers.
The Level 4 numbers form a triangle around the Level 5 numbers in the middle. [Not shown above are the zeros which are assumed to border the three edges of both levels. But they are listed below.]
Level 5 | Level 4
30 | = | 12+12 + 6
| 20 | = | 12 + 4 + 4
| 10 | = | 6 + 4 + | 0 5 | = | 4 + 1 + | 0 1 | = | 1 + | 0+ 0 |
Why are the numbers of The Pyramid the sum of three numbers in the level above and not two numbers like The Triangle? Well, The Pyramid relates to Trinomial Expansion, while The Triangle relates to Binomial Expansion.
How we get there is somewhat complicated; but it comes about as the result of the two step expansion process. To get the next level:
If we start with (A + B + C)4, there are 15 terms. If we multiply each one by A, B, and C, we would have 45 terms. We would then sort and match them, so we could add up the coefficients and wind up with the 21 terms of (A + B + C)5. Seems like a lot of work and a fair chance of errors.
Let's get smart and work backwards–an easier path to enlightenment. Pick the second term of the second row of the fifth level. You can see the coefficient is 20 in the above detached form and if you look at the fully expanded fifth level in The Pyramid section, you will see the full term is: 20A3BC
. Now what we do is divide this term by A, B, and C to get the terms in the fourth level which sum to the coefficient in the fifth level. Cool!
The steps:
The math:
Division | Find matching | Add coefficients
20A3BC / A1 = 20A2BC | 12A2BC | 12
| 20A3BC / B1 = 20A3C | 4A3C | 4
| 20A3BC / C1 = 20A3B | 4A3B | 4
| |
You have now mastered one of the deep, dark secrets of Trinomial Expansion. And the rank of Apprentice Pyramid Builder has been bestowed on you.
Eureka! We have found the Holy Grail! The Pyramid allows us to write out any Trinomial Expansion without having to plow through a mountain of tedious algebra. To understand the short-cut more clearly, let's look again at the Trinomial Expansion to the fifth power, explicitly showing all the coefficients, variables, and exponents, as before:
The structure of the exponents is straight forward: A advances from right to left; B advances from top to bottom; C advances from left to right. The coefficients of the three corners are always 1. And the other coefficients can be calculated–although it's a bit involved:
Here's how it works. Pick any two adjacent terms–horizontally or diagonally. Call oneterm-1and the otherterm-2. Look at the changes to the exponents of the three variables from term-1 to term-2–one exponent increases by one, one exponent decreases by one, and one exponent remains unchanged. We can ignore the unchanged exponent.
This leaves us in the same position as The Triangle with the same relationships between the coefficients and exponents of adjacent terms–except that the rules are slightly more complex because the pair of terms can have three different relative positions (–, \, /) depending on which exponent remains unchanged. The coefficient of term-1 multiplied by the decreasing exponent of term-1 equals the coefficient of term-2 multiplied by the increasing exponent of term-2 (symbolically: C1 × DE1 = C2 × IE2; where C is coefficient, DE is decreasing exponent, IE is increasing exponent). [Note that DE1 > DE2 and IE2 > IE1–that is, for a given variable (A, B, C), the exponent with the larger value is always used in this calculation.]
Here are some examples:
Term-1 Term-2 Ignore Decreasing Increasing Equation 5A4B1C0 10A3B2C0 C0 A4 => A3 B1 => B2 5 × 4 = 10 × 2 10A0B3C2 30A1B2C2 C2 B3 => B2 A0 => A1 10 × 3 = 30 × 1 5A1B0C4 10A2B0C3 B0 C4 => C3 A1 => A2 5 × 4 = 10 × 2 20A3B1C1 30A2B1C2 B1 A3 => A2 C1 => C2 20 × 3 = 30 × 2 5A1B4C0 20A1B3C1 A1 B4 => B3 C0 => C1 5 × 4 = 20 × 1 5A0B1C4 10A0B2C3 A0 C4 => C3 B1 => B2 5 × 4 = 10 × 2
We can re-arrange the basic equation to solve for either one of the two coefficients:
C2 = C1 × DE1 / IE2;
C1 = C2 × IE2 / DE1.
So, we can write the variables and exponents (they are just boilerplate) and then go back and fill in the coefficients (using the ones we know to calculate the missing values). The trick being the triangular arrangement, rather than a linear one, so that the data stay organized and coherent–that is, the adjacent terms have the relationship detailed above. I have reached my goal in life–a short-cut to Trinomial Expansion. And now, I can die a happy man!
If you found the previous section a bit confusing (with its increasing and decreasing exponents, etc.), then you may be happy to know that you can get to the same place in an easier way. Any number in The Pyramid is related to the surrounding adjacent numbers by whole number ratios. The easiest way to explain this is to show an example–Level 5
. However, for clarity, I will show the example in three parts, using the following symbols to connect the numbers and the ratios:
<a:b> | horizontally from left to right and vice-versa, |
\c:d\ | diagonally from upper left to lower right and vice-versa, |
/e:f/ | diagonally from upper right to lower left and vice-versa. |
[I hope you are impressed by my high-tech graphics.] Showing the example three ways is probably overkill, since The Pyramid is symmetrical in all three directions. But the regular pattern of the antecedent term (first number) and the consequent term (second number) of the ratios should be obvious. (That is: the ratios change in a systematic order, regardless of direction.)
In fact, if you compare the ratios to the exponents of the Trinomial Expansion you will find they match. The antecedent term of the ratio is the same as the increasing exponent of the consequent expansion term and the consequent term of the ratio is the same as the decreasing exponent of the antecedent expansion term. (Increasing and decreasing exponents are understood to be from antecedent to consequent expansion term. Antecedent and consequent expansion terms are understood to be in the same order as the ratio terms.)
OK, I got carried away with my antecedents
and consequents
in the last paragraph. Suffice it to say that every number is related to all adjacent numbers in a uniform way. That goes for numbers on the same level as well as numbers on adjacent levels of The Pyramid.
What are the numbers of The Pyramid? Do they have any connection to real life? I knew the numbers of The Triangle were the combinations of n thing taken m at a time. It took me some time to figure out that the numbers of The Pyramid are multinomial coefficients. I thought that's what they are; but when I checked one of my text books, I must have looked on the wrong page. After repeatedly banging my head against the proverbial wall, I eventually found the right page.
Multinomial coefficients are the number of ways a set of events can occur. This is multiplied by the probabilities that the events do occur to give the likelihood that the particular set of events does occur. As mentioned above, both the Binomial and Trinomial Distributions are subsets of the generalized Multinomial Distribution, which can have any number of possible outcomes. Binomial processes have two possible outcomes–such as: pass, fail; or heads, tails. Trinomial processes have three possible outcomes–such as grades of A, B, C; win, place, show; or 3 candidates for office. Here is an example of a trinomial process:
In an election, 3 candidates received the following votes:
A got 54%, B got 30%, C got 16%.
If a sample of 9 voters is selected, what is the likelihood that they voted this way:
4 for A, 3 for B, 2 for C?
The sum total (n) is 9 and the exponents (x, y, z) are 4, 3, 2. The coefficient of the distribution (and the number from The Pyramid) is the number of ways this sample can occur:
9! / 4! / 3! / 2! = 1260.
The likelihood the 9 sample voters balloted for the 3 candidates is the chance that:
4 voted for A, 3 voted for B, 2 voted for C;
A's% × A's% × A's% × A's% × B's% × B's% × B's% × C's% × C's%;
(A's%)4 × (B's%)3 × (C's%)2;
(54%)4 × (30%)3 × (16%)2 = .0059%.
The number of sample possibilities is multiplied by the balloting likelihood to give the chance that the sample voters chose the candidates as specified:
1260 × .0059% = 7.4%.
The probability of4 for A, 3 for B, 2 for Cis 7.4%.
In the process of hunting for relationships among the coefficients of The Pyramid, I discovered a short-cut for generating the numbers for any level of The Pyramid using just The Triangle, which is much simpler and avoids the tedious task of generating all the previous levels of The Pyramid and trying to figure which three numbers are above
each of the numbers in the current level. (Particularly helpful for people who get easily cross-eyed.)
This short-cut illustrates the close connection between The Triangle and The Pyramid.
To produce the nth level of The Pyramid, multiply each of the first n lines of The Triangle by the numbers of the nth line of The Triangle. An example will clarify my words:
The Triangle (to nth line) | × nth line = | nth level of The Pyramid |
1 | 1 | 1 |
1 1 | 5 | 5 5 |
1 2 1 | 10 | 10 20 10 |
1 3 3 1 | 10 | 10 30 30 10 |
1 4 6 4 1 | 5 | 5 20 30 20 5 |
1 5 10 10 5 1 | 1 | 1 5 10 10 5 1 |
This may look like Linear Algebra (matrix multiplied by vector), but it's not. [The Pyramid has been inverted from its usual form–or The Triangle could have been stood on its head–they both must have the same shape
for this short-cut to work.] Each of the numbers in each line of The Triangle is multiplied by the corresponding number from the nth line of The Triangle. Symbolically, T(i,j) × T(n,j) = P(n,i,j), where T is Triangle, P is Pyramid, i = 0 to n, j = 0 to i, and n = line or level.
How does this work? Well, the coefficient formulae for The Triangle and The Pyramid are almost the same. The formulae given previously can be restated in terms similar to one another:
Originally | Restated | Alternative
Triangle | n! / (m! × (n – m)!) | n! / x! / y! | (x + y)! / (x! × y!)
| Pyramid | (x + y + z)! / ( x! × y! × z!) | n! / x! / y! / z! | (x + y + z)! / (x! × y! × z!)
| |
m, which can be replaced by
x. The number of times the second outcome occurs is
n – m, which can be replaced by
y. The number of all outcomes is
n, which equals x + y.
x,
y, and
z. The number of all outcomes is
n, which equals x + y + z.
Let's examine the case of 6 × 5 = 30 in the fourth line of the three tables above. These numbers are the coefficients of the following terms found in the Binomial and Trinomial Expansions. The coefficients can be calculated from the exponents:
Term | 6A2B2 | 5A1B4 | 30A2B2C1 |
Result | 6 = 4! / 2! / 2! | 5 = 5! / 1! / 4! | 30 = 5! /2! /2! /1! |
The integer of the three numerators (4!, 5!, 5!) are the sum of the exponents and the integers of the denominators contain the exponents. The coefficient can be found in the following transformation:
6 × 5 = (4! / [2! × 2!]) × (5! / [1! × 4!]) =
(4! × 5!) / (2! × 2! × 1! × 4!) = 5! / (2! × 2! × 1!) = 30
The 4! in the numerator and the 4! in the denominator cancel out each other.
In all the above, we have assumed that all the variables are positive (have a +
sign).
(+A +B)n | (+A +B +C)n | etc. |
But what if one or more of the variables are negative (have a –
sign). For example:
(+A –B)n | (–A +B)n | (–A –B)n |
(+A +B –C)n | (+A –B +C)n | (–A +B +C)n |
(–A –B +C)n | (–A +B –C)n | (+A –B –C)n |
(–A –B –C)n | etc. |
This would seem to stir up a hornet's nest of painful problems. Not to worry. Pyramid-man to the rescue!
The Rule of Signs:
The sign of the term is positive, unless the sum of the exponent(s) is an odd number for those variable(s) having a negative coefficient in the original unexpanded expression.
This is really fairly easy:
An example:
Unexpanded expression | (–A +B –C)n | –A and –C are negative |
Expansion term | –A3B4C2 | 3 + 2 is odd, term is negative |
Expansion term | +A3B4C5 | 3 + 5 is even, term is positive |
Expansion term | +A2B3C2 | 2 + 2 is even, term is positive |
The same rules apply if all three (–A –B –C) are negative or only one (–A +B +C, +A –B +C, +A +B –C) is negative.
How does this magic
work? It follows the rules of multiplication:
Positive number times positive number is positive number | (+3 × +2 = +6). |
Negative number times positive number is negative number | (–3 × +2 = –6). |
Negative number times negative number is positive number | (–3 × –2 = +6). |
Thus, the odd powers of negative numbers are negative and the even powers of negative numbers are even:
–31 = –3, –32 = +9, –33 = –27, –34 = +81, –35 = –243.
And the multiplied powers of negative numbers follow these same multiplication rules:
–An × –Bm = –AnBm is a negative number, if n + m is odd;
–An × –Bm = +AnBm is a positive number, if n + m is even.
Today, spelling and arithmetic are lost arts–computers do it all. There are programs which will do Binomial, Trinomial, even Quadrinomial Expansion faster than the blink of an eye. Tomorrow, it will be an app
on our cell phones. There is no need for short-cuts.
And even if there is a need because of a power failure, then there is another method which is slightly superior. I had been pursuing the short-cut approach Fr. Deno used for Binomial Expansion, which involves the ratio of exponents with the previously-determined coefficient of an adjacent term. However, the Restated
formulae for calculating coefficients mentioned in the section on Pyramid Short-cut
is probably a little easier, faster, simpler, and cleaner–if a table of factorials or a hand-held calculator is available. Just use the exponents of the current term and the formulae n! / x! / y!
(binomial) or n! / x! / y! / z!
(trinomial), etc., where x, y, z are the exponents and n is the sum of the exponents.
I completed work on The Pyramid in the late 1980s. Someone at General Foods suggested publication in the Journal of Recreational Mathematics
. I was not sure whether or not someone else had already come up with the same ideas. I did not want to embarrass myself again with JRM as I did with my discovery that the sum of the n odd integers equals n squared
. I tried to research the matter on what then passed for the Internet. I found nothing, but the search engine was primitive.
During my work on The Pyramid, I had explained my discovery to my three sons. Colin, the oldest, talked it up at the University of Scranton with one of his friends, a math major. The friend expressed an interest in knowing more, so I pulled my notes together and sent him a copy. It came back a few months later–without comment. Deflating!
I focused on my day-job. The years went by quickly. Recently, I searched the Internet again on this topic–500,000 hits this time. I have not reviewed all half million links, but most seem to be blogs of graduate math students who are bored with their classes. They have figured out the triangular structure and the multinomial coefficients. None which I have seen come even close to finding all the connections I have documented here. Most call my creation Pascal's Pyramid
; some talk of Pascal's Tetrahedron
.
I have seen admonishments to the effect that it is a violation of scientific etiquette to name a discovery or invention after oneself. The idea is that if your work has merit others will call it by your name. So, my ever-so-dearest friends, my fame rests in your hands.