Information Technology Reference
In-Depth Information
referred to as the
rarity of injections
has very surprising consequences. For example,
in a town where seven accidents occur each week, it is very improbable that these
accidents are distributed one per day. In fact, 7!
7
7
00613, therefore unlucky
days and lucky days, most probably, can be experienced. A famous example in this
regard is the so-called birthday phenomenon. If you consider a class with
m
students,
with
m
/
<
0
.
23, you have a big probability of finding two of them who were born on
the same day of the year. In general, the probability that
m
birthdays coincide is
given by:
>
1
1
1
−
(
365
)
m
365
m
1
365
2
365
m
1
365
−
p
=
1
=
−
−
...
−
.
If we discard the products between fractions (which are very small) the expression
can be approximated by:
1
+
2
+
3
...
+(
m
−
1
)
m
(
m
−
1
)
p
≈
1
−
=
1
−
.
365
730
The previous examples are close to an important combinatorial principle known as
Pigeonhole Principle
.
Ta b l e 7 . 1
The Pigeonhole Principle
For any allocation of
n
objects to
m
cells, where
m
<
n
, at least one cell
has to contain more than one object.
In fact, in a class with more than 366 students, at least two of them were born in
the same day (the date February 29 is included). This principle has very important
consequences. For example, if a dynamical system has a finite number of possi-
ble states, with no terminal state (where it may remain forever), then it has to be
eternally recurrent
, that is, some of its states occurs an unbounded number of times.
7.1.2
Combinations and Binomial Coefficients
How many possibilities are there of choosing
k
objects among
n
given objects? That
is, how many
k
-subset does a set of cardinality
n
have?
A
k
-subset of
n
objects is also called a
k
-combination over
n
objects. Also in
this case we can use an allocation schema. In fact, a combination is obtained by
allocating
k
of the
n
objects to
k
undistinguishable cells, with exactly an object
per cell. Therefore, the number of
k
-combinations of
n
objects can be deduced by
allocating the
n
objects to
k
distinguishable cells, in
)
k
ways, and then by dividing
this number for the number of possible different ways these cells can be ordered,
that is
k
! ways. In conclusions the combinations we are searching are:
(
n
(
n
)
k
k
!
=
n
!
k
!
(
n
−
k
)
!
