we give it a symbol, namely n!, which is read “n factorial”. Thus, for

example, 3! = 3 · 2 · 1 = 6, 4! = 4 · 3 · 2 · 1 = 24, etc. For reasons

which will be clear later, we de¬ne 0! = 1. Thus we can say there are

n! di¬erent permutations of n distinct objects.

Example 3.7 In the game of Scrabble, suppose there are seven let-

tered blocks from which we try to form a seven-letter word. If the

seven letters are all di¬erent, we must consider 7! = 5040 di¬erent

™¦

orders.

Example 3.8 A quarterback has a sequence of ten plays. Suppose his

or her coach instructs him or her to run through the ten-play sequence

without repetition. How much freedom is left to the quarterback? He

or she may choose any one of 10! = 3, 628, 800 orders in which to call

™¦

the plays.

46 CHAPTER 3. PARTITIONS AND COUNTING

Example 3.9 How many ways can n people be seated around a cir-

cular table? When this question is asked, it is usually understood that

two arrangements are di¬erent only if at least one person has a di¬erent

person on the right in the two arrangements. Consider then one person

in a ¬xed position. There are (n ’ 1)! ways in which the other people

may be seated. We have now counted all the arrangements we wish to

™¦

consider di¬erent.

A general principle. There are many counting problems for

which it is not possible to give a simple formula for the number of

possible cases. In many of these the only way to ¬nd the number

of cases is to draw a tree and count them (see Exercise 4). In some

problems, the following general principle is useful.

If one thing can be done in exactly r di¬erent ways, for each of

these a second thing can be done in exactly s di¬erent ways, for each

of the ¬rst two, a third can be done in exactly t ways, etc., then the

sequence of things can be done in the product of the numbers of ways

in which the individual things can be done, i.e., r · s · t ways.

The validity of the above general principle can be established by

thinking of a tree representing all the ways in which the sequence of

things can be done. There would be r branches from the starting posi-

tion. From the ends of each of these r branches there would be s new

branches, and from each of these t new branches, etc. The number of

paths through the tree would be given by the product r · s · t.

Example 3.10 The number of permutations of n distinct objects is

a special case of this principle. If we were to list all the possible per-

mutations, there would be n possibilities for the ¬rst, for each of these

n ’ 1 for the second, etc., until we came to the last object, and for

which there is only one possibility. Thus there are n(n ’ 1) . . . 1 = n!

™¦

possibilities in all.

Example 3.11 If there are three roads from city x to city y and two

roads from city y to city z, then there are 3 · 2 = 6 ways that a person

™¦

can drive from city x to city z passing through city y.

Example 3.12 Suppose there are n applicants for a certain job. Three

interviewers are asked independently to rank the applicants according

to their suitability for the job. It is decided that an applicant will be

hired if he or she is ranked ¬rst by at least two of the three interviewers.

47

3.3. PERMUTATIONS

What fraction of the possible reports would lead to the acceptance of

some candidate? We shall solve this problem by ¬nding the fraction

of the reports which do not lead to an acceptance and subtract this

answer from 1. Frequently, an indirect attack of this kind on a problem

is easier than the direct approach. The total number of reports possible

is (n!)3 since each interviewer can rank the men in n! di¬erent ways.

If a particular report does not lead to the acceptance of a candidate,

it must be true that each interviewer has put a di¬erent applicant in

¬rst place. This can be done in n(n ’ 1)(n ’ 2) di¬erent ways by our

general principle. For each possible ¬rst choices, there are [(n ’ 1)!]3

ways in which the remaining men can be ranked by the interviewers.

Thus the number of reports which do not lead to acceptance is n(n ’

1)(n ’ 2)[(n ’ 1)!]3 . Dividing this number by (n!)3 we obtain

(n ’ 1)(n ’ 2)

n2

as the fraction of reports which fail to accept a candidate. The fraction

which leads to acceptance is found by subtracting this fraction from 1

which gives

3n ’ 2

n2

7

For the case of three applicants, we see that 9 of the possibilities lead to

acceptance. Here the procedure might be criticized on the grounds that

even if the interviewers are completely ine¬ective and are essentially

guessing there is a good chance that a candidate will be accepted on

the basis of the reports. For n equal to ten, the fraction of acceptances

is only .28, so that it is possible to attach more signi¬cance to the

™¦

interviewers ratings, if they reach a decision.

Exercises

1. In how many ways can ¬ve people be lined up in a row for a group

picture? In how many ways if it is desired to have three in the

front row and two in the back row?

[Ans. 120;120.]

2. Assuming that a baseball team is determined by the players and

the position each is playing, how many teams can be made from

13 players if

48 CHAPTER 3. PARTITIONS AND COUNTING

(a) Each player can play any position?

(b) Two of the players can be used only as pitchers?

3. Grades of A, B, C, D, or F are assigned to a class of ¬ve students.

(a) How many ways may this be done, if no two students receive

the same grade?

[Ans. 120.]

(b) Two of the students are named Smith and Jones. How many

ways can grades be assigned if no two students receive the

same grade and Smith must receive a higher grade than

Jones?

