This master's thesis addresses the problem of counting objects that allow a certain degree of symmetry. In Mathematics, symmetry is associated with groups, which is why group theory is briefly summarized at the beginning, with a focus on group actions and permutation groups. Two important lemmas are mentioned: the orbit-stabilizer lemma, and the Burnside's lemma, which allows us to calculate the number of orbits of the corresponding group action by using the average number of fixed points of elements of the permutation group.
Next, Pólya-Redfield theory is presented, which deals with counting nonequivalent colorings of a given object with a certain degree of symmetry. An important part of this theory involves so-called cycle indices, which are related to the symmetry group of the object being considered. The main result of this theory is the Pólya-Redfield theorem, which tells us that by inserting sums of various powers of variables into the cycle index, we obtain a so-called list of colorings. This list of colorings is a polynomial, whose coefficients represent the number of nonequivalent colorings of the object, specifically for each particular arrangement of the "components" of the object in each color.
The last part of the presented theory of counting objects with symmetry discusses the de Bruijn's theorem, which is essentially a generalization of the Pólya-Redfield theorem to cases where, in addition to the symmetries of the object, there are also symmetries on the set of colors used to color the object.
A very important part of the master's thesis consists of three sets of symmetry-combinatorial problems, which follow the main theorems of the presented theory of counting, with each set clearly demonstrating the application of one of these theorems in solving counting problems.
|
