Information Technology Reference
In-Depth Information
D
2
D
1
(
23
)=
P
(
21
)
−
(
21
)
P
(
21
)=
792
D
1
(
21
)=
P
(
20
)=
627
D
2
(
)=
23
165
D
3
D
1
D
2
(
)=
(
)
−
(
)
−
(
)
23
P
20
20
20
D
1
(
20
)=
P
(
19
)=
490
D
2
D
1
(
20
)=
P
(
18
)
−
(
18
)
P
(
18
)=
385
D
1
(
18
)=
P
(
17
)=
297
D
2
(
20
)=
88
D
3
(
23
)=
627
−
490
−
88
=
49
D
4
(
27
)=
1255
−
1002
−
165
−
49
=
39.
7.4
Stirling, Bell, Catalan, and Bernoulli Numbers
In this section we briefly present some important classes of numbers related to fun-
damental enumeration formulae (see [218] for more details).
7.4.1
Stirling and Bell Numbers
Now, let us consider the number of allocations of
n
distinguishable objects to
k
undistinguishable non-empty cells. For counting these combinatorial schemata, we
introduce this definition, by induction, of Stirling numbers of the second kind, de-
noted by:
n
k
.
Stirling numbers of the first kind, we only mention here, are denoted by:
n
k
and count the number of permutations of
n
objects having exactly
k
cycles (a cycle
(
is a permutation where
a
goes to
b
,
b
goes to
c
...and so on, and ends
with
m
going to
a
).
Stirling numbers (of the second kind) satisfy the following equations:
n
n
abc
...
m
)
n
1
=
=
1
n
k
n
k
n
k
+
1
=
+
.
k
−
1
In fact, when allocating
n
1 objects into
k
undistinguishable cells, firstly we can
remove one object from the given object. The remaining objects can be allocated
+
