Geri Dön

Pattern-avoiding permutations: The case of length three, four, and five

Motif içermeyen permütasyonlar: Uzunluğu üç, dört ve beş olan durumlar

PDF İndir

  1. Tez No: 828668
  2. Yazar: ZİLAN AKBAŞ
  3. Danışmanlar: DR. ÖĞR. ÜYESİ GÖKHAN YILDIRIM
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 125

Özet

Uzunluğu $n$ olan bir permütasyon, kendisinde daha kısa $k$ uzunluğundaki bir permütasyonla aynı göreceli sıralamaya sahip bir altdizi içeriyorsa, bu permütasyonu motif olarak içerir. Aksi takdirde, bu permütasyon bu motifi içermez. Uzunluğu $n$ olan permütasyonlar kümesi $S_n$ ile, uzunluğu $n$ olan ve $\tau$ motifini içermeyen permütasyonlar kümesi $S_n(\tau)$ ile gösterilir. Motif içermeme, motif kümesi $S_k$ üzerinde bir denklik bağıntısı tanımlar. \rho, \tau \in S_k$ iken her $n \geq 1$ için $|S_n(\rho)| = |S_n(\tau)|$ doğruysa $\rho$ ve $\tau$ aynı Wilf sınıfındadır denir ve $\rho \sim_W \tau$ ile gösterilir. Bu denklik sınıflarına Wilf sınıfları denir. Başlıca sorular $S_k$'nın Wilf sınıflarını belirlemek ve her sınıftaki eleman sayısını bulmaktır. Öncelikle $S_3$ ve $S_4$'ün Wilf sınıflarının belirlenmesine ve Wilf sınıflarının sayımına yönelik çalışmaları inceliyoruz. Daha sonra, uzunluğu beş olan ikili motiflerin Wilf sınıflandırmasına ilişkin bazı yeni sayısal sonuçlar sunuyoruz. Eğer bir Wilf sınıfında birden fazla motif ikilisi varsa buna büyük Wilf sınıfı, sadece bir tane motif ikilisi varsa küçük Wilf sınıfı denir. Uzunluğu beş olan ikili motifler için en az 968 küçük Wilf sınıfı ve en fazla 13 büyük Wilf sınıfı olduğunu gösteriyoruz.

Özet (Çeviri)

A shorter permutation of length $k$ is said to appear as a pattern in a longer permutation of length $n$ if the longer permutation has a subsequence of length $k$ that is order isomorphic to the shorter one. Otherwise, the longer permutation avoids the shorter one as a pattern. We use $S_n(\tau)$ to denote the set of permutations of length $n$ that avoid pattern $\tau$. Pattern avoidance induces an equivalence relation on the pattern set $S_k$. For $\rho, \tau \in S_k$, we define the equivalence relation as follows: $\rho \sim_W \tau$ if and only if $|S_n(\rho)| = |S_n(\tau)|$ for all $n \geq 1.$ The equivalence classes of this relation are called Wilf classes. The main questions are determining the Wilf classes of $S_k$ and enumerating each class. We first study the Wilf classification and enumeration of each class for $S_3$ and $S_4$. We then present some new numerical results regarding the Wilf classification of pairs of patterns of length five. We define a Wilf class as small if it contains only one pair and big if it contains more than one pair. We show that there are at least 968 small Wilf classes and at most 13 big Wilf classes.

Benzer Tezler

  1. Tez No

    872820

    Generating tree method and applications to pattern-avoiding inversion sequences

    Üreteç ağaçlar yöntemi ve motif içermeyen ters-çevrim dizilerine uygulamaları

    MELİS GEZER

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Matematikİhsan Doğramacı Bilkent Üniversitesi

    Matematik Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ GÖKHAN YILDIRIM

  2. Tez No

    359744

    Karadeniz Teknik Üniversitesi Farabi Hastanesi Biyokimya Laboratuvarı test sonuçlarından veri madenciliği yolu ile örüntü çıkarma

    Pattern extraction from Karadeniz Technical University Farabi Hospital Biochemistry Laboratory medical tests using data mining techniques

    YASEMİN ZEYNEP ENGİN

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKaradeniz Teknik Üniversitesi

    Tıp Bilişimi Ana Bilim Dalı

    DOÇ. DR. KEMAL TURHAN

  3. Tez No

    447134

    Development of a framework for frequent itemset mining under multiple support thresholds

    Çoklu destek eşiklerinde sık kümeler madenciliği için uygulama iskeleti geliştirilmesi

    SADEQ HUSSEIN SALEH DARRAB

    Yüksek Lisans

    İngilizce

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİzmir Yüksek Teknoloji Enstitüsü

    Bilgisayar Mühendisliği Ana Bilim Dalı

    Assist. Prof. Dr. BELGİN ERGENÇ BOSTANOĞLU

  4. Tez No

    661390

    Sıçanlarda random paternli fleplere postoperatif lokal soğuk ve sıcak uygulamalarının flep sağkalımına etkisi

    Effects of postoperative warming and cooling on random pattern cutaneous flap survival in rats

    SEMİH YILDIZ

    Tıpta Uzmanlık

    Türkçe

    Türkçe

    2021

    Plastik ve Rekonstrüktif CerrahiSağlık Bilimleri Üniversitesi

    Plastik ve Rekonstrüktif Cerrahi Ana Bilim Dalı

    DOÇ. DR. NESİBE SİNEM ÇİLOĞLU

  5. Tez No

    509545

    Merkezi örüntü üreteci ile robot balığın üç boyutlu hareketinin akıllı denetimi

    Intelligent control of three-dimensional motion of the robotic fish with central pattern generator

    DENİZ KORKMAZ

    Doktora

    Türkçe

    Türkçe

    2018

    Elektrik ve Elektronik MühendisliğiFırat Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ CAFER BAL

Geri Dön