Combinatorial Analysis

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?

1. (a) How many different 7-place license plates are possible if the first 2 places are for letters and the other 5 for numbers? (b) Repeat part (a) under the assumption that no letter or number can be repeated in a single license plate 

 Twenty workers are to be assigned to 20 different jobs, one to each job. How many different assignments are possible 

John, Jim, Jay, and Jack have formed a band consisting of 4 instruments. If each of the boys can play all 4 instruments, how many different arrangements are possible? What if John and Jim can play all 4 instruments, but Jay and Jack can each play only piano and drums? 

 For years, telephone area codes in the United States and Canada consisted of a sequence of three digits. The first digit was an integer between 2 and 9, the second digit was either 0 or 1, and the third digit was any integer from 1 to 9. How many area codes were possible? How many area codes starting with a 4 were possible 

A well-known nursery rhyme starts as follows: “As I was going to St. Ives I met a man with 7 wives. Each wife had 7 sacks. Each sack had 7 cats. Each cat had 7 kittens...” How many kittens did the traveler meet 

?

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

A child has 12 blocks, of which 6 are black, 4 are red, 1 is white, and 1 is blue. If the child puts the blocks in a line, how many arrangements are possible ? 

How many different letter arrangements can be made from the letters (a) Fluke? (b) Propose? (c) Mississippi? (d) Arrange? 

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 one another? (e) there are 4 married couples and each couple must sit together? 

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? 

In how many ways can $3$novels, $2$mathematics books, and $1$chemistry book be arranged on a bookshelf if

(a) the books can be arranged in any order?

(b) the mathematics books must be together and the novels must be together?

(c) the novels must be together, but the other books can be arranged in any order?

(a) How many different 7-place license plates are possible if the first 2 places are for letters and the other 5 for numbers? (b) Repeat part (a) under the assumption that no letter or number can be repeated in a single license plate 

The game of bridge is played by $4$players, each of who is dealt $13$cards. How many bridge deals are possible?

The game of bridge is played by $4$players, each of whom is dealt $13$cards. How many bridge deals are possible?

If $12$people are to be divided into $3$committees of respective sizes $3,4,$and $5,$how many divisions are possible?

If $8$new teachers are to be divided among $4$schools, how many divisions are possible? What if each school must receive $2$teachers?

Ten weight lifters are competing in a team weight-lifting contest. The lifters $3$are from the United States,$4$ are from Russia, $2$are from China, and $1$are from Canada. If the scoring takes account of the countries that the lifters represent, but not their individual identities, how many different outcomes are possible from the point of view of scores? How many different outcomes correspond to results in which the United States has $1$competitors in the top three and $2$in the bottom three?

Expand${\left(x_1+2x_2+3x_3\right)}^4$.

Five separate awards (best scholarship, best leadership qualities, and so on) are to be presented to selected students

from a class of $30$. How many different outcomes are possible if

(a) a student can receive any number of awards?

(b) each student can receive at most $1$ award?

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?

A dance class consists of $22$ students, of which $10$ are women and 12 are men. If $5$ men and $5$ women are to be

chosen and then paired off, how many results are possible?

A student has to sell $2$ books from a collection of $6$ math, $7$ science, and $4$ economics books. How many choices are possible if

(a) both books are to be on the same subject?

(b) the books are to be on different subjects?

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

A committee of $7$, consisting of $2$ Republicans, $2$ Democrats, and $3$ Independents, is to be chosen from a group of $5$ Republicans, $6$ Democrats, and $4$ Independents. How many committees are possible?

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?

Consider the grid of points shown at the top of the next column. Suppose that, starting at the point labelled A, you can go one step up or one step to the right at each move. This procedure is continued until the point labelled B is reached. How many different paths from A to B are possible? Hint: Note that to reach B from A, you must take $4$ steps to the right and $3$ steps upward.

In Problem 21, how many different paths are there from A to B that go through the point circled in the following lattice?

A psychology laboratory conducting dream research contains $3$ rooms, with $2$ beds in each room. If $3$ sets of identical twins are to be assigned to these $6$ beds so that each set of twins sleeps in different beds in the same room, how many assignments are possible?

Expand ${(3x^2 + y)}^5$.

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? 

Delegates from $10$countries, including Russia, France, England, and the United States, are to be seated in a row. How many different seating arrangements are possible if the French and English delegates are to be seated next to each other and the Russian and U.S. delegates are not to be next to each other?

If $8$identical blackboards are to be divided among $4$schools, how many divisions are possible? How many of each school must receive at least $1$a blackboard?

An elevator starts at the basement with $8$people (not including the elevator operator) and discharges them all by the time it reaches the top floor, number$6$. In how many ways could the operator have perceived the people leaving the elevator if all people look alike to him? What if the $8$people consisted of $5$men and $3$women and the operator could tell a man from a woman?

