<< . .

. 5
( : 20)



. . >>

the number 1. The number obtained in this way occurs so often that
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 .]

<< . .

. 5
( : 20)



. . >>