Counting Arguments

Recall that the quantity $\displaystyle {n \choose r}$ was defined inductively using Pascal’s identity

$\displaystyle {n \choose r} = {n-1 \choose r} + {n-1 \choose r-1}.$

and denotes the number of $r$ -subsets of a set of size $n$ (i.e. $n$ distinct objects).

Problem 1. Prove that $\displaystyle {n \choose r} = {n \choose n-r}$ .

(Click for Solution)

Solution. Fix a set of $n$ distinct objects. There are $\displaystyle {n \choose r}$ possible $r$ -subsets of items that we can remove from that set. Therefore, every $(n-r)$ -subset of items left behind is obtained by exactly one corresponding $r$ -subset of items removed. Therefore, the number of $(n-r)$ -subsets (left behind) equals the number of $r$ -subsets (removed), yielding

$\displaystyle {n \choose r} = {n \choose n-r}.$

Problem 2. Prove that $\displaystyle {n \choose m} {m \choose r} = {n \choose r} {n-r \choose m-r}$ .

(Click for Solution)

Solution. We can interpret the identity as counting the number of $m$ -committeees out of $n$ persons, and among the $m$ persons, we choose $r$ persons in a “core team”. This is the quantity counted by the left-hand side:

$\displaystyle {n \choose m} {m \choose r}.$

On the right-hand side, we count the same quantity differently: first choose the $r$ “core team” members, then choose the remaining $(m-r)$ members out of the remaining $(n-r)$ persons:

$\displaystyle {n \choose r} {n-r \choose m-r}.$

Since both types of counting give the same total,

$\displaystyle {n \choose m} {m \choose r} = {n \choose r} {n-r \choose m-r}.$

Problem 3. Prove that $\displaystyle {n \choose r} = \frac nr {n-1 \choose r-1}$ .

(Click for Solution)

Solution. Replacing $(n,m,r)$ with $(n,r,1)$ in Problem 2,

$\displaystyle r \cdot {n \choose r} = {n \choose r} {r \choose 1} = {n \choose 1} {n-1 \choose r-1} = n \cdot {n-1 \choose r-1}.$

Problem 4. Prove that $\displaystyle {n \choose r} = \frac {n}{n-r} {n-1 \choose r}$ .

(Click for Solution)

Solution. Using Problems 1 and 3,

$\displaystyle {n \choose r} = {n \choose n-r} = \frac{n}{n-r} \cdot {n-1 \choose n-r-1} = \frac{n}{n-r} \cdot {n-1 \choose r}.$

Problem 5. Prove that $\displaystyle {n \choose r} = \frac {n-r+1}r {n \choose r-1}$ .

(Click for Solution)

Solution. Replacing $(n,m,r)$ with $(n,r,r-1)$ in Problem 2,

$\begin{aligned} r \cdot {n \choose r} ={n \choose r} {r \choose r-1} &= {n \choose r-1} {n-(r-1) \choose r-(r-1)} \\ &= (n-r+1) \cdot {n \choose r-1}. \end{aligned}$

Problem 6. For any $n \in \mathbb N^+, r \in \mathbb N_0$ , count the number of $n$ -tuples $(x_1,\dots,x_n) \in \mathbb N_0^n$ such that

$\displaystyle \sum_{k=1}^n x_k = r.$

(Click for Solution)

Solution. Consider a row of $r$ stars and $(n-1)$ bars. Let $x_1$ denote the number of stars before the 1st bar, $x_2$ denote the number of stars after the 1st bar and before the 2nd bar, and so on and so forth. Each arrangement of the $r$ stars and $(n-1)$ bars then corresponds to each desired $n$ -tuple. Thus, the required number is the number of places to place the bars:

$\displaystyle {r + (n-1) \choose (n-1)} = {n+r-1 \choose n-1} ={n+r-1 \choose r}.$

Problem 7. For any $n \in \mathbb N^+, p \in \mathbb N_0$ , suppose $p$ is prime. Count the number of $(2n)$ -tuples $(x_1,\dots,x_n,y_1,\dots, y_n) \in \mathbb N_0^n$ such that

$\displaystyle \left( \sum_{i=1}^n x_i \right) \cdot \left( \sum_{j=1}^n y_j \right) = p.$

(Click for Solution)

Solution. Since $p$ is prime, we require one of the sums to equal $1$ , and the other to equal $p$ . If the $x_i$ terms sum to $1$ , then there are a total of $n$ possible options of $(x_1,\dots, x_n)$ . By Problem 6, there are a total of