
Chapter 2
Basic Tools
Today, combinatorics is an important branch of mathematics and has many applications
in computer science, physics, chemistry, and biology. Usually, one is interested in counting
objects of a set that depend on a parameter or several parameters, for example, the number
of partitions of the set [n] (here the parameter is n), or the number of set partitions of the set
[n] with exactly k blocks (here the parameters are n and k). It is not hard to enumerate the
number of such partitions for small values of n and k by exhibiting all possibilities, but as n
(k) increases, the number of such partitions grows very fast, and so we need