Alberi aleatori: formula di Cayley e struttura degli alberi aleatori

Cayley's formula counts the number of trees with n nodes, where n is a natural number. While various proofs of this formula exist, in this thesis we present one of the most recent ones, proposed by Louigi Addario-Berry and Serte Donderwinkel in 2021, in which we associate a unique numerical sequence to each tree and viceversa. This bijection is also useful for deriving results regarding the distribution of distances between nodes in trees, allowing us to discuss local and global structures of random trees. In conclusion we define Bienaymé trees, random trees in which every node has a random number of children, given a certain probability distribution. We are interested in determining the conditions under which these random trees have a finite or infinite number of nodes.

La formula di Cayley conta il numero di alberi di n nodi, con n numero naturale. Esistono varie dimostrazioni di questa formula. In questa tesi trattiamo una delle più recenti, proposta da Louigi Addario-Berry e Serte Donderwinkel nel 2021, in cui a ciascun albero viene associata un'unica sequenza di numeri e viceversa. Questa biiezione è utile anche a fornire alcuni risultati sulla distribuzione delle distanze tra nodi negli alberi, permettendoci di discutere della struttura locale e globale degli alberi aleatori. Infine definiamo gli alberi di Bienaymé, alberi aleatori in cui ogni nodo ha un numero di figli casuale, che segue una certa distribuzione di probabilità. Siamo interessati a capire sotto quali condizioni questi alberi aleatori hanno un numero finito o infinito di nodi.