how about a proof for the multinomial theorem?
Useless computational theorem? Yes.
Useful theorem? Yes, good combinatorial exercise
So we basically want to find a generalised 'formula' for
^n)
(Where as the binomial theorem is just for
^n)
, ie when
)
So let's start off by doing some experimentation. Let's look at
^7)
. How do we expand this? Let's consider the first 2 brackets, namely:
(x+y+z)(x+y+z)^5 = (x \cdot x + xy + xz +yx + y \cdot y + yz + zx +zy+ z \cdot z)(x+y+z)^5)
Now leaving them unsimplified we can see that the 2 brackets expanded into 9 'unsimplified' terms. Which is expected since we have 3 choices from the first bracket and another 3 choices from the 2nd bracket.
This means that if we expanded all 7 brackets we would get a total of
unsimplified terms since there are 7 brackets and each bracket has 3 'choices'.
Now let's assume we have expanded all 7 brackets and we want to find the coefficient of the
term.
We notice a few things: the powers all add up to 7 and we realise that this is just a direct application of the Mississippi 'formula'.
Just imagine we have a lot
terms lying around to be collected as like terms after the expansion of the 7 brackets. However each would have a different permutation.
As we list some:
Thus the total 'amount' of
terms lying around would be
.
Let's try another experiment, let's say we want to find how many of
terms are lying around uncollected after the expansion of the 7 brackets.
We realise after undergoing the same process as before we get
terms are lying around.
A pattern can be seen: The numerator is always 7! (As we expect since there are always 7 terms to permute).
The denominator's factorials are correspondent to the power of each term.
Therefore we can generalise this a bit and say the coefficient of any term in the expansion of
is
!p(y)!p(z)!})
where
)
denotes the power of
respectively of the term.
Now that we have generalised the result for working out the coefficients of any term we need to generalise what
will be expanded into.
Let's try work out how many terms
when all like terms are collected.
However
seems too tedious to work with, so let's try an easier example
^3)
To work out how many different like-terms there are in total when
is expanded let's consider what we discovered before with the exponents. We found that the exponent must add up to
. So all exponents of the terms of
when expanded must add up to 3.
How many different combinations can we get? Certainly there can be all the different permutations of
)
,
)
and
)
.
Thus the total number of terms we should expect should be
Which when we expand
we certainly do get 10 terms!
Now we can try to find a more general formula for the expansion of
^3 = \sum_{p_1,p_2,p_3}\left[\left(\frac{3!}{p_1!p_2!p_3!}\right)\left(x^{p_1}y^{p_2}z^{p_3}\right)\right])
What exactly does this mean?
Basically it means that we take the summation of all permutations of non-negative integer indices
through to
such that
^3 = \sum_{p_1,p_2,p_3}\left[\left(\frac{3!}{p_1!p_2!p_3!}\right)\left(x^{p_1}y^{p_2}z^{p_3}\right)\right] = \sum_{0,0,3}\left[\left(\frac{3!}{0!0!3!}\right)\left(x^{0}y^{0}z^{3}\right)\right] + \sum_{0,1,2}\left[\left(\frac{3!}{0!1!2!}\right)\left(x^{0}y^{1}z^{2}\right)\right] + \sum_{1,1,1}\left[\left(\frac{3!}{1!1!1!}\right)\left(x^{1}y^{1}z^{1}\right)\right])
\left(x^{0}y^{0}z^{3}\right)\right] + \left[\left(\frac{3!}{0!0!3!}\right)\left(x^{3}y^{0}z^{0}\right)\right] + \left[\left(\frac{3!}{0!0!3!}\right)\left(x^{0}y^{3}z^{0}\right)\right] + \left[\left(\frac{3!}{0!1!2!}\right)\left(x^{0}y^{1}z^{2}\right)\right] + \left[\left(\frac{3!}{0!1!2!}\right)\left(x^{0}y^{2}z^{1}\right)\right] + \left[\left(\frac{3!}{0!1!2!}\right)\left(x^{1}y^{0}z^{2}\right)\right] + \left[\left(\frac{3!}{0!1!2!}\right)\left(x^{1}y^{2}z^{0}\right)\right] + \left[\left(\frac{3!}{0!1!2!}\right)\left(x^{2}y^{1}z^{0}\right)\right]+ \left[\left(\frac{3!}{0!1!2!}\right)\left(x^{2}y^{0}z^{1}\right)\right] + \left[\left(\frac{3!}{1!1!1!}\right)\left(x^{1}y^{1}z^{1}\right)\right])
\left[z^3+x^3+y^3\right] + \left(\frac{3!}{0!1!2!}\right)\left[yz^2+y^2z+xz^2+xy^2+x^2y+x^2z\right] + \left(\frac{3!}{1!1!1!}\right)\left[xyz\right])
 + 6xyz)
Now we are ready to play around with our general statement
Using the same format:
^n = \sum_{p_1,p_2...p_q}\left[\left(\frac{n!}{p_1!,p_2!...p_q!}\right)\left(x_1^{p_1}x_2^{p_2}...x_q^{p_q}\right)\right])
Which basically means that we take the summation of all permutations of positive integer indices
through to
such that
Home
Help
Search
Login
