Information Technology Reference
In-Depth Information
7
Combinations and Chances
Archimedes' Truncated
icosahedron
Abstract.
Combinatorics is the field of mathematics which provides methods for
counting discrete structures of a given type. The exact evaluation of these num-
bers has very often a great importance in many theoretical and applicative contexts.
In this chapter the basic formulae of combinatorics will be presented, by empha-
sizing the links among combinatorics, probability, statistics, and biological applica-
tions. The Least Square Evaluation method is outlined, and basic notions about trees
and graphs are also provided with the fundamental enumeration formulae of these
structures.
7.1
Factorials and Binomial Coefficients
The main aim of combinatorics is the evaluation of the numbers of finite mathe-
matical structures of a given type. In the following sections, we present the basic
combinatorial schemata which occur frequently in the problems of counting finite
structures. A simple and unifying way of describing combinatorial schemata is the
notion of
allocation
. An allocation is defined by a set of objects and a set of cells,
and a way of putting objects into cells. Many kinds of allocations can be considered
in correspondence to the following features: i) whether or not objects are distinct,
ii) whether or not cells are distinct, iii) whether or not objects can be repeated, and
iv) whether or not cells can be repeated.
An important aspect in this regard is the explanation of what exactly means “dis-
tinct”. In fact, two objects are of course distinct, otherwise they is only one object.
However, in many contexts it is necessary to discern between
distinct
and
distin-
guishable
. Two balls having exactly the same shape are distinct when you put them
together on a table, but they may be not easily distinguishable if you put one of
them alone, and then the other one, or the same, at subsequent points in time. In the
