Information Technology Reference
In-Depth Information
determine
k
different locations in a sequence: before the first occurrence, between
the first and the second occurrence, and so on. Therefore, by choosing the positions
where to put the
n
objects of the first type, we get the following value corresponding
to this kind of partitions:
n
+
k
−
1
.
n
If we want the number of partitions of
n
undistinguishable objects into exactly
k
non-empty distinct cells (
n
k
), then we apply the same method given above, but
we force the presence of one object before each of the
k
separators. Therefore, in
this case we get the following number of possibilities:
n
≥
−
1
.
k
−
1
With an analogous argument we can determine the number of
k
-multisets over a
set of
n
elements. In fact, consider now
n
1 undistinguishable separators and
k
undistinguishable tokens. Each permutation of
n
−
1 of one
type and
k
of a different type (tokens and separators), represents a multiset where
the number of tokens before the
i
+
k
−
1 objects with
n
−
1 separator corresponds to the multiplicity of
the
i
-th object of the set. For example, the multiset 3
a
−
+
2
b
+
4
c
of size 9 over 3
different kinds of objects,
a
,
b
,
c
, would be represented by (1 as separator and 0 as
token):
00010010000
.
Therefore, the number of
k
-multisets over a set of
n
elements is given by:
n
+
k
−
1
.
k
7.3.3
Integer Partitions
A partition of a positive integers
n
is a sum of positive integers equal to
n
.For
example, 10
5). This
kind of partition corresponds to allocate
n
undistinguishable objects to a number of
undistinguishable, non empty, cells. We denote by
P
=
2
+
3
+
5 is a partition of 10 in three parts (the summands 2
,
3
,
(
n
)
the number of partitions of
the integer
n
. Euler found a generating function for
P
, that is a function that, when
represented as infinite series of monomials
a
n
x
n
, with
n
(
n
)
∈
N
, satisfies the equation
a
n
=
P
(
n
)
. In fact, Euler has proven that:
1
1
x
k
∞
n
=
0
P
(
n
)
x
n
∞
k
=
1
=
.
−
The following asymptotic expression for
P
(
n
)
was first obtained by Hardy and Ra-
manujan in 1918 [224]:
