PROFESSOR: There are two generalizations of the bijection rule and the product rule that come up all the time and play an essential role in the repertoire of any counter. So let's look at those.
The first of these is a generalization of the product rule. And let's see an instance where it comes up. Suppose I wanted to count the number of lineups of five students in the class. So if I let S be the number of students, and let's say, for the afternoon session S is 91, then the number of lineups of five students-- if I use the ordinary product rule, I would get-- I'm talking about S to the fifth, that is, sequences of length five of elements of S.
And so the product rule would say, take 91 to the fifth as the number of lineups of five students. And that would be correct if the same student could appear twice in line, but that, of course, isn't possible with real students. So the lineups have no repeats. And what we're really counting is the number of those sequences of length five of students with no repeats. And the generalized product rule tells you quite straightforwardly how to count those. Namely, there are 91 ways to choose the first student among the 91. And whichever first student you've chosen, that leaves 90 other students you could choose to be second.
And once you've chosen the first two, that leaves 89 students you could choose for the third, and 88 for the fourth, and 87 for the fifth. And the formula then is 91 times 90 times 89, 88, 87, for the number of sequences of distinct students of length five. Now, one nice way to express the 91 down to 87, in terms of factorials, is its 91 factorial, which is the product from 1 to 91, and divided by the product from 1 to 86, which cancels out the first 86 terms in 91 factorial, leaving me with exactly 87 through 91 product.
So the second rule is a sort of obvious generalization of the bijectional, but I'm getting ahead of myself. Let's state the generalized product rule in general. So if we let Q be a set of length-k sequences with the following property, there are n1 possible first elements among these length-k sequences. And for every one of the first possible elements, if you look at the number of tuples with what the second possible coordinates for a given first coordinate, it's always n2.
And likewise, if you look at the number of possible third coordinates given the first two, it's n3 and it's uniform no matter what the first two are. Then if you have this kind of a set up, which is exactly what happens when you're picking one student after another and they can't compete, you discover that the length-k sequences with n1 , first possible choices, n2, second possible choices, down through nk, k-th possible choices is n1 through nk. So that's the statement of the generalized product rule in the magenta box.
Now, we come to the generalized bijection rule, which is called the division rule. And a simple, memorable way to illustrate is if you wanted to count the number of students in class 6.042, you could count the number of students fingers and divide by 10. Now, it's probably harder to count fingers than students, so this is not meant as a practical method. But it illustrates a basic and straightforward idea. Of course, it's implicitly assuming that we don't have any instances of amputations or polydactylism, and that, in fact, every student has exactly 10 fingers.
OK, so in general, the division rule can be stated this way, if I have a total function from a set A to a set B, domain A, co-domain B, and this mapping is k-to-1, then the cardinality of A is simply k times the cardinality of B. So k-to-1 means that exactly k A elements hit each B element. Another way to say it is that there are exactly k arrows into every element of B. So then the number of arrows is simply k times B. And if you have a total function on A, the number of arrows is equal to the size of A, and that's where we get the formula. OK. And that's the generalized bijection rule.
Let's apply it in a crucial example that is absolutely basic and we'll be using repeatedly. Suppose that I want to know how many possible subsets of size four are there from the numbers 1 through 13? So I have 13 possible numbers that I can choose. I want to pick out any four of them and I want to know how many ways are there to do that. And we'll do that by finding a mapping from things we know how to count to these particular subsets.
So what we know how to count is if I let A be the set of all permutations of 1 through 13, then I know that the size of A is 13 factorial because there's 13 choices for the first element of the permutation, 12 for the second, down to one for the 13th. And let's let B be this object that I want to count, namely, the set of size four subsets of 1 through 13. And I want to find a mapping from A that I know how to count to B that I don't yet know how to count, but in a way where I can figure out that it's k-to-1 for a k that I can also count. How do I do that?
Well, let's take an arbitrary permutation of A, that is to say, a sequence of the elements of A in some order-- call them a1, a2, through a13. So these numbers a1 through a13 are those numbers 1 through 13 in some unknown order. And I'm going to map a permutation of A, like this, to its first four elements. Just take the first four elements of the permutation and map them to the set consisting of those four elements.
Now, since this is a permutation, these elements are all different, so I really do get a set of four different things here, a1, a2, and a3. And a4 is supposed to be different. This gives me a very well-defined total function from a permutation of 13 numbers to set of its first four elements. And now what we want to know is what kind of a mapping is this? And I'm going to argue that it's k-to-1 for a k that's not very hard to count.
So when I look at what other things map to the set a1, a2, a3, a4, we mapped a permutation to its first four elements. And if we've got a1 through a4 as the set, what other things map to that set a1, a2, a3, a4? Well, the answer is any permutation with the same first four elements, but possibly in a different order, because we're just going to take the first four in sequence and map them to the set of those first four. The order in which the first four doesn't matter. OK?
And likewise, the order of the remaining nine elements, 5 through 13, also doesn't matter. Whatever they are, if I have a given set of four elements to start, no matter what the remaining 9 are, they're going to map to the same subset of four elements. So there are 4 factorial possible ways that the first four elements can be permuted. And there are 9 factorial ways that the last nine elements can be permuted. And every one of these goes to the same set of four elements, a1 through a4. And those are the only ones that go there.
And so what we've figured out is that the mapping of these kind of sequences with the given four elements first in some order and the remaining nine elements in some other order is 4 factorial times 9 factorial-to-1. There are 4 factorial times 9 factorial permutations that map to any given set of four elements. And that means that by applying the division rule, I've discovered that the size of A, which I know is 13 factorial, is equal to that k of the k-to-1 of 4 factorial times 9 factorial times the size of B.
B is the subsets of size four that I'm trying to count. And so what I get is that the size of B is simply 13 factorial divided by that k, 4 factorial 9 factorial, 13 factorial over 4 factorial 9 factorial. And this number comes up so often that it has this special notation called binomial coefficient notation, which we read as 13 choose 4.
In general, if I have an n element set and I'm going to choose a subset of m of them-- generalizing this argument because the 4 and the 9 and the 13 were completely arbitrary and the argument works in general-- is that the number of ways to choose a set of m elements among n is n choose m. And the definition of n choose m is n factorial over the m factorial ways to permute the first m elements and the n minus m factorial ways to permute the remaining n minus m elements. And again, that notation, the binomial coefficient, is called n over m is n choose m. This is an absolutely fundamental formula that you need to remember because we will be using it constantly and repeatedly.