Information Technology Reference
In-Depth Information
context of combinatorial schemata, objects or cells are always distinct when you
count them, but they are undistinguishable when some of them can occur many
times and these multiple occurrences are counted as the occurrence of the same ob-
ject (distinguishability implies distinctness, but the converse implication does not
hold). In the following, when we speak of objects or cells, we assume that they are
distinguishable, unless the contrary is stated. The combinatorial schemata that we
will analyze will clarify these aspects.
7.1.1
Permutations and Arrangements
Let us consider
n
objects
. How many possibilities we have of arranging them in
a sequence? Such an arrangement is usually called a
permutation
of
n
objects.
In set-theoretic terms a permutation is a bijective function. In fact, we determine
this number by using an allocation schema associating the
n
objects to
n
cells
or
locations numbered from 1 to
n
(this terminology is used for a better visualization
of the arrangement). In the first cell we can choose one of
n
objects, in the second
one of the remaining
n
1 objects, and so on. In the last cell only one possibility of
choice remains, because the other
n
−
−
1 objects are already allocated. In conclusion,
the number of
n
-permutations is
n
(
n
−
1
)(
n
−
2
)
...
2
·
1
=
n
!
In this sense, factorial numbers count permutations.
The argument for counting permutations can be easily extended to the case of
arrangements
, that is, injective functions from
n
objects to
k
places, where
k
<
n
(permutations are arrangements where
n
=
k
). In this case, we get the following
product, which we call
k
-
subfactorial
of
n
:
n
(
n
−
1
)(
n
−
2
)
...
(
n
−
k
+
1
)=(
n
)
k
.
Of course:
(
n
)
k
=
n
!
/
(
n
−
k
)
!
Let us consider allocations of objects in cells where any object can occur any number
of times, but only one object can be allocated to each cell. How many possible
allocations of this kind, of
n
objects to
k
cells are there? Any allocation of this
type corresponds to a function from the cells to the objects. In this case, at any
step of the allocation process,
n
choices are possible, whence we have
n
k
different
arrangements with repetition.
The number of permutations and arrangements are useful for counting words.
How many words of length 10 can be written with 20 letters? They are 20
10
.How
many words of length 10 where no letter occurs more than once? They are
)
10
.
How many different words can be obtained by rearranging the order of letters in the
word
number
?6!
(
20
720.
It is interesting to remark that the ratio between the number of injective functions
and all possible functions becomes very small when
n
increases. This phenomenon,
=
