PermPAL - Permutation Pattern Avoidance Library

Abstract

Við leitum leiða til að reikna út tölusetningu (e. enumeration) á klösum umraðana (e. permutation classes) sem innihalda ekki mynstur út frá fléttufræðilegum (e. combinatorial) formgerðum (e. structure) sem skilgreind eru af reikniritunum Struct og ATRAP. Framleiðniföll og rakningarformúlur eru notuð til að reikna fjölda umraðana af ákveðnum lengdum. Talning út frá Struct þekjum (e. cover) heppnaðist í öllum tilvikum en endurkvæmni í formgerðum ATRAP trjáa gerði sambærilega talningu þeirra erfiða. Framleiðniföll sem við reiknuðum út fyrir klasa með mynstur sem innihalda umraðanir úr S3 og S4 voru flokkuð í Wilf klasa (e. Wilf-classes). Gagnagrunnur og vefur var settur upp til að geyma og birta allar niðurstöður, sem eru aðgengilegar á http://permpal.ru.is.

We explore and develop ways to enumerate permutation pattern avoidance classes from combinatorial structures defined by the algorithms Struct and ATRAP. Generating functions and recurrence relations are used to describe the coefficients for permutations of certain lengths. Enumeration of avoidance classes from Struct covers was successful in all cases,but recursively defined structures posed a problem in ATRAP trees. The generating functions we obtained for bases with patterns from S3 and S4 were categorized into Wilf-Classes. A database and a web site were set up to store and display all the results, and are accessible on http://permpal.ru.is.