Exercises

Exercises 2.7 Exercises

Additional Exercises for Chapter 2

1.

The latest album release from the worldwide famous Kpop group ONCE has four different versions for sale: versions L, O, V, and E. Preorder numbers by version as reported by Korean newspaper Dispatched are as follows:

L: 20,000
O: 25,000
V: 22,500
E: 30,000

How many units did ONCE's album move in preorders, total? Can we also determine how many people preordered the album?

2.

The local bank Factorial Financials enforces the following restrictions on its online banking passwords:

Should only contain alphanumeric characters (A-Z, 0-9);
Should be exactly 8 characters in length; and
Should start and end with a letter.

How many possible passwords can be created?

Answer

$26^2 \cdot 36^6\text{.}$

3.

A new format for passenger vehicle licence plates issued in the province is being proposed, that adheres to the following conditions:

Pattern is AB123-4CD (or letter-letter-digit-digit-digit--digit-letter-letter).
The letters G, I, O, Q and U cannot be used.
The first digit cannot be a zero.
The last two letters must be different.

How many licence plates combinations are possible that satisfy all these conditions?

Solution

Only 21 letters are available to pick from, so there are $21^2$ possible letter combinations for A and B; and also there are $21^2 - 21$ possible combinations for C and D (subtracting the 21 invalid outcomes where the same letter is picked for C and D). To decide the digits, there are 9 choices for the first digit and 10 each for the other three digits. Thus there are a total of $21^2 \cdot (21^2 - 21) \cdot (9 \cdot 10^3)$ possible licence plate combinations.

4.

How many arrangements of the word PANINI

end with the letter P?
start with three vowels?
have all letters in alphabetical order?
have all vowels in alphabetical order (but not necessarily beside each other)?

Solution

b. The rearrangement should start A, I, and I, in some order, and end with P, N, and N in some order. These two decisions are independent of each other, so using Principle 2.1.9 and Proposition 2.2.10 we count a total of

\begin{equation*} \dfrac{3!}{2!} \times \dfrac{3!}{2!} = 9 \end{equation*}

rearrangements. (Try listing them all!)

5.

Consider the following quote:

“You can't spell awesome without me.”
―Taylor Swift ft. Brendon Urie (2019)

How many arrangements of the word AWESOME do not have the string ME?

Answer

$\displaystyle\frac{7!}{2!} - 6!\text{.}$

6. Fall 2022 Final Exam.

Count the number of arrangements of the word WANDERER where:

the letter W appears somewhere in between the two R's (not necessarily all beside each other); and
the string READ does not appear.

Hint

As with most combinatorial counting problems, there's more than one way to solve this; one approach is to consider the proportion of all arrangements that satisfies the first condition.

Answer

$\displaystyle\frac{1}{3}\left(\dfrac{8!}{2!\ 2!} - 5!\right)\text{.}$

7.

Write your own problem where the answer is $\displaystyle\binom{7}{2}\text{.}$ Be as creative as you can!

8.

Determine the coefficient of the term $x^3y^2$ in each product:

$\displaystyle (x+y)^5$
$\displaystyle (3x+2y)^5$
$\displaystyle (2x-y)^5$
$\displaystyle (7x + 7y)^5$

Solution

In this case $n=5, k=2\text{,}$ applying Theorem 2.3.5, the coefficient of $x^3y^2$ is ${{5}\choose{2}} = \frac{5!}{2!(5-2)!}=10\text{.}$
In this case $n=5, k=2\text{,}$ applying Theorem 2.3.5 again, the coefficient of $x^3y^2$ is ${{5}\choose{2}}3^3\cdot 2^2\text{.}$
The coefficient is ${{5}\choose{2}}2^{3}\cdot (-1)^{2} = 80\text{.}$
The coefficient is ${{5}\choose{2}}7^3\cdot7^2=168070\text{.}$

9. Fall 2022 Term Test.

Determine the coefficient of $\dfrac{a^5}{b^4}$ in the expansion of $\left(\dfrac{a}{2} - \dfrac{3}{b^2}\right)^7\text{.}$

Answer

$\displaystyle\binom{7}{5}\dfrac{(-3)^2}{2^5}\text{.}$

10.

Given a standard deck of cards (see Example 2.2.17), a straight is a hand of five different ranks in consecutive order. For example:

4$\diamondsuit$ 5$\heartsuit$ 6$\clubsuit$ 7$\clubsuit$ 8$\diamondsuit\text{.}$

Assume that straights can start with an ace (A-2-3-4-5) or 10 (10-J-Q-K-A) or any other numbered card, but not with any face card (J, Q, or K). How many straights can be formed?

Solution

The operation of forming a straight can be broken down into the following operations:

