Original title: Kombinatorické úlohy o permutacích
Translated title: Combinatorial problems on permutations
Authors: Wolfová, Mária ; Slavík, Antonín (advisor) ; Rmoutil, Martin (referee)
Document type: Master’s theses
Year: 2019
Language: cze
Abstract: [cze] [eng]
Diplomová práce ve své teoretické části shrnuje základní poznatky týkající se permutací. Kromě způsobů reprezentace permutací a určování jejich základních charakteristik se teoretická část zaměřuje především na výsledky týkající se rozkladu permutace na nezávislé cykly a hledání počtu permutací s určitou vlastností. Je zavedena takzvaná základní bijekce užitečná při řešení mnoha problémů týkajících se permutací. Dále je odvozen počet permutací bez pevného bodu, Eulerova čísla vyjadřující počet permutací s daným počtem sestupů a počet permutací s daným počtem překročení, Stirlingova čísla 1. druhu vyjadřující počet permutací s daným počtem cyklů a Catalanova čísla vyjadřující počet permutací, které neobsahují zvolený vzor délky tři. Pozornost je věnována rovněž Gilbreathovým permutacím a jejich vlastnostem. V praktické části je prezentováno 14 motivačních úloh. Při řešení těchto úloh jsou využity poznatky z teoretické části a odvozeny některé další zajímavé výsledky týkající se náhodných permutací. In its theoretical part, this thesis sums up the basic knowledge concerning permutations. Besides the representation of permutations and determination of their fundamental characteristics, the theoretical part is, first of all, aimed at results concerning the decomposition of permutations into disjoint cycles and at finding the number of permutations with a certain characteristic. We introduce the fundamental bijection that is useful for solving many problems concerning the permutations. Further on, we focus on the number of permutations without a fixed point, Eulerian numbers expressing the number of permutations with a given number of descents, and the number of permutations with a given number of excedances, Stirling numbers of the first kind expressing the number of permutations with a given number of cycles, and Catalan numbers representing the number of permutations avoiding a chosen pattern of length three. Attention is also paid to the Gilbreath permutations and their characteristics. The practical part consists of 14 solved problems. The solutions rely on the results presented in the theoretical part, and there are deduced some further interesting results concerning random permutations.
Keywords: disjoint cycles; Eulerian numbers; fixed points; Gilbreath permutations; pattern avoidance; random permutation; Stirling numbers; Eulerova čísla; Gilbreathovy permutace; nezávislé cykly; náhodná permutace; pevné body; Stirlingova čísla; vzory

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/109144

Permalink: http://www.nusl.cz/ntk/nusl-405207


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses