PROFESSOR: The binomial theorem extends
to a thing called the multinomial theorem,
whereas instead of taking a product of a sum of two things,
you'd take the product of a sum of k things
to get the multinomial theorem.
And what underlies it is a rule that we're
going to call the bookkeeper rule, and here's why.
So, the bookkeeper rule is about the question of,
look at the word bookkeeper and ask how many different ways
are there to scramble the letters in this word that
actually are distinguishable?
The point being that the two o's are indistinguishable,
so the order in which they appear doesn't matter.
Likewise, the three e's and the two k's.
Well, how do we answer this question?
The simple way to do it to begin with
is to label all of the indistinguishable
letters with subscripts to make them distinguishable.
So, I'm going to put subscripts 1 and 2 on the o's, 1 and 2
on the k's, and 1, 2, and 3 on the e's.
Now, all the 10 letters are distinguishable.
And if I ask how many ways are there
to permute these 10 letters, the answer,
we know by the generalized product
rule is simply 10 factorial.
Now, my strategy is going to be to use the division
rule to count the number of patterns of the letters
in the word with no subscripts.
And the way I'm going to do that is
take one of these subscripted words and erase the subscripts.
So, I'm going to map it to the same permutation of letters
with no subscripts.
I've just done that.
Here I've taken an arbitrary permutation
of the subscripted word, and then I've erased the subscripts
and consolidated the letters.
And I wind up with this permutation.
Now, if I want to count the number
of unsubscripted permutations, then I simply
figure out that this mapping is K to 1,
and I'm going to then divide by K. Well, how many to 1 is it?
Well, how many subscripted words map to this given pattern?
The answer is the subscripts on the o's don't matter,
so there's two possible orders in which those subscripts might
appear.
Subscripts on the k's don't matter.
There's two possible orders in which
those subscripts might appear.
Subscripts on the e's don't matter.
Three possible orders, or 3 factorial possible orders that
the subscripts might occur in the e's.
The net result is that with two o's, two k's, and three
e's, the mapping is 2 factorial by 2 factorial
by 3 factorial to 1.
And that instantly gives us, by the division rule,
that the total number of permutations
of the letters in the word bookkeeper
is 10 factorial over 2 factorial times 2 factorial times 3
factorial.
More generally by the same reasoning
if, I look at a sequence of n letters, of which n1 are
a's and n2 are b's up through nk are z's, then
the number of permutations of those letters
with the repeated a's, b's, and Z's is
n factorial divided by n1 factorial times
n2 factorial through nk factorial.
And this formula occurs so often that it has a name.
It's called a multinomial coeff--
there's a name for it written in this format,
n over n1, n2 through nk.
You could start to say n choose n1 choose n2 choose nk,
if you're thinking about how we pronounce
the binomial coefficients.
The convention is that the sum of the ni's is supposed
to be equal to the numerator n.
This is called a multinomial coefficient.
So, n factorial divided by this product of factorials
is written in somewhat shorter notation
without the factorials as a multinomial coefficient.
Binomial coefficient, by the way, are a special case.
When we write n choose k, if we wrote it
as a multinomial coefficient, you'd
have to write it as n choose k and then choose n minus k.
So, we can apply this to think about words and coefficients
and expanding things that are more than binomials.
So, let's look at expanding a quintomial, a sum of five
things, E, M, S, T, and Y. And I raise that
to the seventh power.
So, that means in these products of seven of these terms,
I'm looking at words of length seven
whose components are the letters E, M, S, T, and Y.
And So, if I multiply this out, applying the distributive law,
I would wind up with 5 to the 7th terms,
each of them consisting of a permutation of the letters
E, M, S, T, and Y.
And if I ask what's the coefficient in that expansion
of the term E, M, S cubed, T, Y, it's
exactly the number of ways of permuting these five
letters, a word of length seven made out of these five letters
with three occurrences of S. In other words,
the coefficient of E, M, S cubed, T, Y in this product
is the number of ways of rearranging the letters
in this sequence of seven.
It's the word systems, which is why
we chose it to be rememberable.
How many ways are there to rearrange
the letters in the word systems by the bookkeeper rule?
There are seven.
Choose 1, 1, 3, 1, 1.
Let's do another example.
What's the coefficient of BA cubed
N squared if I expand this trinomial, B plus A
plus N to the sixth power?
Well, now again I have 3 to the 6th terms.
How many of them involve a B, three A's, and two
N's by the bookkeeper rule?
It's the number of ways-- well, it's
the number of ways of rearranging
the letters in the word banana.
And by the bookkeeper rule, that's
six with subscripts 1, 3, and 2.
More generally, this is what the multinomial theorem says.
If I look at the coefficient of the term--
a product of Xi to the ri's in an expansion
of a k-nomial, a sum of k distinct variables raised
to the n-th power, now I've got if I expanded this
out using the distributive law without collecting terms,
I'd have k to the n terms, each of which
was a permutation of the X1's through Xk's, with repeats.
And then if I ask, how many of those products,
if any of these k variables have this many X1's, this many
X2's, through this many rk's-- this many Xk's, I'm asking
again a bookkeeper question.
And the answer is n choose r1, r2 through rk.
So, now we're ready for the record
to state the general multinomial formula.
If I take a sum of k terms, a k-nomial to the nth power,
then expressing it in concise notation,
it's the sum over r1 through rk summing to n of the multinomial
coefficient n r1 through rk times this product of Xi's.
I'm not putting a highlighted box around it,
because this is not a formula which is particularly
important to memorize.
And it's clearly all clogged up with subscripts.
But nevertheless, it's good to have sometimes for the record.
And next week, we will continue with this theme
about the connection between counting and algebra.
And in particular, not only ordinary polynomials
as we've been looking at here with a product of sums,
but in fact, infinite polynomials or infinite series
when we pick up generating functions next week.