Pick a first card: there are 10 choices (A to 10).
There is only one way to continue picking ranks. (If we start with a 6, then the next four cards must be 7, 8, 9, and 10.)
Now we pick a suit for each of the cards we picked. There are four choices for each of the five cards, or a total of $4^5$ suit combinations.

Hence using Principle 2.1.9, we can form a total of $10 \cdot 4^5$ straights from a standard deck.

11.

A flush is a hand of five cards, all of the same suit. For example, the five-card hand

4$\spadesuit$ 5$\spadesuit$ 8$\spadesuit$ J$\spadesuit$ K$\spadesuit$

is a flush.

How many flushes can be formed?
How many flushes are also straights? (This hand is called a straight flush.)

Hint

First pick a suit, then pick cards from that suit.

Answer

a. $\displaystyle 4 \cdot \binom{13}{5}\text{,}$ b. $\displaystyle 4 \cdot 10 = 40\text{.}$

12.

A full house is a five-card hand with three cards of the same rank, plus two other cards of the same rank. For example, the five-card hand

7$\heartsuit$ 7$\diamondsuit$ 7$\clubsuit$ J$\heartsuit$ J$\spadesuit$

is a full house.

How many five-card hands are full houses?

Answer

$\displaystyle \binom{13}{1}\binom{4}{3}\binom{12}{1}\binom{4}{2}$ or $\displaystyle {}_{13}P_{2}\binom{4}{3}\binom{4}{2}\text{.}$

13.

How many ways are there to draw a three-card hand from a standard deck of cards such that:

all of them are face cards (J, Q, K)?
there are at least two numbered cards? (numbered cards are 2 to 10)
there are at least two numbered cards, and exactly two red cards?

Solution

b. The set of three-card hands that have at least two numbered cards can be partitioned into two disjoint sets: those that have exactly two numbered cards, and those that have exactly three numbered cards. Let's call these sets $A$ and $B\text{;}$ by Principle 2.1.7, the desired quantity is $|A| + |B|\text{.}$

The hands in $|A|$ can be counted by first selecting two numbered cards. There are 36 of them (nine ranks and four suits each) so this step has $\binom{36}{2}$ possibilities. Then, we pick the third non-numbered card from 16 options (A, J, Q, K; four suits each). Hence by Principle 2.1.9 $|A| = \binom{36}{2} \cdot \binom{16}{1}\text{.}$

Also, there are $|B| = \binom{36}{3}$ ways to pick three numbered cards. Hence the total is $\binom{36}{2} \cdot \binom{16}{1} + \binom{36}{3}\text{.}$

14.

From a standard deck of cards, count the number of six-card hands that contain at most three suits.

For example, the hand 4$\clubsuit$ 5$\clubsuit$ 8$\diamondsuit$ J$\diamondsuit$ K$\diamondsuit$ 9$\heartsuit$ is a valid hand, while the hand 4$\clubsuit$ 5$\clubsuit$ 8$\diamondsuit$ J$\diamondsuit$ 5$\spadesuit$ 9$\heartsuit$ is invalid since it does not contain at most three suits.

Answer

$\displaystyle \binom{52}{6} - \binom{4}{3}\binom{13}{1}^2\binom{13}{3} - \binom{4}{2}\binom{13}{1}^2\binom{13}{2}^2\text{.}$

15.

Count the number of rectangles that can be formed using the edges of a $3 \times 3$ grid with $(0,0)$ as one of its vertices. Here are some examples:

Solution

Knowing $(0,0)$ is a vertex, by locating the opposite vertex, a unique rectangle can be formed. So this question is equivalent to How many vertices can be chosen to form a rectangle with $(0,0)\text{?}$ We can simply count that there are 9 of them in total, since any vertex besides those of the form $(0,a)$ and $(b,0)$ can be chosen to be the opposite vertex.

16.

Generalize Exercise 2.7.15 to an $m \times n$ grid.

Answer

$mn$ rectangles.

17.

Count the number of rectangles that can be formed using the edges of an $m \times n$ grid (with no restrictions on the vertices). For example, if $m = 2$ and $n = 1\text{,}$ there are 3 possible rectangles:

Hint

Forming a rectangle on an $m \times n$ grid can be broken down into two steps: pick two vertical lines on the grid, and then pick two horizontal lines on the grid.

Answer

$\displaystyle\binom{m+1}{2}\binom{n+1}{2}$ rectangles.

18.

Count the number of lattice paths from $(0,0)$ to $(5,4)$ that:

Pass through the point $(2,2)\text{.}$
Avoid the point $(3,3)\text{.}$
Pass through the point $(2,2)$ and avoid the point (3,3).

Answer

a. $\displaystyle\binom{4}{2}\binom{5}{2}\text{;}$ b. $\displaystyle\binom{9}{5} - \binom{6}{3}\binom{3}{1}\text{;}$ c. $\displaystyle\binom{4}{2}\left(\binom{5}{2} - \binom{2}{1}\binom{3}{1})\text{.}$

