21.6 Permutations and combinations 607
Multinomial distributions
Multinomial distributions are generalizations of the binomial distribution for
experiments that have more than two possible outcomes. Let an experiment have
kpossible outcomes,E
1, E
2, =, E
k, with respective probabilitiesp
1,p
2, =, p
k. Then,
the joint probability that there are n
ioccurrences of outcomeE
i(i 1 = 11 , 2 , =, k), in n
independent trials is
(21.21)
where
is a multinomial coefficient (Section 7.3).
0 Exercises 14, 15
21.6 Permutations and combinations
The possible outcomes of tossing a coin or throwing a die are exclusive events with
equal probabilities; each of kpossible outcomes has probability 12 k. The counting of
equally-probable outcomes is important in several applications of probability theory
in the sciences and often involves the counting of the permutations and combinations
of sets of objects or events. The following theorems are some of the important results
in combinatorial theory.
2Permutations
A set of ndifferent (distinguishable) objects (real objects, numbers, events, and so on)
may be arranged in a row in a number of ways, and each such arrangement is called
a permutationof the nobjects. For example, the three letters A, B, and Ccan be
arranged in the 6 ways
ABC, ACB, BAC, BCA, CAB, CBA
There are3! 1 = 16 permutations of 3 different objects. In general:
1.The number of permutations of ndifferent objects is n!
The first object can be put in ndifferent positions, leavingn 1 − 11 positions for the
second object (think of nboxes in a row and nballs of different colours). The first two
n
nn n
n
nn n
12 k 12 k
=
!
!!!
Pn n n
n
nn n
pp p
kknnknk(, , )
12121212...,
...
=
2An early discussion of permutations and combinations is found in the Jewish mystical Sefer Yetsirah(Book of
creation), possibly of the second century AD, in which the (unknown) author calculates the ways of arranging the
22 letters of the Hebrew alphabet, and the number of combinations taken 2 at a time. The French mathematician,
astronomer, and biblical commentator Levi ben Gerson (1288–1344) gave a derivation of the rules of combinations
in his Maasei Hoshev(Art of the calculator) in 1321. He also invented the Jacob Staff, used for centuries by sailors
to measure the angular separation of heavenly bodies.