Original title: Enumerace kompozic čísel se zakázanými vzory
Translated title: Enumeration of compositions with forbidden patterns
Authors: Dodova, Borjana ; Klazar, Martin (advisor) ; Jelínek, Vít (referee)
Document type: Master’s theses
Year: 2013
Language: cze
Abstract: [cze] [eng]
Enumerace kompozic čísel se zakázanými vzory Abstrakt Tato práce si klade za cíl odvodit některé výsledky pro 3-regulární kompozice, tedy kompozice se zakázaným vzorem {121, 212, 11}, které jsou jistým zobecněním Carlitzových kompozic. Pomocí generujících funkcí příslušejících kompozicím se zakázanou množinou vzorů {121, 11} a {212, 11} počítáme horní asymptotický odhad koeficientů mocninného rozvoje generující funkce příslušející 3-regulárním kompozicím. S využitím teorie konečných automatů dostáváme také dolní odhad. Ten posléze zpřesňujeme na základě 3-blokových kompozic. Pro generující funkci příslušející 3- regulárním kompozicím se zvýrazněnou předposlední a poslední částí dokazujeme rekurzivní vztah. Kromě 3-regulárních kompozic a úloh, které s nimi přímo souvisejí, se zabýváme také kompozicemi s množinou zakázaných vzorů {312, 321} s částmi z konečné množiny [d], pro něž odvozujeme maticový tvar generující funkce. V závěru práce dokazujeme transcendentalitu generující funkce příslušející Carlitzovým kompozicím. Enumeration of pattern avoiding compositions of numbers Abstract The aim of this work was to find some new results for 3-regular compositions, i.e., for those compositions which avoid the set of patterns {121, 212, 11}. Those compositions can be regarded as a generalization of Carlitz composition. Based on the generating function of compositions avoiding the set of patterns {121, 11} and {212, 11} we derive an upper bound for the coefficients of the power series of the generating function of 3-regular compositions. Using the theory of finite automata we derive its lower bound. We develop this result further by defining 3-block compositions. For the generating function of 3-regular compositions we prove a recursive ralation. Besides that we also compute the generating function of compositions avoiding the set of patterns {312, 321} whose parts are in the set [d]. In the last section we prove that the generating function of Carlitz compositions is transcendental.
Keywords: asymptotics; compositions; generating function; pattern avoiding; transcendence; asymptotiky; generující funkce; kompozice; transcedence; zakázané 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/61442

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


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