19. Winter 2021 Term Test.

Define a sequence of digits to be triangular if the digits first form a nondecreasing sequence, then a nonincreasing sequence, so that the largest digit(s) is/are in between both subsequences. In other words, a sequence $a_1,a_2,\ldots,a_n$ is triangular if

\begin{equation*} a_1 \leq a_2 \leq \cdots \leq a_{k-1} \leq a_k \geq a_{k+1} \geq \cdots \geq a_{n-1} \geq a_n \end{equation*}

for some $1 \leq k \leq n\text{.}$ For example, $0114765320$ is triangular, while $0012431576$ is not.

Count the number of triangular rearrangements of your student number.

Hint

Theorem 2.4.5 with two bins.

20.

Count the number of ways to distribute 30 identical balls into 9 different boxes so that each box is nonempty.

Hint

Similar to Checkpoint 2.4.7.

21. Fall 2019 Term Test.

How many arrangements of the word ONTARIO:

do not have any two vowels beside each other?
have all vowels in alphabetical order?

Solution

(a). If no vowels can be beside each other, then the arrangement must have the pattern vowel-consonant-vowel-consonant-vowel-consonant-vowel. Hence to create an arrangement, we just need to:

Step 1: Arrange vowels A, I, O, O ($4!/2!$ ways)
Step 2: Arrange consonants N, T, R ($3!$ ways)

where these two steps are performed independently of each other. Hence there are $\dfrac{4!}{2!} \cdot 3!$ arrangements that satisfy the given condition.

(b). The vowels have to be in the order AIOO from left to right, and this fixes the ordering of the vowels. Hence to create an arrangement, we need to perform the following steps:

Step 1: Arrange consonants ($3!$ ways)
Step 2: Insert the three consonants among the vowels—since consonant order has been fixed in the previous step, this is equivalent to distributing 3 indistinguishable balls into 5 distinguishable bins corresponding to the five places in

_ A _ I _ O _ O _

There are $\binom{7}{3}$ ways to do this by Theorem 2.4.5.

Hence there are $3! \cdot \displaystyle\binom{7}{3}$ such arrangements.

Note: there are other (even simpler) solutions. Can you solve (b) in as many different ways as you can?

22.

Count the number of ways $2n$ people can be grouped into pairs.

For example, when $n = 2$ and there are four people A, B, C, and D, then there are three ways to pair them up: AB/CD, AC/BD, AD/BC.

Hint

Look at small cases first ($n = 2, 3, 4$) then try generalizing.

Answer

$\displaystyle\frac{\binom{2n}{2}\binom{2n-2}{2}\cdots\binom{4}{2}\binom{2}{2}}{n! \cdot 2^n} = \frac{(2n)!}{(2!)^n}\cdot\frac{1}{n!}\text{.}$

Find the number of integer solutions to each system:

23.

$x_1 + x_2 + x_3 = 30\text{,}$ $x_1, x_2, x_3 \geq 0\text{.}$

Solution

Theorem 2.4.5 gives ${{3+30-1}\choose{30}} = \binom{32}{30}\text{.}$

24.

$x_1 + x_2 + x_3 + x_4 = 2020\text{,}$ $x_1 \geq 30\text{,}$ $x_2 \geq 40\text{,}$ $x_3 \geq 50\text{,}$ $x_4 \geq 100$

Answer

$\displaystyle\binom{1803}{1800}\text{.}$

25.

$x_1 + x_2 + x_3 + x_4 = 2020\text{,}$ $x_1 \geq 300\text{,}$ $x_2 \geq 400\text{,}$ $x_3 \geq 500\text{,}$ $x_4 \geq 1000$

Solution

We first try simplifying the question by making the substitution $y_i = x_i - c_i$ where $x_i \geq c_i$ is given. We get

\begin{equation*} y_1+y_2+y_3+y_4 = 2020-300-400-500-1000 = -180 \lt 0\text{.} \end{equation*}

Therefore there are no solutions.

26.

$x_1 + x_2 + x_3 = 12\text{,}$ $3 \leq x_1 \leq 5\text{,}$ $1 \leq x_2\text{,}$ $1 \leq x_3 \leq 7$

27.

Find the number of integer solutions to

\begin{equation*} x_1 + x_2 - x_3 = -4 \end{equation*}

such that $x_1, x_2, x_3 \geq 0$ and $x_3 \leq 10\text{.}$

Hint

Let $y_3 = 10 - x_3\text{.}$

28.

Find the number of nonnegative integer solutions to $x_1 + x_2 + \cdots + x_k \leq n\text{.}$

Hint

Transform the inequality into an equation by adding another variable $x_{k+1}\text{.}$

29.

Prove the identity

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

by counting the number of subsets of size $n$ of the set $\{a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n\}\text{.}$