[Ans. 60.]

(c) How many ways may grades be assigned if only grades of A

and F are assigned?

[Ans. 32.]

4. A certain club wishes to admit seven new members, four of whom

are Republicans and three of whom are Democrats. Suppose the

club wishes to admit them one at a time and in such a way that

there are always more Republicans among the new members than

there are Democrats. Draw a tree to represent all possible ways

in which new members can be admitted, distinguishing members

by their party only.

5. There are three di¬erent routes connecting city A to city B. How

many ways can a round trip be made from A to B and back?

How many ways if it is desired to take a di¬erent route on the

way back?

[Ans. 9;6.]

6. How many di¬erent ways can a ten-question multiple-choice exam

be answered if each question has three possibilities, a, b, and c?

How many if no two consecutive answers are the same?

7. Modify Example 3.12 so that, to be accepted, an applicant must

be ¬rst in two of the interviewers™ ratings and must be either ¬rst

or second in the third interviewers™ rating. What fraction of the

possible reports lead to acceptance in the case of three applicants?

In the case of n?

49

3.3. PERMUTATIONS

[Ans. 4 ; n2 .]

4

9

8. A town has 1240 registered Republicans. It is desired to contact

each of these by phone to announce a meeting. A committee of

r people devise a method of phoning s people each and asking

each of these to call t new people. If the method is such that no

person is called twice,

(a) How many people know about the meeting after the phon-

ing?

(b) If the committee has 40 members and it is desired that all

1240 Republicans be informed of the meeting and that s and

t should be the same, what should they be?

9. In the Scrabble example (Example 3.7), suppose the letters are

Q, Q, U, F, F, F, A. How many distinguishable arrangements are

there for these seven letters?

[Ans. 420.]

10. How many di¬erent necklaces can be made

(a) If seven di¬erent sized beads are available?

[Ans. 360.]

(b) If six of the beads are the same size and one is larger?

[Ans. 1.]

(c) If the beads are of two sizes, ¬ve of the smaller size and two

of the larger size?

[Ans. 3.]

11. Prove that two people in Columbus, Ohio, have the same initials.

12. Find the number of distinguishable arrangements for each of the

following collections of ¬ve symbols. (The same letters with dif-

ferent subscripts indicate distinguishable objects.)

(a) A1 , A2 , B1 , B2 , B3 .

[Ans. 120.]

50 CHAPTER 3. PARTITIONS AND COUNTING

(b) A, A, B1 , B2 , B3 .

[Ans. 60.]

(c) A, A, B, B, B.

13. Show that the number of distinguishable arrangements possible

for n objects, n1 of type 1, n2 of type 2, etc., for r di¬erent types

is

n!

.

n1 !n2 ! · · · nr !

Supplementary exercises.

14. (a) How many four digit numbers can be formed from the digits

1, 2, 3, 4, using each digit only once?

(b) How many of these numbers are less than 3000?

[Ans. 12.]

15. How many license plates can be made if they are to contain ¬ve

symbols, the ¬rst two being letters and the last three digits?

16. How many signals can a ship show if it has seven ¬‚ags and a signal

consists of ¬ve ¬‚ags hoisted vertically on a rope?

[Ans. 2520.]

17. We must arrange three green, two red, and four blue books on a

single shelf.

(a) In how many ways can this be done if there are no restric-

tions?

(b) In how many ways if books of the same color must be grouped

together?

(c) In how many ways if, in addition to the restriction in 17b,

the red books must be to the left of the blue books?

(d) In how many ways if, in addition to the restrictions in 17b

and 17c, the red and blue books must not be next to each

other?

[Ans. 288.]

51

3.4. COUNTING PARTITIONS

18. A youngster has three shades of nail polish with which to paint

his or her ¬ngernails. In how many ways can he or she do this

(each nail being one solid color) if there are no more than two

di¬erent shades on each hand?

[Ans. 8649.]

3.4 Counting partitions

Up to now we have not had occasion to consider the partitions [{1, 2}, {3, 4}]

and [{3, 4}, {1, 2}] of the integers from 1 to 4 as being di¬erent parti-

tions. Here it will be convenient to do so, and to indicate this distinc-

tion we shall use the term ordered partition. An ordered partition with

r cells is a partition with r cells (some of which may be empty), with

a particular order speci¬ed for the cells.

We are interested in counting the number of possible ordered par-

titions with r cells that can be formed from a set of n objects having a

prescribed number of elements in each cell. We consider ¬rst a special

case to illustrate the general procedure.

Suppose that we have eight students, A, B, C, D, E, F, G, and H,

and we wish to assign these to three rooms, Room 1, which is a triple

room, Room 2, a triple room, and Room 3, a double room. In how

many di¬erent ways can the assignment be made? One way to assign

the students is to put them in the rooms in the order in which they

arrive, putting the ¬rst three in Room 1, the next three in Room 2,

and the last two in Room 3. There are 8! ways in which the students

can arrive, but not all of these lead to di¬erent assignments. We can

represent the assignment corresponding to a particular order of arrival

as follows,

|BCA|DF E|HG|.

