E-Locus - Institutional Repository of the University of Crete

Home Collections School/Department School of Sciences and Engineering Department of Mathematics and Applied Mathematics Post-graduate theses

Post-graduate theses

Current Record: 3 of 125

[Add to Basket]

Identifier

000464368

Title

Μέθοδοι κοσκινίσματος

Alternative Title

Sieve methods

Author

Αθανασίου, Δημήτριος-Μάριος

Thesis advisor

Τζανάκη, Ελένη

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.

Language

Greek, English

Subject

Combinatorics

Discordant permutations

Inclusion -exclusion

Transfer matrix method

Ασύμφωνες μεταθέσεις

Αυτοαντίστροφη απεικόνιση

Εγκλεισμός-αποκλεισμός

Συνδυαστική

Issue date