Permutations and combinations

30.3 PERMUTATIONS AND COMBINATIONS
We note that (30.27) may be written in a more general form if S is not simply
divided into A and Ā but, rather, into any set of mutually exclusive events Ai that
exhaust S. Using the total probability law (30.24), we may then write
Pr(Ai ) Pr(B|Ai ),
Pr(B) =
i
so that Bayes’ theorem takes the form
Pr(A) Pr(B|A)
,
Pr(A|B) = i Pr(Ai ) Pr(B|Ai )
(30.28)
where the event A need not coincide with any of the Ai .
As a final point, we comment that sometimes we are concerned only with the
relative probabilities of two events A and C (say), given the occurrence of some
other event B. From (30.26) we then obtain a different form of Bayes’ theorem,
Pr(A) Pr(B|A)
Pr(A|B)
=
,
Pr(C|B)
Pr(C) Pr(B|C)
(30.29)
which does not contain Pr(B) at all.
30.3 Permutations and combinations
In equation (30.5) we defined the probability of an event A in a sample space S as
nA
Pr(A) =
,
nS
where nA is the number of outcomes belonging to event A and nS is the total
number of possible outcomes. It is therefore necessary to be able to count the
number of possible outcomes in various common situations.
30.3.1 Permutations
Let us first consider a set of n objects that are all different. We may ask in
how many ways these n objects may be arranged, i.e. how many permutations of
these objects exist. This is straightforward to deduce, as follows: the object in the
first position may be chosen in n different ways, that in the second position in
n − 1 ways, and so on until the final object is positioned. The number of possible
arrangements is therefore
n(n − 1)(n − 2) · · · (1) = n!
(30.30)
Generalising (30.30) slightly, let us suppose we choose only k (< n) objects
from n. The number of possible permutations of these k objects selected from n
is given by
n!
≡ nPk .
n(n − 1)(n − 2) · · · (n − k + 1) =
9:
; (n − k)!
8
k factors
1133
(30.31)
PROBABILITY
In calculating the number of permutations of the various objects we have so
far assumed that the objects are sampled without replacement – i.e. once an object
has been drawn from the set it is put aside. As mentioned previously, however,
we may instead replace each object before the next is chosen. The number of
permutations of k objects from n with replacement may be calculated very easily
since the first object can be chosen in n different ways, as can the second, the
third, etc. Therefore the number of permutations is simply nk . This may also be
viewed as the number of permutations of k objects from n where repetitions are
allowed, i.e. each object may be used as often as one likes.
Find the probability that in a group of k people at least two have the same birthday
(ignoring 29 February).
It is simplest to begin by calculating the probability that no two people share a birthday,
as follows. Firstly, we imagine each of the k people in turn pointing to their birthday on
a year planner. Thus, we are sampling the 365 days of the year ‘with replacement’ and so
the total number of possible outcomes is (365)k . Now (for the moment) we assume that no
two people share a birthday and imagine the process being repeated, except that as each
person points out their birthday it is crossed off the planner. In this case, we are sampling
the days of the year ‘without replacement’, and so the possible number of outcomes for
which all the birthdays are different is
365
Pk =
365!
.
(365 − k)!
Hence the probability that all the birthdays are different is
p=
365!
.
(365 − k)! 365k
Now using the complement rule (30.11), the probability q that two or more people have
the same birthday is simply
q = 1−p =1−
365!
.
(365 − k)! 365k
This expression may be conveniently evaluated using Stirling’s approximation for n! when
n is large, namely
n n
√
n! ∼ 2πn
,
e
to give
365−k+0.5
365
.
q ≈ 1 − e−k
365 − k
It is interesting to note that if k = 23 the probability is a little greater than a half that
at least two people have the same birthday, and if k = 50 the probability rises to 0.970.
This can prove a good bet at a party of non-mathematicians! So far we have assumed that all n objects are different (or distinguishable). Let
us now consider n objects of which n1 are identical and of type 1, n2 are identical
and of type 2, . . . , nm are identical and of type m (clearly n = n1 + n2 + · · · + nm ).
From (30.30) the number of permutations of these n objects is again n!. However,
1134
30.3 PERMUTATIONS AND COMBINATIONS
the number of distinguishable permutations is only
n!
,
n1 !n2 ! · · · nm !
(30.32)
since the ith group of identical objects can be rearranged in ni ! ways without
changing the distinguishable permutation.
A set of snooker balls consists of a white, a yellow, a green, a brown, a blue, a pink, a
black and 15 reds. How many distinguishable permutations of the balls are there?
In total there are 22 balls, the 15 reds being indistinguishable. Thus from (30.32) the
number of distinguishable permutations is
22!
22!
=
= 859 541 760. (1!)(1!)(1!)(1!)(1!)(1!)(1!)(15!)
15!
30.3.2 Combinations
We now consider the number of combinations of various objects when their order
is immaterial. Assuming all the objects to be distinguishable, from (30.31) we see
that the number of permutations of k objects chosen from n is n Pk = n!/(n − k)!.
Now, since we are no longer concerned with the order of the chosen objects, which
can be internally arranged in k! different ways, the number of combinations of k
objects from n is
n!
n
≡ n Ck ≡
for 0 ≤ k ≤ n,
(30.33)
k
(n − k)!k!
where, as noted in chapter 1, n Ck is called the binomial coefficient since it also
appears in the binomial expansion for positive integer n, namely
(a + b)n =
n
n
Ck ak bn−k .
(30.34)
k=0
A hand of 13 playing cards is dealt from a well-shuffled pack of 52. What is the probability
that the hand contains two aces?
Since the order of the cards in the hand is immaterial, the total number of distinct hands
is simply equal to the number of combinations of 13 objects drawn from 52, i.e. 52 C13 .
However, the number of hands containing two aces is equal to the number of ways, 4 C2 ,
in which the two aces can be drawn from the four available, multiplied by the number of
ways, 48 C11 , in which the remaining 11 cards in the hand can be drawn from the 48 cards
that are not aces. Thus the required probability is given by
4
C2
48
52 C
C11
13
4! 48! 13!39!
2!2! 11!37! 52!
(3)(4) (12)(13)(38)(39)
=
= 0.213 2 (49)(50)(51)(52)
=
1135
PROBABILITY
Another useful result that may be derived using the binomial coefficients is the
number of ways in which n distinguishable objects can be divided into m piles,
with ni objects in the ith pile, i = 1, 2, . . . , m (the ordering of objects within each
pile being unimportant). This may be straightforwardly calculated as follows. We
may choose the n1 objects in the first pile from the original n objects in n Cn1 ways.
The n2 objects in the second pile can then be chosen from the n − n1 remaining
objects in n−n1 Cn2 ways, etc. We may continue in this fashion until we reach the
(m − 1)th pile, which may be formed in n−n1 −···−nm−2 Cnm−1 ways. The remaining
objects then form the mth pile and so can only be ‘chosen’ in one way. Thus the
total number of ways of dividing the original n objects into m piles is given by
the product
Cn2 · · · n−n1 −···−nm−2 Cnm−1
(n − n1 )!
(n − n1 − n2 − · · · − nm−2 )!
n!
···
=
n1 !(n − n1 )! n2 !(n − n1 − n2 )!
nm−1 !(n − n1 − n2 − · · · − nm−2 − nm−1 )!
(n − n1 )!
(n − n1 − n2 − · · · − nm−2 )!
n!
···
=
n1 !(n − n1 )! n2 !(n − n1 − n2 )!
nm−1 !nm !
n!
.
(30.35)
=
n1 !n2 ! · · · nm !
N = n Cn1
n−n1
These numbers are called multinomial coefficients since (30.35) is the coefficient of
xn11 xn22 · · · xnmm in the multinomial expansion of (x1 + x2 + · · · + xm )n , i.e. for positive
integer n
n!
(x1 + x2 + · · · + xm )n =
xn1 xn2 · · · xnmm .
n
!n
!
· · · nm ! 1 2
1
2
n1 ,n2 ,... ,nm
n1 +n2 +···+nm =n
For the case m = 2, n1 = k, n2 = n − k, (30.35) reduces to the binomial coefficient
n
Ck . Furthermore, we note that the multinomial coefficient (30.35) is identical to
the expression (30.32) for the number of distinguishable permutations of n objects,
ni of which are identical and of type i (for i = 1, 2, . . . , m and n1 +n2 +· · ·+nm = n).
A few moments’ thought should convince the reader that the two expressions
(30.35) and (30.32) must be identical.
In the card game of bridge, each of four players is dealt 13 cards from a full pack of 52.
What is the probability that each player is dealt an ace?
From (30.35), the total number of distinct bridge dealings is 52!/(13!13!13!13!). However,
the number of ways in which the four aces can be distributed with one in each hand is
4!/(1!1!1!1!) = 4!; the remaining 48 cards can then be dealt out in 48!/(12!12!12!12!)
ways. Thus the probability that each player receives an ace is
4!
48! (13!)4
24(13)4
=
= 0.105. (12!)4 52!
(49)(50)(51)(52)
As in the case of permutations we might ask how many combinations of k
objects can be chosen from n with replacement (repetition). To calculate this, we
1136
30.3 PERMUTATIONS AND COMBINATIONS
may imagine the n (distinguishable) objects set out on a table. Each combination
of k objects can then be made by pointing to k of the n objects in turn (with
repetitions allowed). These k equivalent selections distributed amongst n different
but re-choosable objects are strictly analogous to the placing of k indistinguishable
‘balls’ in n different boxes with no restriction on the number of balls in each box.
A particular selection in the case k = 7, n = 5 may be symbolised as
xxx| |x|xx|x.
This denotes three balls in the first box, none in the second, one in the third, two
in the fourth and one in the fifth. We therefore need only consider the number of
(distinguishable) ways in which k crosses and n − 1 vertical lines can be arranged,
i.e. the number of permutations of k + n − 1 objects of which k are identical
crosses and n − 1 are identical lines. This is given by (30.33) as
(k + n − 1)! n+k−1
=
Ck .
k!(n − 1)!
(30.36)
We note that this expression also occurs in the binomial expansion for negative
integer powers. If n is a positive integer, it is straightforward to show that (see
chapter 1)
∞
(−1)k n+k−1 Ck a−n−k bk ,
(a + b)−n =
k=0
where a is taken to be larger than b in magnitude.
A system contains a number N of (non-interacting) particles, each of which can be in
any of the quantum states of the system. The structure of the set of quantum states is such
that there exist R energy levels with corresponding energies Ei and degeneracies gi (i.e. the
ith energy level contains gi quantum states). Find the numbers of distinct ways in which
the particles can be distributed among the quantum states of the system such that the ith
energy level contains ni particles, for i = 1, 2, . . . , R, in the cases where the particles are
(i)
(ii)
(iii)
(iv)
distinguishable with no restriction on the number in each state;
indistinguishable with no restriction on the number in each state;
indistinguishable with a maximum of one particle in each state;
distinguishable with a maximum of one particle in each state.
It is easiest to solve this problem in two stages. Let us first consider distributing the N
particles among the R energy levels, without regard for the individual degenerate quantum
states that comprise each level. If the particles are distinguishable then the number of
distinct arrangements with ni particles in the ith level, i = 1, 2, . . . , R, is given by (30.35) as
N!
.
n1 !n2 ! · · · nR !
If, however, the particles are indistinguishable then clearly there exists only one distinct
arrangement having ni particles in the ith level, i = 1, 2, . . . , R . If we suppose that there
exist wi ways in which the ni particles in the ith energy level can be distributed among
the gi degenerate states, then it follows that the number of distinct ways in which the N
1137
PROBABILITY
particles can be distributed among all R quantum states of the system, with ni particles in
the ith level, is given by

R

N!


wi for distinguishable particles,

 n1 !n2 ! · · · nR !
i=1
W {ni } =
R


(30.37)


wi
for indistinguishable particles.

i=1
It therefore remains only for us to find the appropriate expression for wi in each of the
cases (i)–(iv) above.
Case (i). If there is no restriction on the number of particles in each quantum state,
then in the ith energy level each particle can reside in any of the gi degenerate quantum
states. Thus, if the particles are distinguishable then the number of distinct arrangements
is simply wi = gini . Thus, from (30.37),
n
g ni
N!
i
gi i = N!
.
n1 !n2 ! · · · nR ! i=1
ni !
i=1
R
W {ni } =
R
Such a system of particles (for example atoms or molecules in a classical gas) is said to
obey Maxwell–Boltzmann statistics.
Case (ii). If the particles are indistinguishable and there is no restriction on the number
in each state then, from (30.36), the number of distinct arrangements of the ni particles
among the gi states in the ith energy level is
wi =
(ni + gi − 1)!
.
ni !(gi − 1)!
Substituting this expression in (30.37), we obtain
W {ni } =
R
(ni + gi − 1)!
.
ni !(gi − 1)!
i=1
Such a system of particles (for example a gas of photons) is said to obey Bose–Einstein
statistics.
Case (iii). If a maximum of one particle can reside in each of the gi degenerate quantum
states in the ith energy level then the number of particles in each state is either 0 or 1.
Since the particles are indistinguishable, wi is equal to the number of distinct arrangements
in which ni states are occupied and gi − ni states are unoccupied; this is given by
w i = gi Cni =
gi !
.
ni !(gi − ni )!
Thus, from (30.37), we have
W {ni } =
R
i=1
gi !
.
ni !(gi − ni )!
Such a system is said to obey Fermi–Dirac statistics, and an example is provided by an
electron gas.
Case (iv). Again, the number of particles in each state is either 0 or 1. If the particles
are distinguishable, however, each arrangement identified in case (iii) can be reordered in
ni ! different ways, so that
gi !
w i = g i Pn i =
.
(gi − ni )!
1138