Teacher resources and professional development across the curriculum
Teacher professional development and classroom resources across the curriculum
The counting function C(n,k) and the concept of bijection coalesce in one of the most studied mathematical concepts, Pascal's Triangle. At its heart, Pascal's Triangle represents a recursive way to compute all the C(n,k), the numbers of k-subsets of an n-element set for any n and any k. As a recursive pattern, Pascal's Triangle incorporates previously known values in the creation of new ones. To portray the relationship at the heart of the triangle, we will again solve a particular problem in two different ways.
Once again let's address the question of how many k-subsets there are of an n-element set. Solved one way, we know the answer is . Now as we explore the question again, we will also consider whether or not a k-subset contains the element "n." Using the flavors example, we would sort all of our combinations of flavors into two sets, those that have "salty" as one of their components and those that do not. In this strategy, sometimes known as"weirdo" analysis; we call "n" or "salty" the "weirdo" and make deductions by counting the sets that either contain it or don't contain it.
To start, let's focus on just the k-subsets. We can separate these subsets into two piles. Pile A will have all the k-subsets that contain the element n. Pile B will have all the k-subsets that do not contain n. In terms of flavors, A has all of the combinations containing "salty," and B has all those that don't. Note that both pile A and pile B are sets of subsets.
All of the subsets in pile A have to contain n; therefore, to figure out how many of them there are, we can just pretend that they are only of size k-1 (because one of the slots is always filled by n).
_ _ _ _ … n
(In other words, k spaces, one of which is always filled by n, means that there are actually only k-1 spaces in play.)
Likewise, because n is not allowed to move around, it is in some sense "out of play" in our larger n-sized set. This means that each of the subsets in pile A has k-1 spaces to fill using only the elements {1, 2, …, n-1}. The number of these subsets in pile A is the same as the number of k-1 subsets of an (n-1)-sized set. We thus have a bijection between the set of k-sized subsets containing n and the set of (k-1)-sized subsets of an (n-1)-sized set.
We know the way to find how many (k-1)-sized subsets there are of (n-1) by using our C(n,k) formula. For simplicity's sake we'll just write C(n-1,k-1).
Now, let's look at pile B containing the k-sized subsets that do not contain n. For each subset we have to fill k spaces using only the elements {1, 2, …, n-1}. This is the same as asking how many k-sized subsets there are of an (n-1)-sized set. We again can use our handy formula, written as C(n-1,k).
Finally, we know that if we combine pile A and pile B, we should have the total amount of k-sized subsets of an n-sized set, which can be expressed as C(n,k).
The total number of subsets of size k, C(n,k), is equal to the total of those that include n, the weirdo, C(n-1, k-1), plus those that don't, C(n-1, k), or:
C(n,k) = C(n-1, k-1) + C(n-1,k)
This relationship, known as Pascal's equation, gives us a recursive relationship that enables us to compute the number of k-subsets of an n-element set using the results we already have for smaller subsets of smaller sets. Organizing the results of a few iterations of this rule into a chart yields an interesting structure.
Looking at a few iterations of Pascal's equation gives us the following result in tabular form:
This information is probably more familiar to you presented in the following form:
In this arrangement, each number is denoted by C(row, column). Note that the first row is considered row zero, as is the first column. So, returning to our taste example, we can find the number of combinations of three out of six by looking at row 6 and finding column 3. The value found in that position, 20, is in complete agreement with everything we've done before. To find how many subsets of any size there are in a group of six, we simply add all the numbers in the sixth row, taking care not to add the 1 that represents the empty set.
Notice that C(0,0) and C(n,n) are both equivalent to one, reminding us that there is only one way to choose zero items out of a set of zero, and only one way to choose n items out of a set of n items when the order does not matter.
Pascal's Triangle is a mathematical paradise, with many interesting relationships hidden in its structure. First, note that the sum of entries of any row n is equal to 2^{n}, in agreement with our binary strings bijection from before.
4^{th} ROW
1 + 4 + 6 + 4 + 1 = 16
2^{n} = 2^{4} = 16
Also, the entries in the n^{th} row of the triangle give the coefficients of the terms in the expansion of a simple binomial raised to the power n, such as (x+y)^{n}. For example:
(x+y)^{3} = 1x^{3} + 3x^{2}y + 3xy^{2} + 1y^{3}
The coefficients of this polynomial can be found in the third row of Pascal's Triangle. Because they are useful in expanding binomials, the various sets of C(n,k)s are also known as binomial coefficients. Note that this isn't magic; it's simply the result of counting the number of subsets with k factors of x.
Another interesting phenomenon in Pascal's Triangle can be found by looking at so-called "hockey-sticks." A hockey-stick is a pattern within the triangle composed of a diagonal string of numbers and a terminating offset number, such as those shown here:
What is fascinating in a hockey-stick pattern is that the linear string of numbers, when added together, totals the value of the number that is offset. For example, the sum of the numbers 1, 6, 21, and 56 is 84 (the blue pattern in the figure above). This works no matter where in the triangle we draw a hockey stick, as long as it starts with a "1."
To get a sense for why this holds true, let's look at the orange hockey stick above, 1 + 3 + 6 = 10. Recognizing the "10" in our pattern as the second entry of the 5^{th} row, we can write it as 10 = C(5,2). Let's plug this into Pascal's equation:
C(n,k) = C(n-1, k-1) + C(n-1, k)
C(5,2) = C(4, 1) + C(4, 2)
Note that C(4,2) is the second entry in row four, "6," which is part of our hockey stick. However, C(4,1), the first entry in row four, is not part of our pattern. If we use Pascal's equation again, we find:
C(4,1) = C(3, 0) + C(3, 1)
C(3,0) = 1 and C(3,1) is the first entry of row three, which is "3." Plugging these results back into the equation for C(5,2), we get:
C(5,2) = C(4,2) + C(3,1) + C(3,0) => 10 = 6 + 3 + 1
This is the hockey stick identity that we set out to prove!
There are many other fascinating mathematical series and relationships to be found in the triangle, such as triangular numbers, primes and their multiples, and Fibonacci numbers to name but a few.
By the way, Pascal did not invent this triangle. It was known centuries earlier to both the Indians and Chinese as having particular use in finding combinations, as we have just seen. The Chinese mathematicians Yang Hui and Chu Shih Chieh knew about it at least 350 years before Pascal's work.
Next: 2.5 The Order of the Garter