Chapter 1: Combinatorial Analysis

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).

From a group of $8$ women and $6$ men, a committee consisting of $3$ men and $3$ women is to be formed. How many

different committees are possible if

(a) $2$ of the men refuse to serve together?

(b) $2$ of the women refuse to serve together?

(c) $1$ man and $1$ woman refuse to serve together?

Prove the multinomial theorem.

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?

Two experiments are to be performed. The first can result in any one of m possible outcomes. If the first experiment results in outcome i, then the second experiment can result in any of ni possible outcomes, i = 1, 2, ..., m. What is the number of possible outcomes of the two experiments?

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?

How many outcome sequences are possible when a die is rolled four times, where we say, for instance, that the outcome is 3, 4, 3, 1 if the first roll landed on 3, the second on 4, the third on 3, and the fourth on 1?

Two experiments are to be performed. The first can result in any one of m possible outcomes. If the first experiment results in an outcome$i,$then the second experiment can result in any of$n_i$ the possible outcomes, i = 1, 2, ..., m. What is the number of possible outcomes of the two experiments?

A person has $8$friends, of whom $5$will be invited to a party.

(a) How many choices are there if $2$ of the friends are feuding and will not attend together?

(b) How many choices if $2$ of the friends will only attend together?

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$?