Information Technology Reference
In-Depth Information
Fig. 7.4
Poisson distribution for different values of
λ
(if
λ
>
10 it approximates to a
gaussian)
This formula has a simple combinatorial meaning. It corresponds to the number
of different ways of allocating
n
distinguishable objects into
m
distinguishable cells,
where
k
1
,
k
m
objects are allocated, respectively in the
m
cells.
It gives also the number of
permutations
with repetitions, that is, the different
ways we can change the positions to the elements of a sequence over an alphabet,
say
k
2
,...
{
a
,
b
,
c
,
d
}
, with
n
a
occurrences of
a
,
n
b
of
b
,
n
c
of
c
,and
n
d
of
d
. It is easy to
show that:
n
k
1
n
n
...
n
n
−
k
1
−
k
1
−
k
2
−
k
1
−
k
2
...−
k
m
−
2
=
.
k
1
,
k
2
,...,
k
m
k
2
k
3
k
m
−
1
7.3.2
Partitions and Multisets
Binomial coefficients provide also the formula for computing the number of parti-
tions of
n
undistinguishable objects into
k
distinguishable cells possibly empty.
In fact, for obtaining this number we can add
k
1 undistinguishable tokens,
that is, elements which are different from the given
n
undistinguishable objects.
Then, we consider all permutations of a sequence of
n
−
1 objects of two types.
Each permutation provides a partition into different cells. In fact, the
k
+
k
−
−
1tokens
