Catalanova števila : magistrsko delo

Kozarski, Lara (author), 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.

• Language: Slovenian
• Keywords: Catalanova števila, preštevalna kombinatorika, bijekcije, Dyckove poti
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Place of publishing: Ljubljana
• Publisher: [L. Kozarski]
• Year: 2014
• Number of pages: 66 str.
• PID: 20.500.12556/RUL-95870
• UDC: 519.1
• COBISS.SI-ID: 17207641
• Publication date in RUL: 22.09.2017

Secondary language

• Language: English

Abstract

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.

• Keywords: Catalan numbers, enumerative combinatorics, bijections, Dyck paths