Dokazi Cayleyeve formule

master's thesis

• Title (english): Proofs of Cayley's formula
• Author: Patricija Dovijanić
• Mentor: Vedran Krčadinac (mentor)
• Committee member: Vedran Krčadinac (predsjednik povjerenstva)
• Committee member: Boris Širola (član povjerenstva)
• Committee member: Igor Pažanin (član povjerenstva)
• Committee member: Sonja Štimac (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2024-03-01, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu proučavamo Cayleyevu formulu i njene dokaze. Najprije uvodimo osnovne pojmove teorije grafova i iskaz Cayleyeve formule. Zatim prelazimo na njene odabrane dokaze, počevši s bijektivnim dokazima: dokaz pomoću Pruferovih kodova, dokaz Joyalovom bijekcijom te dokaz pomoću funkcija parkiranja. Potom provodimo dokaze koji se temelje na matematičkoj indukciji: dokaz formulom uključivanja-isključivanja te Riordanov i Renyijev dokaz. Slijede dokazi dvostrukim prebrojavanjem: Pitmanov dokaz preko usmjerenih stabala, dokaz preko razapinjućih stabala i Clarkeov dokaz pomoću prespajanja. Zatim obrađujemo Polyin dokaz preko funkcija izvodnica i Lagrangeove formule inverzije. Kao primjer matričnog dokaza dajemo dokaz Kirchhoffovim matričnim teoremom o stablima. Završavamo vjerojatnosnim dokazom preko Poissonovog procesa grananja.

Abstract (english)

In this thesis, we study Cayley’s formula and its various proofs. First, we introduce basic graph theory notation and the statement of Cayley’s formula. We then move on to a selection of its proofs, starting with bijective proofs: a proof using Prufer codes, a proof using Joyal’s bijection, and a proof using parking functions. Then we carry out proofs based on mathematical induction: a proof using the principle of inclusion and exclusion, and Riordan and Renyi’s proof. Proofs by double counting follow: Pitman’s proof via directed trees, a proof via spanning trees, and Clarke’s proof using linkages of trees. We continue by covering Polya’s proof via generating functions and Lagrange’s inversion formula. We also present a proof using Kirchhoff’s matrix-tree theorem. We conclude with a probabilistic proof using a Poisson branching process.

• Keywords: Pruferovi kodovi; Joyalova bijekcija; Riordanov dokaz; Renyijev dokaz; Pitmanov dokaz
• Keywords (english): Prufer codes; Joyal’s bijection; Riordan proof; Renyi’s proof; Pitman’s proof
• Language: croatian
• URN:NBN: urn:nbn:hr:217:272993
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-03-13 09:05:44