We have$\backslash (20,000$ that must be invested among $4$possible opportunities. Each investment must be integral in units$\backslash )1000,$ and there are minimal investments that need to be made if one is to invest in these opportunities. The minimal investments are $\backslash (2000, \backslash )2000, \backslash (3000,$and$\backslash )4000$. How many different investment strategies are available if

$\left(a\right)$an investment must be made in each opportunity?

$\left(b\right)$ investments must be made in at least $3$of the $4$opportunities?

Suppose that $10$fish are caught at a lake that contains $5$distinct types of fish.

$\left(a\right)$How many different outcomes are possible, where an outcome specifies the numbers of caught fish of each of the $5$types?

$\left(b\right)$ How many outcomes are possible when$3$ the $10$fish caught are trout?

$\left(c\right)$ How many when at least $2$of the $10$are trout?

Prove the generalized version of the basic counting principle.

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?

In how many ways can$r$ objects be selected from a set of $n$objects if the order of selection is considered relevant?

There are$\left(\begin{array}{c}n\\ r\end{array}\right)$ different linear arrangements of $n$balls that $r$ are black and $n - r$ are white. Give a combinatorial explanation of this fact.

Determine the number of vectors $(x_1, ... , x_n),$such that each $x_i$is either $0$or$1$ and$\sum _{i=1}^n{x}_i\ge k$.

Determine the number of vectors$(x_1,...x_{n)}$  such that each $xi$ is either $0$ or $1$ and

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

How many vectors $x_1, . . . , x_k$ are there for which each $x_i$ is a positive integer such that $1 \le x_i\le n$ and  $x_1 < x_2 < · · · < x_k$?

Give an analytic proof of Equation (4.1).

Prove that: 

$\left(\begin{array}{c}n+m\\ r\end{array}\right)=\left(\begin{array}{c}n\\ 0\end{array}\right)\left(\begin{array}{c}m\\ r\end{array}\right)+\left(\begin{array}{c}n\\ 1\end{array}\right)\left(\begin{array}{c}m\\ r-1\end{array}\right)+..........+\left(\begin{array}{c}n\\ r\end{array}\right)\left(\begin{array}{c}m\\ 0\end{array}\right)$

Hint: Consider a group of $n$ men and $m$ women. How many groups of size $r$ are possible?

Use Theoretical Exercise 8 to prove that

$\left(\begin{array}{c}2n\\ n\end{array}\right)=\sum _{k=0}^n{\left(\begin{array}{c}n\\ k\end{array}\right)}^2$

From a group of $n$ people, suppose that we want to choose a committee of k, $k\le n$, one of whom is to be designated as chairperson.

(a) By focusing first on the choice of the committee and then on the choice of the chair, argue that there are $\left(\begin{array}{c}n\\ k\end{array}\right)k$ possible choices.

(b) By focusing first on the choice of the non-chair committee members and then on the choice of the chair, argue that there are $\left(\begin{array}{c}n\\ k-1\end{array}\right)\left(n-k+1\right)$ possible choices.

(c) By focusing first on the choice of the chair and then on the choice of the other committee members, argue that

there are $n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ possible choices.

(d) Conclude from parts (a), (b), and (c) that $k\left(\begin{array}{c}n\\ k\end{array}\right)=\left(n-k+1\right)\left(\begin{array}{c}n\\ k-1\end{array}\right)=n\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$.

(e) Use the factorial definition of $\left(\begin{array}{c}m\\ r\end{array}\right)$ to verify the identity in part (d).

The following identity is known as Fermat’s combinatorial identity:

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

Give a combinatorial argument (no computations are needed) to establish this identity.

Hint: Consider the set of numbers $1$ through $n$. How many subsets of size $k$ have $i$ as their highest numbered member?

Consider the following combinatorial identity:

$\sum _{k=1}^{n}k\left(\begin{array}{c}n\\ k\end{array}\right)=n·2^{n-1}$

(a) Present a combinatorial argument for this identity by considering a set of $n$ people and determining, in two ways,

the number of possible selections of a committee of any size and a chairperson for the committee.

Hint:

(i) How many possible selections are there of a committee of size $k$ and its chairperson?

(ii) How many possible selections are there of a chairperson and the other committee members?

(b) Verify the following identity for $n = 1, 2, 3, 4, 5$:

$\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^2=2^{n-2}n(n+1)$

For a combinatorial proof of the preceding, consider a set of n people and argue that both sides of the identity represent

the number of different selections of a committee, its chairperson, and its secretary (possibly the same as the chairperson).

Hint:

(i) How many different selections result in the committee containing exactly $k$ people?

(ii) How many different selections are there in which the chairperson and the secretary are the same?

(answer: $n{2}^{n-1}$.)

(iii) How many different selections result in the chairperson and the secretary being different?

(c) Now argue that

$\sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)k^3=2^{n-3}{n}^2(n+3)$