1 |
Pattern Avoidance in Alternating Sign MatricesJohansson, Robert January 2006 (has links)
<p>This thesis is about a generalization of permutation theory. The concept of pattern avoidance in permutation matrices is investigated in a larger class of matrices - the alternating sign matrices. The main result is that the set of alternating sign matrices avoiding the pattern 132, is counted by the large Schröder numbers. An algebraic and a bijective proof is presented. Another class is shown to be counted by every second Fibonacci number. Further research in this new area of combinatorics is discussed.</p>
|
2 |
Pattern Avoidance in Alternating Sign MatricesJohansson, Robert January 2006 (has links)
This thesis is about a generalization of permutation theory. The concept of pattern avoidance in permutation matrices is investigated in a larger class of matrices - the alternating sign matrices. The main result is that the set of alternating sign matrices avoiding the pattern 132, is counted by the large Schröder numbers. An algebraic and a bijective proof is presented. Another class is shown to be counted by every second Fibonacci number. Further research in this new area of combinatorics is discussed.
|
3 |
Permutações que evitam certos padrões / Permutations avoiding certain patternsFéres Junior, Jorge, 1961- 07 January 2014 (has links)
Orientador: José Plínio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T10:24:33Z (GMT). No. of bitstreams: 1
FeresJunior_Jorge_M.pdf: 656533 bytes, checksum: f89557654d48cebb7328f9f5ebbc8d0f (MD5)
Previous issue date: 2014 / Resumo: Nesta dissertação estudamos permutações que evitam determinados padrões. Mais especificamente, nosso foco é a contagem de tais permutações. Dentre as várias formas de descrever uma permutação, adotamos a ''representação posicional em linha'', apresentando um tratamento sistemático nesta área de padrão proibido, estudando operações, simetrias, estruturas, transformações, e principalmente, técnicas de contagem para este fim / Abstract: In this dissertation, we study permutations avoiding certain patterns. More specifically, our focus is on counting such permutations. Among the many ways to describe a permutation, we adopted the "positional representation in line" presenting a systematic treatment of this area of forbidden pattern, studying operations, symmetries, structures, transformations, and especially counting techniques for this purpose / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada
|
4 |
Métodos de Monte Carlo para amostragem de permutações com restrições e aplicações / Monte Carlo sampling of restricted permutations and aplicationsReale, Fábio Tosetto 06 July 2018 (has links)
Neste trabalho definimos o processo de exclusão simples simétrico em tempo discreto sobre grafos por meio de permutações com restrições sobre os índices dos vértices dos grafos. O processo é uma generalização das permutações dos índices do grafo completo. Apresentamos algoritmos de Monte Carlo e de amostragem sequencial por importância para amostrar permutações com restrições inspirados pelo problema análogo de calcular permanentes. Como aplicação, utilizamos esses algoritmos para estimar os tempos de relaxação do processo de exclusão simples simétrico em tempo discreto sobre grafos aleatórios densos de Erdös-Rényi com laços / In this work we define the symmetric simple exclusion process in discrete time over graphs by means of suitably restricted permutations over the labels of the vertices of the graphs. The process is a generalization of the shuffling of labels on the complete graph. Straightforward Monte Carlo and sequential importance sampling algorithms to sample restricted permutations inspired by the related problem of computing permanents are discussed. We illustrate the formalism by estimating the relaxation times of the symmetric simple exclusion process in discrete time over dense loop-augmented Erdös-Rényi random graphs
|
5 |
Métodos de Monte Carlo para amostragem de permutações com restrições e aplicações / Monte Carlo sampling of restricted permutations and aplicationsFábio Tosetto Reale 06 July 2018 (has links)
Neste trabalho definimos o processo de exclusão simples simétrico em tempo discreto sobre grafos por meio de permutações com restrições sobre os índices dos vértices dos grafos. O processo é uma generalização das permutações dos índices do grafo completo. Apresentamos algoritmos de Monte Carlo e de amostragem sequencial por importância para amostrar permutações com restrições inspirados pelo problema análogo de calcular permanentes. Como aplicação, utilizamos esses algoritmos para estimar os tempos de relaxação do processo de exclusão simples simétrico em tempo discreto sobre grafos aleatórios densos de Erdös-Rényi com laços / In this work we define the symmetric simple exclusion process in discrete time over graphs by means of suitably restricted permutations over the labels of the vertices of the graphs. The process is a generalization of the shuffling of labels on the complete graph. Straightforward Monte Carlo and sequential importance sampling algorithms to sample restricted permutations inspired by the related problem of computing permanents are discussed. We illustrate the formalism by estimating the relaxation times of the symmetric simple exclusion process in discrete time over dense loop-augmented Erdös-Rényi random graphs
|
6 |
Consecutive patterns and statistics on restricted permutationsElizalde Torrent, Sergi 16 July 2004 (has links)
El tema d'aquesta tesi és l'enumeració de permutacions amb subseqüències prohibides respecte a certs estadístics, i l'enumeració de permutacions que eviten subseqüències generalitzades.Després d'introduir algunes definicions sobre subseqüències i estadístics en permutacions i camins de Dyck, comencem estudiant la distribució dels estadístics -nombre de punts fixos' i -nombre d'excedències' en permutacions que eviten una subseqüència de longitud 3. Un dels resultats principals és que la distribució conjunta d'aquest parell de paràmetres és la mateixa en permutacions que eviten 321 que en permutacions que eviten 132. Això generalitza un teorema recent de Robertson, Saracino i Zeilberger. Demostrem aquest resultat donant una bijecció que preserva els dos estadístics en qüestió i un altre paràmetre. La idea clau consisteix en introduir una nova classe d'estadístics en camins de Dyck, basada en el que anomenem túnel.A continuació considerem el mateix parell d'estadístics en permutacions que eviten simultàniament dues o més subseqüències de longitud 3. Resolem tots els casos donant les funcions generadores corresponents. Alguns casos són generalitzats a subseqüències de longitud arbitrària. També descrivim la distribució d'aquests paràmetres en involucions que eviten qualsevol subconjunt de subseqüències de longitud 3. La tècnica principal consisteix en fer servir bijeccions entre permutacions amb subseqüències prohibides i certs tipus de camins de Dyck, de manera que els estadístics en permutacions que considerem corresponen a estadístics en camins de Dyck que són més fàcils d'enumerar.Tot seguit presentem una nova família de bijeccions del conjunt de camins de Dyck a sí mateix, que envien estadístics que apareixen en l'estudi de permutacions amb subseqüències prohibides a estadístics clàssics en camins de Dyck, la distribució dels quals s'obté fàcilment. En particular, això ens dóna una prova bijectiva senzilla de l'equidistribució de punts fixos en les permutacions que eviten 321 i en les que eviten 132. A continuació donem noves interpretacions dels nombres de Catalan i dels nombres de Fine. Considerem una classe de permutacions definida en termes d'aparellaments de 2n punts en una circumferència sense creuaments. N'estudiem l'estructura i algunes propietats, i donem la distribució de diversos estadístics en aquests permutacions.En la següent part de la tesi introduïm una noció diferent de subseqüències prohibides, amb el requeriment que els elements que formen la subseqüència han d'aparèixer en posicions consecutives a la permutació. Més en general, estudiem la distribució del nombre d'ocurrències de subparaules (subseqüències consecutives) en permutacions. Resolem el problema en diversos casos segons la forma de la subparaula, obtenint-ne les funcions generadores exponencials bivariades corresponents com a solucions de certes equacions diferencials lineals. El mètode està basat en la representació de permutacions com a arbres binaris creixents i en mètodes simbòlics.La part final tracta de subseqüències generalitzades, que extenen tant la noció de subseqüències clàssiques com la de subparaules. Per algunes subseqüències obtenim nous resultats enumeratius. Finalment estudiem el comportament assimptòtic del nombre de permutacions de mida n que eviten una subseqüència generalitzada fixa quan n tendeix a infinit. També donem fites inferiors i superiors en el nombre de permutacions que eviten certes subseqüències.
|
Page generated in 0.1391 seconds