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.