Combinatorial Analysis

Show that, for n > 0,

$\sum _{i=0}^n{(-1)}^i\left(\begin{array}{c}n\\ i\end{array}\right)=0$

Hint: Use the binomial theorem.

From a set of $n$ people, a committee of size $j$ is to be chosen, and from this committee, a subcommittee of size $i$, $i\le j$, is also to be chosen.

(a) Derive a combinatorial identity by computing, in two ways, the number of possible choices of the committee and subcommittee—first by supposing that the committee is chosen first and then the subcommittee is chosen, and second

by supposing that the subcommittee is chosen first and then the remaining members of the committee are chosen.

(b) Use part (a) to prove the following combinatorial identity:  $\sum _{j=i}^n\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)=\left(\begin{array}{c}n\\ i\end{array}\right)2^{n-i}; i\le n$

(c) Use part (a) and Theoretical Exercise 13 to show that:  $\sum _{j=i}^n\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right){\left(-1\right)}^{n-j}=0; i<n$

Let $H_k\left(n\right)$ be the number of vectors $x_1, . . . , x_k$ for which each $x_i$ is a positive integer satisfying $1\le x_i\le n$ and $x_1 \le x_2\le , \dots , \le x_k.$

(a)Without any computations, argue that 

$$\begin{gathered} H_1\left(n\right)=n \\ {H}_k\left(n\right)=\sum _{j=1}^n{H}_{k-1}\left(j\right) k>1 \end{gathered}$$

Hint: How many vectors are there in which $x_k = j$?

(b) Use the preceding recursion to compute $H_3\left(5\right)$.

Hint: First compute $H_2\left(n\right) for n = 1, 2, 3, 4, 5$.

Consider a tournament of $n$ contestants in which the outcome is an ordering of these contestants, with ties allowed. That is, the outcome partitions the players into groups, with the first group consisting of the players who tied for first place, the next group being those who tied for the next-best position, and so on. Let $N\left(n\right)$ denote the number of different possible outcomes. For instance, $N\left(2\right) = 3$, since, in a tournament with $2$ contestants, player $1$ could be uniquely first, player $2$ could be uniquely first, or they could tie for first.

(a) List all the possible outcomes when $n=3$.

(b) With $N\left(0\right)$ defined to equal $1$, argue without any computations, that $N\left(n\right)=\sum _{i=1}^n\left(\begin{array}{c}n\\ i\end{array}\right)N\left(n-i\right)$

Hint: How many outcomes are there in which $i$ players tie for last place?

(c) Show that the formula of part (b) is equivalent to the following: 

$N\left(n\right)=\sum _{i=1}^{n-1}\left(\begin{array}{c}n\\ i\end{array}\right)N\left(i\right)$

(d) Use the recursion to find N(3) and N(4).

Present a combinatorial explanation of why

$\left(\begin{array}{c}n\\ r\end{array}\right)=\left(\begin{array}{c}n\\ r, n-r\end{array}\right)$

Argue that

$\left(\begin{array}{c}n\\ n_1, n_2, ........ , n_r\end{array}\right)=\left(\begin{array}{c}n-1\\ n_1-1, n_2, ........ , n_r\end{array}\right)+\left(\begin{array}{c}n-1\\ n_1, n_2-1, ........ , n_r\end{array}\right)+......+\left(\begin{array}{c}n-1\\ n_1, n_2, ........ , n_r-1\end{array}\right)$

Hint: Use an argument similar to the one used to establish Equation (4.1).

Prove the multinomial theorem.

In how many ways can $n$ identical balls be distributed into $r$ urns so that the $ith$ urn contains at least $m_i$ balls, for each $i = 1, . . . , r$? Assume that $n\ge \sum _{i=1}^r{m}_i$.

Argue that there are exactly $\left(\begin{array}{c}r\\ k\end{array}\right)\left(\begin{array}{c}n-1\\ n-r+k\end{array}\right)$ solutions of $x_1 + x_2 + · · · + x_r = n$ for which exactly $k$ of the $x_i$ are equal to $0$.

Consider a function $f (x_1, . . . , x_n)$ of $n$ variables. How many different partial derivatives of order $r$ does $f$ possess?

Determine the number of vectors $(x1, . . . , xn)$ such that each $x_i$ is a nonnegative integer and $\sum _{i=1}^n{x}_i\le k$

How many different linear arrangements are there of the letters A, B, C, D, E, F for which

(a) A and B are next to each other?

(b) A is before B?

(c) A is before B and B is before C?

(d) A is before B and C is before D?

(e) A and B are next to each other and C and D are also next to each other?

(f) E is not last in line?

