Inversioner i de 1324-undvikande permutationerna

QC 2026-04-07

Abstract

Mönsterundvikning har sitt ursprung i en datavetenskaplig fråga: vilka följder av distinkta tal kan sorteras med hjälp av en enda stack? Knuth (1968) visade att dessa följder kännetecknas av att de inte innehåller någon delföljd a, b, c som uppfyller c < a < b. En sådan delföljd har samma relativa ordning som permutation 231, så vi säger att vår ursprungliga följd undviker 231.

Mer allmänt är mönsterundvikning ett naturligt sätt att begränsa strukturen av permutationer genom att förbjuda delföljder med en viss relativ ordning. Detta har blivit ett populärt ämne inom enumerativ kombinatorik, och det finns kopplingar till många andra områden.

Att bestämma antalet 1324-undvikande permutationer av längd n är det viktigaste öppna problemet inom mönsterundvikning. Denna avhandling består av två artiklar som bidrar till inv-monotonicitetsförmodan av Claesson, Jelínek och Steingrímsson (2012), som säger att av_n^k(1324), antalet 1324-undvikare av längd n med ett fixerat antal k inversioner, är svagt växande i n. Om förmodan är sann, förbättrar den vår förståelse av det asymptotiska beteendet av antalet 1324-undvikare.

I Artikel A ger vi en explicit formel för av_n^k(1324) för alla n ≥ (k + 7)/2. Beviset bygger på en ny strukturell karaktärisering av 1324-undvikare med få inversioner. En konsekvens av resultatet är att inv-monotonicitetsförmodan håller när n ≥ (k + 7)/2.

I Artikel B studerar vi inv-monotoniciteten av klasser av permutationer som undviker flera mönster. Vi visar att mängderna {1324, 231} och {1324, 2314, 3214, 4213} är inv-monotona via explicita injektioner, och introducerar en metod för att konstruera stora inv-monotona mängder. Vi analyserar också strukturen av stora permutationer med ett fixerat antal inversioner som undviker 1324 och ett annat mönster av längd fyra, och bevisar flera halvmonotonicitetsresultat liknande Artikel A.

Link to DiVA