Skip to main content

Exercises 9.4 Exercises

1.

Expand and simplify the binomial \((x+y)^{10}\text{.}\)

2.

Expand and simplify the binomial \((3m-n)^5\text{.}\)

3.

Expand and fully simplify the binomial \((2x-1)^7\text{.}\)

4.

Prove that if \(n \ge 1\text{,}\)

\begin{equation*} \sum_{r=0}^n (-1)^r\binom{n}{r} = 0. \end{equation*}
Hint.

Binomial theorem.

5.

Fix \(n \ge 1\text{.}\) Let \(E\) be the sum of all the \({{n}\choose{r}}\) where \(r\) is even, and let \(O\) be the sum of all the \({{n}\choose{r}}\) where \(r\) is odd. Which is larger: \(E\) or \(O\text{?}\)

Hint.

You just proved that the alternating sum of binomial coefficients is zero. If that's true, what can you say about the combined terms of even index and the combined terms of odd index?

6.

We proved

\begin{equation*} {{n}\choose{r}} = {{n-1}\choose{r-1}} + {{n-1}\choose{r}} \end{equation*}

combinatorially, by appealing to the objects that each side of the equation is counting. Now, prove this statement algebraically, using factorial arithmetic and the formula for \({{n}\choose{r}}\text{.}\)

Hint.

Start with the right side of the equation and combine the two fractions.

7.

We proved

\begin{equation*} \sum_{r=0}^n \binom{n}{r} = 2^n \end{equation*}

using the binomial theorem. This time, prove it combinatorially, by proving that each side of the equation counts the same object.

8.

Generating functions allow us to use tools from algebra, calculus, and elsewhere to learn about sequences. The binomial theorem establishes \((1+y)^n\) as a generating function for the sequence of binomial coefficients for fixed \(n\text{.}\) Differentiating this function yields another combinatorial identitiy:

\begin{equation*} n(1+y)^{n-1} = \sum_{r=0}^n r{{n}\choose{r}}y^{r-1}. \end{equation*}

  1. If you have had calculus, verify this yourself.

  2. Calculate the value of the sum

    \begin{equation*} \sum_{r=0}^n r\binom{n}{r}. \end{equation*}

    (Your answer will be an expression involving \(n\text{.}\))

  3. What is

    \begin{equation*} \sum_{r=0}^{17} r{{17}\choose{r}}? \end{equation*}
9.

How many different teams can be made if we must make \(8\) teams from \(30\) people where the first four teams each have \(4\) people, the fifth has \(3\) people, the sixth has \(2\) people, and the seventh has \(3\) people?

10.

Five students are to be allocated into three distinguishable teams.

  1. How many distributions are there? In other words how many different possible sizes can the teams have? (Include empty teams.) e.g. “Team 1 and 2 each have two members and Team 3 has one member” is one of the distributions being counted; perhaps \(221\) is a good way to represent this distribution. Enumerate (list out) all possible distributions and then check your answer with the appropriate formula.

  2. Suppose a distribution is chosen: two students will be on the first and second teams each, while a single student will be on the third team. How many different combinations of teams are there? e.g. “Team 1: Alicia and Carlos, Team 2: Davina and Bob, Team 3: Erik” is one of the combinations of teams being counted. Perhaps \(AC|DB|E\) is a good way to represent these teams. Enumerate all possible combinations of teams and check your answer with the appropriate formula.

11.

This exercise gets at the same thing as the above exercise. If you understood that one you could skip this one, or vice-versa.

  1. The polynomial \((a+b+c)^5\) is to be fully expanded. How many distinguishable terms (ignoring coefficients) does it have? That is, how many ways can we choose nonnnegative exponents \(h\text{,}\) \(j\text{,}\) and \(k\) for the term \(a^hb^jc^k\) such that \(h+j+k=5\text{?}\) Enumerate all such terms and then check your answer with the appropriate formula. Your list should include expressions like \(ab^3c\text{.}\)

  2. How many ways are there to get a term like \(ab^3c\) in the expansion of the above polynomial? Your answer is the coefficient of the term. Enumerate all such objects and then check your answer with the appropriate formula. Your list should include anything that reduces to \(ab^3c\text{,}\) including \(abbbc\) and \(bacbb\text{.}\)

12.

A lazy math teacher is writing an exam.

  1. The lazy math teacher has a class of \(31\) students and wants to assign some of them A’s, some B’s, some C’s, some D’s, and some F’s. If it is not important to the teacher how many of each grade is assigned, how many ways can they choose how many of each to give?

  2. The lazy math teacher has a class of \(31\) students and wants to assign \(3\) A’s, \(6\) B’s, \(10\) C’s, \(6\) D’s, and the rest F’s. It is not important to the teacher which student gets which grade. How many ways can this assignment be done?

13.

A map of fifty interlocking landmasses is to be colored using four colors (say red, green, blue, and yellow).

  1. How many ways are there to choose the number of landmasses that will be painted with each color?

  2. Suppose that \(15\) of the landmasses will be painted red, \(12\) green, \(9\) yellow, \(14\) blue. How many ways are there to choose which landmasses will be painted with each color?

This problem is a reference to the famous four color theorem, the first major theorem to be proven with the aid of a computer.

14.

How many distinguishable arrangements are there of the letters in ANTIDISESTABLISHMENTARIANISM?

Hint.
There are four A's in the word but we can't tell them apart. So of the total number of characters in the rearranged word, we must choose four of them to be A's. Then we will choose the leftover characters to be N's, etc.
15.

What is the coefficient of the term \(w^3x^4yz\) in the polynomial \((w+x+y+z)^9\text{?}\)

16.

Expand \((x+y+z)^2\) without distributing or “FOIL”ing.

17.

Calculate

\begin{equation*} \sum_{r_1+r_2+r_3=n} \binom{n}{r_1,r_2,r_3}. \end{equation*}

Give an explanation for your answer.

Hint.
The bi...uh...trinomial theorem.
18.

The binomial coefficients could be represented visually using a triangle, incorporating their recurrence. How can the trinomial coefficients be visually represented? Find a way to draw this object from \(n=0\) down to \(n=4\text{.}\)

Hint.
Slices, or colored pencils.