If $4$ Americans, $3$ French people, and $3$ British people are to be seated in a row, how many seating arrangements are possible when people of the same nationality must sit next to each other?

A president, treasurer, and secretary, all different, are to be chosen from a club consisting of $10$ people. How many different choices of officers are possible if

(a) there are no restrictions?

(b) A and B will not serve together?

(c) C and D will serve together or not at all?

(d) E must be an officer?

(e) F will serve only if he is president?

A student is to answer $7$ out of $10$ questions in an examination. How many choices has she? How many if she must answer at least $3$ of the first $5$ questions?

In how many ways can a man divide $7$ gifts among his $3$ children if the eldest is to receive $3$ gifts and the others $2$ each?

How many different $7$-place license plates are possible when $3$ of the entries are letters and $4$ are digits? Assume that repetition of letters and numbers is allowed and that there is no restriction on where the letters or numbers can be placed.

Give a combinatorial explanation of the identity

$\left(\begin{array}{c}n\\ r\end{array}\right)=\left(\begin{array}{c}n\\ n-r\end{array}\right)$

Consider $n$-digit numbers where each digit is one of the $10$ integers $0, 1, . . . , 9$. How many such numbers are there for which

(a) no two consecutive digits are equal?

(b) $0$ appears as a digit a total of $i$ times, $i = 0, . . . , n$?

Consider three classes, each consisting of $n$ students. From this group of $3n$ students, a group of $3$ students is to be chosen.

(a) How many choices are possible?

(b) How many choices are there in which all $3$ students are in the same class?

(c) How many choices are there in which $2$ of the $3$ students are in the same class and the other student is in a different class?

(d) How many choices are there in which all $3$ students are in different classes?

(e) Using the results of parts (a) through (d), write a combinatorial identity.

How many $5$-digit numbers can be formed from the integers $1, 2, . . . , 9$ if no digit can appear more than twice? (For instance, $41434$ is not allowed.)

From $10$ married couples, we want to select a group of $6$ people that is not allowed to contain a married couple.

(a) How many choices are there?

(b) How many choices are there if the group must also consist of $3$ men and $3$ women?

A committee of $6$ people is to be chosen from a group consisting of $7$ men and $8$ women. If the committee must consist of at least $3$ women and at least $2$ men, how many different committees are possible?

An art collection on auction consisted of $4$ Dalis, $5$ van Goghs, and $6$ Picassos. At the auction were 5 art collectors. If a reporter noted only the number of Dalis, van Goghs, and Picassos acquired by each collector, how many different results could have been recorded if all of the works were sold?

Determine the number of vectors $(x_1, . . . , x_n)$ such that each $x_i$ is a positive integer and

$\sum _{i=1}^n{x}_i\le k$

where $k\ge n$.

A total of $n$ students are enrolled in a review course for the actuarial examination in probability. The posted

results of the examination will list the names of those who passed, in decreasing order of their scores. For instance, the posted result will be “Brown, Cho” if Brown and Cho are the only ones to pass, with Brown receiving the higher score. Assuming that all scores are distinct (no ties), how many posted results are possible?

How many subsets of size $4$ of the set $S=\left\{1,2,...,20\right\}$ contain at least one of the elements $1, 2, 3, 4, 5$?

Give an analytic verification of

$\left(\begin{array}{c}n\\ 2\end{array}\right)=\left(\begin{array}{c}k\\ 2\end{array}\right)+k(n-k)+\left(\begin{array}{c}n-k\\ 2\end{array}\right), 1\le k\le n$

Now, give a combinatorial argument for this identity.

In a certain community, there are $3$ families consisting of a single parent and $1$ child, $3$ families consisting of a single parent and $2$ children, $5$ families consisting of $2$ parents and a single child, $7$ families consisting of $2$ parents and $2$ children, and $6$ families consisting of $2$ parents and $3$ children. If a parent and child from the same family are to be chosen, how many possible choices are there?

If there are no restrictions on where the digits and letters are placed, how many $8$-place license plates consisting of $5$ letters and $3$ digits are possible if no repetitions of letters or digits are allowed? What if the $3$ digits must be consecutive?

Verify that the equality

$\sum _{x_1+....+x_r=n, x_i\ge 0} \frac{n!}{x_1!x_2!....x_r!}=r^n$

when $n = 3, r = 2$, and then show that it always valid. (The sum is over all vectors of $r$ nonnegative integer values whose sum is $n$.)

Hint: How many different n letter sequences can be formed from the first $r$ letters of the alphabet? How many of them use letter $i$ of the alphabet a total of $x_i$ times for each $i = 1, . . . , r$?