91Ó°ÊÓ

(a) In how many ways can 3 boys and 3 girls sit in a row? (b) In how many ways can 3 boys and 3 girls sit in a row if the boys and the girls are each to sit together? (c) In how many ways if only the boys must sit together? (d) In how "many ways if no two people of the same sex are allowed to sit together?

Consider \(n\)-digit numbers where each digit is one of the 10 integers 0 , \(1, \ldots, 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, \ldots, n\) ?

Consider three classes, each consisting of \(n\) students. From this group of \(3 n\) 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.

In how many ways can 8 people be seated in a row if (a) there are no restrictions on the seating arrangement; (b) persons \(A\) and \(B\) must sit next to each other; (c) there are 4 men and 4 women and no 2 men or 2 women can sit next to each other; (d) there are 5 men and they must sit next to each other; (e) there are 4 married couples and each couple must sit together?

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 works were sold?

The following identity is known as Fermat's combinatorial identity. $$ \text { - }\left(\begin{array}{l} n \\ k \end{array}\right)=\sum_{i=k}^{n}\left(\begin{array}{l} i-1 \\ k-1 \end{array}\right) \quad n \geq k $$ Give a combinatorial argument (no computations are needed) to establish this identity. HINI: Consider the set of numbers 1 through \(n\). How many subsets of size \(k\) have \(i\) as their highest-numbered member?

Consider a group of 20 people. If everyone shakes hands with everyone else, how many handshakes take place?

How many 5 -card poker hands are there?

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 \leq 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, 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}{l} n \\ j \end{array}\right)\left(\begin{array}{l} j \\ i \end{array}\right)=\left(\begin{array}{l} n \\ i \end{array}\right) 2^{n-i} \quad i \leq n $$ (c) Use part (a) and Theoretical Exercise 13 to show that $$ \sum_{j=i}^{n}\left(\begin{array}{l} n \\ j \end{array}\right)\left(\begin{array}{l} j \\ i \end{array}\right)(-1)^{n-j}=0 \quad i \leq n $$

A total of 7 different gifts are to be distributed among 10 children. How many distinct results are possible if no child is to receive more than one gift?