en English is Íslenska

Thesis Reykjavík University > Tölvunarfræðideild > BSc verkefni >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1946/9181

Title: 
  • Wilf-classification of mesh patterns of short length
  • is Wilf-flokkun möskvamynstra
Submitted: 
  • May 2011
Abstract: 
  • This B.Sc. project deals with mesh pattern avoidance in permutations. A mesh pattern is a pair P=(p,R), where p is a permutation of length k and R is a subset of [0,k]x[0,k]. The elements of R denote filled boxes in a mesh pattern. For a permutation u to contain a mesh pattern, it has to contain the underlying classical pattern p, and no points in u can be located in the shaded boxes. In this paper we begin the study of Wilf-classifying mesh patterns by classifying 776 out of the 1024 mesh patterns of length 2. Two mesh patterns P and Q are said to be equivalent if for any permutation u, u avoids P if and only if u avoids Q. The paper introduces a new operation that preserves pattern equivalence and provides rules determining which additional boxes in a mesh pattern P can be shaded. This is useful to lower the number of patterns one needs to look at in the process of Wilf-classifying patterns. We also have some observations on the only non-trivial interval pattern of length 3.

  • is

    Í þessu B.Sc. verkefni vinnum við með mynstraforðun möskvamynstra í umröðunum. Möskvamynstur er par P=(p,R) þar sem p er umröðun af lengd k og R er hlutmengi í [0,k]x[0,k]. Stökin í R tákna skyggða ferninga í möskvamynstrinu. Umröðun u er sögð innihalda möskvamynstrið P ef hún inniheldur grunnmynstrið p og engir punktar u eru inn í skyggðu ferningum mynstursins P. Í þessu verkefni hefjum við Wilf-flokkun möskvamynstra, þar með hafa 776 mynstur af 1024 verið Wilf-flokkuð. Tvö möskvamynstur P og Q eru sögð vera jafngild ef fyrir sérhverja umröðun u gildir að u forðast P ef og aðeins ef u forðast Q. Verkefnið kynnir nýja aðgerð sem varðveitir jafngildi mynstra og gefur reglur um hvaða ferninga í mynstri P má skyggja aukalega í möskvamynstri. Þessi aðgerð er hentug til að minnka fjölda þeirra mynstra sem þarf að skoða við Wilf-flokkun mynstra. Einnig höfum við skoðað eina bilamynstrið af lengd 3 sem er ekki augljóst, og setjum fram athugasemdir um það.

Description: 
  • is Tölvunarfræði. Heildartexti lokaskýrslu. Prentuð útgáfa og öll fylgi gögn á CD eru varðveitt í bókasafni HR
Accepted: 
  • Jun 9, 2011
URI: 
  • http://hdl.handle.net/1946/9181


Files in This Item:
Filename Size VisibilityDescriptionFormat 
Wilf-classification of mesh patterns of short length - post-mortem.pdf204 kBOpenFylgiskjölPDFView/Open
Wilf-classification of mesh patterns of short length.pdf708.97 kBOpenHeildartextiPDFView/Open