Online Course Discussion Forum
Chapter 6 Combinatorics Math Challenge II-A
Thank you!
Let me do 6.23 first as it's a little different than the others (which give us a good chance to review the binomial theorem a little).
Remember the idea of a combinatorial proof is that you count the same thing two different ways. Then, as long as both ways are correct, the two answers MUST be equal.
As an example of this (not from combinatorics), consider the area of a 3-4-5 triangle. Since this is a right triangle, we know it's area is simply$$\frac{1}{2}\cdot 3\cdot 4.$$However, we could also use Heron's formula to calculate the area as$$\sqrt{6(6-3)(6-4)(6-5)}.$$Now, taking for granted both answers are correct, we've proven that $$\frac{1}{2}\cdot3\cdot 4 = \sqrt{6(6-3)(6-4)(6-5)}$$even if we don't do any calculations!
This is the rough idea here. Take one problem and solve it two different ways to prove our two quantities are equal.
For 6.23, consider the following question:
Suppose you have $n$ total people. You want to choose a group of $k$ people and have one of those $k$ people be the leader of the group. How many ways can you pick the group+leader?
Make sure you can explain why both quantities in 6.23 are answers to this question, which then shows that the two quantities must be equal!
Now let's examine the Binomial Theorem and Multinomial theorem a little. I wouldn't worry too much about 6.25, it's more important to be able to apply the theorem, and in applying it you will gain a better understanding of the general idea anyway.
Let's start with the binomial theorem. As an example, the binomial theorem (similar to Pascal's triangle) says $$\begin{aligned} (x+y)^6 &= \binom{6}{0}x^6y^0 + \binom{6}{1}x^5y^1 + \binom{6}{2}x^4y^2 + \cdots + \binom{6}{6}x^0y^6 \\ &=\frac{6!}{6!0!}x^6y^0 + \frac{6!}{5!1!}x^5y^1 + \frac{6!}{4!2!}x^4y^2 + \cdots + \frac{6!}{0!6!}x^0y^6 \\ &= x^6 + 6 x^5y + 15 x^4y^2 + 20 x^3y^3 + 15x^2y^4 + 6xy^5 + y^6 \\ \end{aligned}$$ Examining the coefficients a little, note that the coefficient of $x^4y^2$ is $\dfrac{6!}{4!2!}$ which is the number of ways to arrange four $x$'s and two $y$'s. This is true for the other coefficients as well (and will continue to be true for the multinomial theorem).
To answer your question a bit from the other post, a lot of times when we say "use the binomial theorem" we really mean to plug in values for $x$ and $y$ in an equation like the one above. For example, if $x = 1$ and $y = 1$, note all powers of $x$ and $y$ disappear. Hence, we get $$2^6 = (1+1)^6 = \binom{6}{0} + \binom{6}{1} + \binom{6}{2} \cdots + \binom{6}{6}.$$ Thus, we've prove than $2^6$ equals the sum of these binomial coefficients! A similar argument using $x=1$ and $y = -1$ gives $$0 = (1+ (-1))^6 = \binom{6}{0} - \binom{6}{1} + \binom{6}{2} - \binom{6}{3} + \binom{6}{4} - \binom{6}{5} + \binom{6}{6}.$$ But wait, by symmetry, $\binom{6}{0} = \binom{6}{6}$, $\binom{6}{1} = \binom{6}{5}$, and $\binom{6}{2} = \binom{6}{4}$ so we actually have $$0 = 2\binom{6}{0} - 2 \binom{6}{1} + 2\binom{6}{2} - \binom{6}{3}$$ so actually $$\frac{1}{2}\binom{6}{3} = \binom{6}{0} - \binom{6}{1} + \binom{6}{2}.$$ Note this is exactly what we want for 6.30 when $n=1$. Try to do something similar for $n=2$, so you need to look at $(1+(-1))^{10}$.
I'll expand on this with the multinomial theorem a bit below when I have a chance.
Social networks