Abstract |
The term sieve method is used in combinatorics in order to describe the procedure in which
we enumerate a set S by considering a larger set and then deleting the redundant elements. This
technique can be separated into two basic categories: the first is the usual inclusion-exclusion
method in which we approach the desired enumeration by counting the elements of a larger set,
then subtracting an approximation of the redundant elements and we repeat the procedure as
many times as necessary in order to eliminate the error. The second method also starts with
the enumeration of a larger set S′, but now we assign a weight function to its elements. The
weight function is defined “naturally” in the sense that it is related to the combinatorics of the
problem and has the property that when summing over all the weighted elements of S′ we get
simplifications which finally lead us to the desired enumeration.
This thesis is organized as follows. In Section 1 we state the inclusion-exclusion principle in its
full generality. We then present a special case where the method takes the form of a determinant.
More precisely, we study the set of permutations according to their descent set and we further
generalize the enumeration for the joint distribution of descents and inversions.
In Section 2 we study permutations with restricted positions. A simple starting example is
permutations with no fixed points (derangements), a well known generalization is the so called
probl`eme des m´enages which finally generalizes the set of k-discordant permutations. For k = 1
and 2, the set of k-discordant permutations reduces the first two cases.
In Section 3 we present a method to solve the problem of k-discordant permutations. This
method, which involves directed graphs, their adjacency matrices and linear algebra, is known
as the tranfer matrix method. Its main feature is that it transforms the problem of k-discordant
permutations to that of the enumeration of closed paths of a directed graph.
In Section 4 we study the method of sign-reversing involutions. We present a couple of wellknown
examples and we conclude with a very interesting application concerning the enumeration
of non-intersecting paths in directed graphs.
|