Generating tree method and applications to pattern-avoiding inversion sequences
Üreteç ağaçlar yöntemi ve motif içermeyen ters-çevrim dizilerine uygulamaları
- Tez No: 872820
- Danışmanlar: DR. ÖĞR. ÜYESİ GÖKHAN YILDIRIM
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Aritmetik diziler, Fibonacci dizileri, Arithmetic sequences, Fibonacci sequences
- Yıl: 2024
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Uzunluğu n olan bir ters-çevrim dizisi, her 0 ≤ i ≤ n için 0 ≤ ei < i şartını sağlayan e = e1 · · · en şeklinde verilmiş bir tamsayı dizisidir. Uzunluğu n olan ters-çevrim dizileri kümesi In ile gösterilir. Uzunluğu k olan motifler, {0, 1, 2, . . . , k − 1} alfabesi üzerinde verilmiş kelimeler ile temsil edilir. Verilen k uzunluğunda bir τ motifi için, uzunluğu n olan bir ters-çevrim dizisi e ∈ In, τ ile aynı göreceli sıralamaya sahip k uzunluğunda bir alt-dizi içeriyorsa, motifi içeriyor deriz. Aksi takdirde, bu ters-çevrim dizisi bu motifi içermez. Verilen bir τ motifi için, τ 'yu içermeyen n uzunluğundaki ters-çevrim dizileri kümesi In(τ) ile gösterilir. Öncelikle uzunluğu 3 olan motifleri içermeyen ters-çevrim dizilerinin nasıl sayıldığını inceliyoruz. Sonrasında, verilen daha genel motifler için, motif içermeyen ters-çevrim dizilerini saymak için üreteç ağaçlar ve çekirdek yöntemlerini çalışıyoruz. Sonra, motif içermeyen ters-çevrim dizileri için örnekleme algoritması veriyoruz ve bunu bazı motiflere uyguluyoruz. Bu algoritma ile yaptığımız çalışmalara dayanarak, belirli motifleri içermeyen ters- çevrim dizilerinin bazı istatistikleri üzerine çalışıyoruz. Bu istatistikler: sıfır olan elemanların sayısı, tekrar eden elemanların sayısı, tekrar etmeyen elemanların sayısı, soldan sağa en büyük olan elemanların sayısı ve dizinin en büyük elemanıdır. Son olarak In(0312) ve In(0321) kümeleri arasında birebir, örten ve bu istatistikleri koruyan bir fonksiyon olduğunu gösteriyoruz.
Özet (Çeviri)
An inversion sequence of length n is an integer sequence e = e1 · · · en such that 0 ≤ ei < i for each 0 ≤ i ≤ n. We use In to denote the set of inversion sequences of length n. Let [k] := {0, 1, · · · , k − 1} denote the alphabet and τ be a word of length k over this alphabet. A pattern of length k is simply a word over the alphabet [k]. We say an inversion sequence e ∈ In contains the pattern τ of length k if it contains a sub-sequence of length k that is order isomorphic to τ ; otherwise, e avoids the pattern τ . For a given pattern τ , we use In(τ ) to denote the set of all τ -avoiding inversion sequences of length n. Firstly, we review the enumeration of inversion sequences that avoid patterns of length three. We then study an enumeration method based on generating trees and the kernel method to enumerate pattern-avoiding inversion sequences for general patterns. Then, we provide sampling algorithms for pattern-avoiding inversion sequences and apply them to some specific patterns. Based on extensive simulations, we study some statistics such as the number of zeros, the number of distinct elements, the number of repeated elements, and the maximum elements. Finally, we present a bijection between In(0312) and In(0321) that preserves these statistics.
Benzer Tezler
- Realization of transmitter and receiver clock generation units and channel switching unit in a modified analog radio relay
Değiştirilen bir analog radyodaki verici ve alıcı saat üretimi birimleri ve kanal anahtarlama biriminin gerçekleştirilmesi
AYHAN BÜYÜKSEMERCİ
Yüksek Lisans
İngilizce
1987
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT AŞKAR
- New algorithms and techniques for microprocessor-controlled PWM induction drives
Başlık çevirisi yok
OSMAN KÜKRER
Doktora
İngilizce
1987
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. H. BÜLENT ERTAN
- Barajların hacim-verim ilişkisi üzerine bir araştırma
Başlık çevirisi yok
MEHMET KILIÇARSLAN
Yüksek Lisans
Türkçe
1987
İnşaat MühendisliğiÇukurova Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. TEFARUK HAKTANIR
- Akaryakıtla çalışan endüstriyel tav fırınlarında yanma, sıcaklık ve basıncın optimum kontrolu
Optimum control of combustion temperature and pressure in industrial tempering furnaces working with fuel-oil
MEHMET EROĞLU
Yüksek Lisans
Türkçe
1987
Makine MühendisliğiGazi ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. YÜCEL ERCAN
- Bornova ekolojik koşullarında bazı haşhaş çeşitlerinin verim ve kaliteleri üzerinde araştırmalar
The Investigations on the yield and qualities of some popy vasied Bornova ecological conditions
HAMDİ AYGÜN
Yüksek Lisans
Türkçe
1985
ZiraatEge ÜniversitesiTarla Bitkileri Ana Bilim Dalı
PROF. DR. ŞÜKRÜ HAZIM EMİROĞLU