Catalanova števila : magistrsko delo

Kozarski, Lara (avtor), Konvalinka, Matjaž (mentor)

V delu predstavimo nekatere kombinatorične probleme, ki ustrezajo zaporedju Catalanovih števil, ter zapišemo bijekcije med njimi. Podamo eksplicitno formulo in rekurzivno zvezo za izračun splošnega člena v tem zaporedju in ju dokažemo na več načinov. Izpeljemo rodovno funkcijo zaporedja ter si ogledamo asimptotiko Catalanovih števil. Definiramo $k$-Catalanova števila kot eno izmed posplošitev in opišemo kombinatorične probleme, ki jim ustrezajo. Dokažemo tudi posplošeno formulo, ki ustreza $k$-Catalanovim številom, in na kratko omenimo še nekaj zgodovinskih animivosti.

• Jezik: Slovenski jezik
• Ključne besede: Catalanova števila, preštevalna kombinatorika, bijekcije, Dyckove poti
• Vrsta gradiva: Magistrsko delo/naloga
• Tipologija: 2.09 - Magistrsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Kraj izida: Ljubljana
• Založnik: [L. Kozarski]
• Leto izida: 2014
• Št. strani: 66 str.
• PID: 20.500.12556/RUL-95870
• UDK: 519.1
• COBISS.SI-ID: 17207641
• Datum objave v RUL: 22.09.2017

Sekundarni jezik

• Jezik: Angleški jezik

Izvleček

The aim of this thesis is to present some examples of combinatorial problems that correspond to the sequence of Catalan numbers and write down bijections between them. We give an explicit formula and a recurrence relation for computation of the general term of this sequence and find different proofs that they hold. We derive the formula for the generating function of the sequence and take a look at asymptotic behavior of Catalan numbers. We define $k$-Catalan numbers as an example of a generalization and describe the corresponding combinatorial problems. We also prove the generalized formula that corresponds to $k$-Catalan numbers and briefly mention a few interesting historical facts.

• Ključne besede: Catalan numbers, enumerative combinatorics, bijections, Dyck paths