Cryptography Reference
In-Depth Information
2.1.1 Permutations and Choices
As we start calculating probabilities, it becomes necessary to have a clearer understanding of counting. Spe-
cifically, we need to remember a few basic ideas about counting arrangements and ways to choose objects.
Sometimes we will want to know the number of
permutations
of a given set of objects — the number of
ways they can be written down in an order. For example, with two objects, say, the numbers 1 and 2, we can
write them as (1 2) and (2 1), so there are two permutations. With three objects, say 1, 2, and 3, we can write
them down in six different orders: (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), and (3 2 1). A clever thought would
be that we started with 2, and when we added a third object, we get 6 = 3 × 2. If we want to know all of the
permutations of four objects, we have to consider all of the cases above, with the fourth object being placed in
at different places. This means that four can be placed at the beginning of all of the above:
(4 1 2 3), (4 1 3 2), (4 2 1 3), (4 2 3 1), (4 3 1 2), (4 3 2 1)
Or we can add the number 4 in between the first and second entries, as in
(1 4 2 3), (1 4 3 2), (2 4 1 3), (2 4 3 1), (3 4 1 2), (3 4 2 1)
as well as in between the second and third, and after the third. This is four different places, with each of them
having six arrangements, for a total of 24 different arrangements. Note that 24 = 4 × 3 × 2 × 1.
For five items, we would then have five places to put the fifth object, and each would have 24 places to go,
for a total of 24 × 5 = 120. The pattern continues on forever. These numbers (2, 6, 24, 120,...), obtained by mul-
tiplying successive numbers together, are results of the
factorial
function. The factorial of a number is usually
denoted with an exclamation mark, as in 6! = 6 × 5 × 4 × 3 × 2 × 1. It should be obvious, but worth saying, that
there is only one way to organize a set of one thing: it, by itself. Similarly, there is only one way to specify the
arrangement of a set of nothing: with a set of nothing. Thus, by definition, 1! = 0! = 1.
Another important concept is the idea of
permuted choices
— how many different ways there are of select-
ing two objects from a set of four objects, where order does not matter. For example, from the set of numbers 1,
2, 3, and 4, how many pairs can we pick? We can easily see that there are the following six pairs:
(1 2), (1 3), (14), (2 3), (2 4), (3 4)
where order doesn't matter, so (1 2) is equivalent to (2 1).
The number of such sets that are being picked can be calculated using a
binomial coefficient
— it is a func-
tion of two variables,
n
and
k
, where
n
is the number of objects in the larger set, and
k
is the size of the sets that
are desired to be picked from the
n
objects, where order does not matter. In this topic, we denote this binomi-
al coefficient as , although it can also be denoted as
C
n,k
and
C
(
n, k
) or even
n
C
k
. When read out loud, it is
almost always pronounced,
“n
choose k.” (I say “almost always” because most mathematicians and scientists
frown upon saying “always” unless there is proof.)
The simple way to calculate these binomial numbers is to use the following formula, based on the concept of
permutations and factorials above:
For example, say we have five cars to choose from, and we need to pick two. How many ways are there to pick
two of them? In this case, we don't care about the order in which they are picked, just the number of ways to
choose two items from five. Calculating “5 choose 2”:
meaning we have 10 different pairs of cars that could be chosen.
Search WWH ::
Custom Search