Information Technology Reference
In-Depth Information
to
k
cells in two possible manners: i) either allocating the remaining objects to
k
cells in
n
k
ways, and then adding the removed object to one of the
k
cells, in
k
different ways, or ii) allocating the remaining objects to
k
1 cells, leaving empty
one cell, and putting the removed object by itself in the empty cell.
By using Stirling numbers, we can also obtain the number of surjective functions
−
S
n
). In fact, these functions
correspond to the allocations of
n
objects to
k
distinguishable cells. Therefore, all
ways of distinguishing
k
cells, correspond to giving them
k
! different orderings,
which yield the following cardinality of
S
(
n
,
k
)
from a set of
n
elements to a set of
k
elements (
k
≤
(
n
,
k
)
:
k
!
n
k
|
S
(
n
,
k
)
|
=
.
The number of all possible partitions of
n
objects into any number of non-empty in-
discernible cells is given by the numbers
b
n
, called Bell numbers, after the American
mathematician who studied them:
n
i
=
∑
i
b
n
.
=
1
,
n
These numbers correspond to the different ways of arranging the first
n
non-zero
numbers into
monotonic
sequences, that is, sequences where the first occurrence of
a number cannot follow that of a number greater than it. For example 1 1 2 3 3 4 5
is monotonic, while 1 132345isnotmonotonic. In this way we get a partition of
the positions of the sequence into undistinguishable non-empty cells (the different
numbers occurring in the sequence).
7.4.2
Catalan Numbers
Catalan numbers count the possible ways of writing correct expressions of
n
pairs
of parentheses.
Expression
is correct, and
if
E
1
and
E
2
are correct, then
E
1
E
2
is correct too. This number corresponds to the
different ways 2
n
persons at a table can shake hands by avoiding crossing, or the
ways we can connect the two extremes of a diagonal in a square grid, by means
of paths consisting of horizontal and vertical segments on the grid. These numbers
also equal to the numbers of sequences of
n
occurrences of 1 and
n
occurrences of
−
()
is correct. If
E
is a correct expression, then also
(
E
)
1, such that the partial sums are never negative (from the beginning to any other
position). Let us call these sequences
positive sequences
over
{
1
,−
1
}
.
Theorem 7.10.
The number of positive sequences over
{
1
,−
1
}
of length
2
n is given
by the n-th Catalan number:
2
n
n
1
n
+
1