Solution

The right-hand-side is exactly the number of $n$-element subsets of the given set $\{a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n\}\text{.}$

We need to show that the left-hand side counts the same collection of objects. Since there is a sum from $k = 0$ to $k = n\text{,}$ let's think about possible cases.

The set $\{a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n\}$ has two types of elements: $a_i$'s and $b_i$'s. So let's take cases on how many of the $a_i$'s we pick when forming an $n$-element subset.

Suppose that we pick $k$ of the $a_i$'s. This means we need to take $n-k$ of the $b_i$'s to create an $n$-subset. Or equivalently, throw away $k$ of the $b_i$'s and use whatever is left. By the product rule we can count this by multiplying $\displaystyle\binom{n}{k}\binom{n}{k}\text{.}$

For example, to include 3 of the $a_i$'s in our subset, we can pick them in $\displaystyle\binom{n}{3}$ ways. Then we need to exclude 3 of the $b_i$'s to end up with $n-3$ $b_i$ elements to include in our subset and make it have $n$ elements. There are $\displaystyle\binom{n}{3}\binom{n}{3}$ ways to do this.

It is a partition of the collection of all $n$-subsets to divide them into cases by how many of the $a_i$'s are picked, from $k = 0$ to $k=n\text{.}$ Hence the sum rule gives the left-hand side:

\begin{equation*} \binom{n}{0}\binom{n}{0} + \binom{n}{1}\binom{n}{1} + \cdots + \binom{n}{n}\binom{n}{n} = \sum_{k=0}^n \binom{n}{k}^2\text{.} \end{equation*}

Therefore the equation

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

holds.

Prove the following identities using combinatorial arguments. Clearly explain which sets or objects you are counting in two ways.

30.

$\displaystyle\sum_{i=1}^n (i-1) = \binom{n}{2}$

31.

$\displaystyle b^3 = 6\binom{b}{3} + 6\binom{b}{2} + b$

Solution

Let $S$ be the number of ordered triples of $\{1,2,\ldots,b\}\text{.}$ Note that $|S| = b^3$ by the Product Rule, since there are $b$ choices per position, and elements can be repeated.

Now define the following sets:

$A_1 = $ the number of ordered triples that consist of only one element.
$A_2 = $ the number of ordered triples that consist of two distinct elements.
$A_3 = $ the number of ordered triples that consist of three distinct elements.

Then by the Sum Rule, $|S| = |A_3| + |A_2| + |A_1|\text{.}$

To form an ordered triple with all three elements distinct, we first select three elements from $\{1,2,\ldots,b\}$ (in $\binom{b}{3}$ ways), then generate all permutations (there are $3! = 6$ permutations). Hence

\begin{equation*} |A_3| = 6\binom{b}{3}\text{.} \end{equation*}

To form an ordered triple with two distinct elements,

We first select the two elements (in $\binom{b}{2}$ ways)—say we picked 1 and 2;
We pick one of the elements to repeat (there are 2 choices)—say 1;
We count all permutations (there are 3 spots to choose from to place the non-repeated element)—(1,1,2), (1,2,1), and (2,1,1) in our example.

Hence

\begin{equation*} |A_2| = 6\binom{b}{2}\text{.} \end{equation*}

Finally,

\begin{equation*} |A_1| = b \end{equation*}

since there are $b$ ordered triples of the form $(i,i,i)$ for $i = 1,2,\ldots,b\text{.}$

Thus the number of ordered triples $|S|$ that can be formed from the set $\{1,2,\ldots,b\}$ is

\begin{equation*} b^3 = 6\binom{b}{3} + 6\binom{b}{2} + b\text{.} \end{equation*}

32. Winter 2021 Term Test.

$\displaystyle \sum_{k=0}^n\sum_{m=0}^{n-k} \binom{n}{k} \binom{n-k}{m} = 3^n $

33.

$\displaystyle \binom{k+7}{7} = \binom{k+4}{4} \binom{2}{2} + \binom{k+3}{4}\binom{3}{2} + \cdots + \binom{4}{4}\binom{k+2}{2} $

Hint

Count the number of $7$-element subsets of $\{1,2,\ldots,k+7\}\text{.}$

34. Winter 2023 Term Test.

Let $a, b, c, n \in \mathbb{N}$ with $n \leq a, b, c\text{.}$ Write a combinatorial proof of the identity

\begin{equation*} \binom{a+b+c}{n} = \sum_{k=0}^n \sum_{r=0}^{n-k} \binom{a}{k}\binom{b}{r}\binom{c}{n-k-r}\text{.} \end{equation*}

Hint

Consider the set $S = \{t_1,t_2,\ldots,t_a,u_1,u_2,\ldots,u_b,v_1,v_2,\ldots,v_c\}\text{,}$ then count the number of $n$-element subsets of $S\text{.}$