Multivariate combinatorial exploration with regular strategies

Abstract

In this thesis, two methods for automatic enumeration of permutation classes are studied.

The first method extends on the theory of combinatorial exploration. We review how combinatorial exploration works as a two phases process: the first phase creating a universe of rules and the second one searching that universe for a solution to a given enumeration problem. After that, we identify a situation where the search step does not succeed to provide an answer despite the universe "containing" (in some sense) one. We present a way to overcome this shortcoming by developing a new theory that allows to find these "answers". Then, we demonstrate how combinatorial exploration can be extended to apply to problems where some additional statistics are involved. This theory is applied to enumerate permutation classes for which we introduce a new decomposition strategy called fusion. Combining all the tools discussed so far, we provide the first direct enumeration of Av(1342).

For the second method, we study the staircase encoding of permutations, which maps a permutation to a staircase grid with cells filled with permutations. We study the restriction of the staircase encoding to many permutation classes where the encoding becomes a bijection. For each of these classes, we describe the image of the bijections using independent sets of graphs weighted with permutations. We then enumerate the permutation classes by deriving the generating function for the independent sets and then for their weighted counterparts. We use our results to uncover some unbalanced Wilf-equivalences of permutation classes.

Í þessari ritgerð er fjallað um tvær sjálfvirkar aðferðir við að telja umraðanaflokka.

Fyrri aðferðin útvíkkar fræðin um fléttufræðilega könnun. Við rifjum upp hvernig fléttufræðileg könnun virkar í tveimur skrefum: fyrsta skrefið býr til heim af reglum, og seinna skrefið leitar í þeim heimi að lausn að talningarvandamáli. Að því loknu finnum við aðstæður þar sem leitin skilar engri niðurstöðu, jafnvel þó heimurinn "innihaldi" (í ákveðnum skilningi) lausn. Við sýnum hvernig megi yfirstíga þetta vandamál með því að þróa nýja fræði sem leifir okkur að finna þessar "lausnir". Síðan sýnum við hvernig nota megi fléttufræðilega könnun megi útvíkka til að takast á við vandamál þar sem margar tölfræðir koma við sögu. Þessari fræði er beitt á umraðanaflokka, og þar skilgreinum við nýja kænsku sem kallast samruni. Með því að nota allar þessar niðurstöður tekst okkur að gefa fyrstu beinu talninguna á Av(1342).

Seinni aðferðin byggir á stigakóðun umraðana, sem varpar umröðunum í stigalaga kóðun þar sem hvert hólf inniheldur umröðun. Við rannsökum einskorðun þessarar stigakóðunar á umraðanaflokka þar sem kóðunin er gagntæk vörpun. Fyrir þessa flokka lýsum við mynd vörpunarinnar með því að nota óháð mengi í netum vigtuð með umröðunum. Við teljum umraðanaflokkana með því að finna framleiðniföll þessara óháðu mengja, með og án vigtun. Við notum þessar niðurstöður til þess að finna ójöfn Wilf-jafngildi umraðanaflokka.