Název: Enumerace kompozic čísel se zakázanými vzory
Překlad názvu: Enumeration of compositions with forbidden patterns
Autoři: Dodova, Borjana ; Klazar, Martin (vedoucí práce) ; Jelínek, Vít (oponent)
Typ dokumentu: Diplomové práce
Rok: 2013
Jazyk: cze
Abstrakt: [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.
Klíčová slova: asymptotiky; generující funkce; kompozice; transcedence; zakázané vzory; asymptotics; compositions; generating function; pattern avoiding; transcendence

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/61442

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-330716


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce