# Section7.4The algebra of combinations

Earlier in this chapter we determined the number of $k$-subsets of a set of size $n$. These numbers, denoted by $C(n,k) = nCk = \binom{n}{k}$ and determined by the formula $\frac{n!}{k!(n-k)!}$ are known as binomial coefficients. It seems likely that you will have already seen the arrangement of these binomial coefficients into a triangular array — known as Pascal's triangle, but if not…

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1

et cetera.

The thing that makes this triangle so nice and that leads to the strange name “binomial coefficients” for the number of $k$-combinations of an $n$-set is that you can use the triangle to (very quickly) compute powers of binomials.

A binomial is a polynomial with two terms. Things like $(x+y)$, $(x+1)$ and $(x^7+x^3)$ all count as binomials but to keep things simple just think about $(x+y)$. If you need to compute a large power of $(x+y)$ you can just multiply it out, for example, think of finding the 6th power of $(x+y)$.

We can use the F.O.I.L rule to find $(x+y)^2 = x^2 + 2xy + y^2$. Then $(x+y)^3 = (x+y) \cdot (x+y)^2 = (x+y) \cdot (x^2 + 2xy + y^2)$.

You can compute that last product either by using the distributive law or the table method:

 $x^2$ $+ 2xy$ $+ y^2$ $x$ $+ y$

Either way, the answer should be $(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$.

Finally the sixth power is the square of the cube thus \begin{gather*} (x+y)^6 = (x+y)^3 \cdot (x+y)^3\\ = (x^3 + 3x^2y + 3xy^2 + y^3) \cdot (x^3 + 3x^2y + 3xy^2 + y^3) \end{gather*}

For this product I wouldn't even think about the distributive law, I'd jump to the table method right away:

 $x^3$ $+ 3x^2y$ $+ 3xy^2$ $+ y^3$ $x^3$ $+ 3x^2y$ $+ 3xy^2$ $+ y^3$

In the end you should obtain \begin{equation*} x^6 + 6 x^5y + 15 x^4y^2 + 20 x^3y^3 + 15 x^2y^4 + 6 xy^5 + y^6. \end{equation*}

Now all of this is a lot of work and it's really much easier to notice the form of the answer: The exponent on $x$ starts at 6 and descends with each successive term down to 0. The exponent on $y$ starts at 0 and ascends to 6. The coefficients in the answer are the numbers in the sixth row of Pascal's triangle.

Finally, the form of Pascal's triangle makes it really easy to extend. A number in the interior of the triangle is always the sum of the two above it (on either side). Numbers that aren't in the interior of the triangle are always 1.

We showed rows 0 through 6 above. Rows 7 and 8 are

 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1.

With this information in hand, it becomes nothing more than a matter of copying down the answer to compute \begin{equation*} (x+y)^8 = x^8 + 8x^7y + 28x^6y^2 + 56x^5y^3 + 70x^4y^4 + 56x^3y^5 + 28x^2y^6 + 8xy^7 + y^8. \end{equation*}

##### Exercise7.4.1

Given the method using Pascal's triangle for computing $(x+y)^n$ we can use substitution to determine more general binomial powers.

Find $(x^4 + x^2)^5$.

All of the above hinges on the fact that one can compute a binomial coefficient by summing the two that appear to either side and above it in Pascal's triangle. This fact is the fundamental relationship between binomial coefficients — it is usually called Pascal's formula.

We are going to prove it twice.

##### Proof

There are quite a few other identities concerning binomial coefficients that can also be proved in (at least) two ways. We will provide one or two other examples and leave the rest to you in the exercises for this section.

Let's try a purely algebraic approach first.

##### Proof

A combinatorial argument usually involves counting something in two ways. What could that something be? Well, if you see a product in some formula you should try to imagine what the multiplication rule would say in that particular circumstance.

##### Proof

The final result that we'll talk about actually has (at least) three proofs. One of which suffers from the fault that it is “like swatting a fly with a sledge hammer.”

The result concerns the sum of all the numbers in some row of Pascal's triangle.

Our sledge hammer is a powerful result known as the binomial theorem which is a formalized statement of the material we began this section with.

We won't be proving this result just now. But, the following proof is a proof of the previous theorem using this more powerful result.

##### Proof

Our second proof will be combinatorial. Let us re-iterate that a combinatorial proof usually consists of counting some collection in two different ways. The formula we have in this example contains a sum, so we should search for a collection of things that can be counted using the addition rule.

# Subsection7.4.1Exercises

1. Use the binomial theorem (with $x=1000$ and $y=1$) to calculate $1001^6$.

2. Find $(2x+3)^5$.

3. Find $(x^2+y^2)^6$.

4. The following diagram contains a 3-dimensional analog of Pascal's triangle that we might call “Pascal's tetrahedron.” What would the next layer look like? \ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi 5. The student government at Lagrange High consists of 24 members chosen from amongst the general student body of 210. Additionally, there is a steering committee of 5 members chosen from amongst those in student government. Use the multiplication rule to determine two different formulas for the total number of possible governance structures.

6. Prove the identity \begin{equation*} \binom{n}{k} \cdot \binom{k}{r} \; = \; \binom{n}{r} \cdot \binom{n-r}{k-r} \end{equation*} combinatorially.

7. Prove the binomial theorem. \begin{equation*} \forall n \in \Naturals, \; \forall x,y \in \Reals, \; (x+y)^n \; = \; \sum_{k=0}^n \binom{n}{k} x^{n-k}y^k \end{equation*}