Enumerating score sequences and permutations by inversions and forbidden patterns

Abstract

This thesis studies the enumeration of score sequences and permutations. The first paper settles a conjecture of Hanna on a recursion for the number of score sequences of a tournament, derives a closed formula, and gives a quadratic-time algorithm. The second presents generating functions for permutations with few inversions: those with as many inversions as elements, and those with a fixed number of inversions fewer than elements. The third continues on the theme of inversions, enumerating pattern-avoiding permutations by inversions for all patterns of length at most 3. The fourth and last paper explores how to obtain bounds on the number of 1324-avoiding permutations by encoding permutations as walks in a directed graph.

Þessi doktorsritgerð rýnir í talningu stigaruna og umraðana. Fyrsta rannsóknarritgerðin í henni sannar tilgátu Hanna um rakningu fjölda stigaruna, leiðir út lokaða formúlu og gefur kvaðratískt reiknirit fyrir útreikning þeirra. Næsta ritgerð setur fram framleiðandi föll fyrir umraðanir með fáar umhverfingar, fyrst fyrir umraðanir með jafn mörg stök og umhverfingar og svo fyrir þær með fastan fjölda umhverfinga færri en stök. Sú þriðja heldur sig við umhverfingar og telur allar mynstursforðandi umraðanir útfrá umhverfingum fyrir mynstur af lengd mest 3. Fjórða og síðasta rannsóknarritgerðin kannar hvernig megi leiða út efra mark á fjölda 1324-forðandi umraðanir með því að túlka umraðanir sem vegi í stefndu neti.