In this case, B, C, and A are assigned to Room 1, D, F, and E to Room

2, and H and G to Room 3. Notice that orders of arrival which simply

change the order within the rooms lead to the same assignment. The

number of di¬erent orders of arrival which lead to the same assignment

as the one above is the number of arrangements which di¬er from the

given one only in that the arrangement within the rooms is di¬erent.

There are 3! · 3! · 2! such orders of arrival, since we can arrange the

three in Room 1 in 3! di¬erent ways, for each of these the ones in

Room 2 in 3! di¬erent ways, and for each of these, the ones in Room

52 CHAPTER 3. PARTITIONS AND COUNTING

3 in 2! ways. Thus we can divide the 8! di¬erent orders of arrival into

groups of 3! · 3! · 2! di¬erent orders such that all the orders of arrival

in a single group lead to the same room assignment. Since there are

3! · 3! · 2! elements in each group and 8! elements altogether, there are

8!

groups, or this many di¬erent room assignments.

3!3!2!

The same argument could be carried out for n elements and r rooms,

with n1 in the ¬rst, n2 in the second, etc. This would lead to the

following result. Let n1 , n2 , . . . , nr be nonnegative integers with

n1 + n2 + . . . + nr = n.

Then:

The number of ordered partitions with r cells [A1 , A2 , . . . , Ar ] of a

set of n elements with n1 in the ¬rst cell, n2 in the second, etc. is

n!

n1 !n2 ! . . . nr !

We shall denote this number by the symbol

n!

.

n1 !, n2 !, . . . , nr !

Note that this symbol is de¬ned only if n1 + n2 + . . . + nr = n.

The special case of two cells is particularly important. Here the

problem can be stated equivalently as the problem of ¬nding the num-

ber of subsets with r elements that can be chosen from a set of n

˜

elements. This is true because any choice de¬nes a partition [A, A],

˜

where A is the set of elements chosen and A is the set of remaining

elements.

n!

The number of such partitions is r!(n’r)! and hence this is also the

n

number of subsets with r elements. Our notation for this case

r,n’r

n

is shortened to .

r

n

Notice that n’r is the number of subsets with n ’ r elements

which can be chosen from n, which is the number of partitions of the

˜ ˜

form [A, A] above. Clearly, this is the same as the number of [A, A]

partitions. Hence n = n’r .

n

r

Example 3.13 A college has scheduled six football games during a

season. How many ways can the season end in two wins, three losses,

and one tie? From each possible outcome of the season, we form a

53

3.4. COUNTING PARTITIONS

partition, with three cells, of the opposing teams. In the ¬rst cell

we put the teams which our college defeats, in the second the teams

to which our college loses, and in the third cell the teams which our

6

college ties. There are 2,3,1 = 60 such partitions, and hence 60 ways

in which the season can end with two wins, three losses, and one tie. ™¦

Example 3.14 In the game of bridge, the hands N, E, S, and W deter-

mine a partition of the 52 cards having four cells, each with 13 elements.

52!

Thus there are 13!13!13!13! di¬erent bridge deals. This number is about

5.3645 · 1028 , or approximately 54 billion billion billion deals. ™¦

Example 3.15 The following example will be important in probability

theory, which we take up in the next chapter. If a coin is thrown six

times, there are 26 possibilities for the outcome of the six throws, since

each throw can result in either a head or a tail. How many of these

possibilities result in four heads and two tails? Each sequence of six

heads and tails determines a two-cell partition of the numbers from

one to six as follows: In the ¬rst cell put the numbers corresponding

to throws which resulted in a head, and in the second put the numbers

corresponding to throws which resulted in tails. We require that the

¬rst cell should contain four elements and the second two elements.

Hence the number of the 26 possibilities which lead to four heads and

two tails is the number of two-cell partitions of six elements which have

four elements in the ¬rst cell and two in the second cell. The answer is

6

= 15. For n throws of a coin, a similar analysis shows that there are

4

n

di¬erent sequences of H™s and T™s of length n which have exactly r

r

heads and n ’ r tails. ™¦

Exercises

1. Compute the following numbers.

7

(a) 5

[Ans. 21.]

3

(b) 2

7

(c) 2

250

(d) 249

54 CHAPTER 3. PARTITIONS AND COUNTING

[Ans. 250.]

5

(e) 0

5

(f) 1,2,2

4

(g) 2,0,2

[Ans. 6.]

2

(h) 1,1,1

2. Give an interpretation for n and also for n

. Can you now give

0 n

a reason for making 0! = 1?

3. How many ways can nine students be assigned to three triple

rooms? How many ways if one particular pair of students refuse

to room together?

[Ans. 1680; 1260.]

4. A group of seven boys and ten girls attends a dance. If all the

boys dance in a particular dance, how many choices are there for

the girls who dance? For the girls who do not dance? How many

choices are there for the girls who do not dance, if three of the

girls are sure to be asked to dance?

5. Suppose that a course is given at three di¬erent hours. If ¬fteen

students sign up for the course,

(a) How many possibilities are there for the ways the students

could distribute themselves in the classes?

[Ans. 315 .]