subject:(Dyck paths)

Queen Mary, University of London

1. Mortimer, Paul. Lattice path enumeration on restricted domains.

Degree: PhD, 2016, Queen Mary, University of London

URL: http://qmro.qmul.ac.uk/xmlui/handle/123456789/12992 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.775258

► This thesis concerns the enumeration and structural properties of lattice paths. The study of Dyck paths and their characteristics is a classical combinatorial subject. In… (more)

Subjects/Keywords: Mathematics; Dyck paths; algebraic combinatorics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Mortimer, P. (2016). Lattice path enumeration on restricted domains. (Doctoral Dissertation). Queen Mary, University of London. Retrieved from http://qmro.qmul.ac.uk/xmlui/handle/123456789/12992 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.775258

Chicago Manual of Style (16^th Edition):

Mortimer, Paul. “Lattice path enumeration on restricted domains.” 2016. Doctoral Dissertation, Queen Mary, University of London. Accessed January 15, 2021. http://qmro.qmul.ac.uk/xmlui/handle/123456789/12992 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.775258.

MLA Handbook (7^th Edition):

Mortimer, Paul. “Lattice path enumeration on restricted domains.” 2016. Web. 15 Jan 2021.

Vancouver:

Mortimer P. Lattice path enumeration on restricted domains. [Internet] [Doctoral dissertation]. Queen Mary, University of London; 2016. [cited 2021 Jan 15]. Available from: http://qmro.qmul.ac.uk/xmlui/handle/123456789/12992 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.775258.

Council of Science Editors:

Mortimer P. Lattice path enumeration on restricted domains. [Doctoral Dissertation]. Queen Mary, University of London; 2016. Available from: http://qmro.qmul.ac.uk/xmlui/handle/123456789/12992 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.775258

2. Manes, Konstantinos. Απαρίθμηση προτύπων σε μονοπάτια Dyck και Grand-Dyck.

Degree: 2014, University of Piraeus (UNIPI); Πανεπιστήμιο Πειραιώς

URL: http://hdl.handle.net/10442/hedi/34603

►

The Catalan numbers are considered to be the second most significant numbers in Combinatorics, after the binomial coefficients, because they appear frequently in various combinatorial… (more)

▼

The Catalan numbers are considered to be the second most significant numbers in Combinatorics, after the binomial coefficients, because they appear frequently in various combinatorial problems. Professor R. Stanley maintains a record including more than 200 different combinatorial objects which are enumerated by the Catalan numbers, therefore are structurally equivalent. Perhaps, the most popular among these are Dyck paths (or words) and binary trees.Dyck paths are the main object studied in this dissertation. They have a very simple geometrical representation and for that reason they are suitable for studying properties which are then translated into properties of other objects in the Catalan family.Moreover, by introducing various restrictions (parameters), we obtain special categories of Dyck paths which are often equivalent to other known objects, so that any results are also extended to these objects.In this dissertation, we mainly study the parameter “number of occurrences of the string t”, where a string is considered to be any binary word. In the first chapter, the basic definitions and necessary mathematical tools are extensively presented.In the second chapter, we study the parameter “number of occurrences of t at height j”, that is we enumerate Dyck paths, with respect to their length and number of occurrences of t at height j. The result is expressed via the corresponding generating function for any binary word t.In the third chapter, we study the parameters “number of occurrences of t” and “number of occurrences of t at height at least j” in Dyck paths. We again obtain the results via the corresponding generating function for the cases where t is a Dyck prefix or a Dyck suffix and for some other general cases as well. In the fourth chapter, we study the parameter “number of occurrences of t” in Grand-Dyck paths, where t has length 3. In addition, by considering the auxiliary parameter “number of up-steps below zero level”, we obtain in some cases refinements of the Chung-Feller theorem. In the fifth chapter, three new parameters of Dyck paths, not related to strings, are studied and complete enumerative results are obtained. These parameters are defined by refining the well known parameter “number of peaks”. In the sixth chapter, exact as well as asymptotic formulas are presented, for the mean value and variance of the parameters studied in previous chapters.

Οι αριθμοί Catalan θεωρούνται ως οι πιο σημαντικοί αριθμοί της Συνδυαστικής, μετά τους διωνυμικούς συντελεστές, λόγω της εντυπωσιακά συχνής εμφάνισής τους σε διάφορα προβλήματα. Ενδεικτικά, ο R. Stanley διατηρεί αρχείο με περισσότερα από 200 διαφορετικά σύνολα συνδυαστικών αντικείμενων που απαριθμούνται από τους αριθμούς Catalan και άρα είναι πληθικά αλλά και δομικά ισοδύναμα. Τα πιο διαδεδομένα από αυτά είναι ίσως τα μονοπάτια (λέξεις) Dyck και τα δυαδικά δένδρα.Το κεντρικό αντικείμενο μελέτης της διατριβής αυτής είναι τα μονοπάτια Dyck, τα οποία αποτελούν απλά μια αναπαράσταση στο επίπεδο των λέξεων Dyck. Λόγω της απλής και εύληπτης γεωμετρικής…

Subjects/Keywords: Μονοπάτια Dyck; Μονοπάτια Grand-Dyck; Αριθμοί Catalan; ΓΕΝΝΗΤΡΙΕΣ ΣΥΝΑΡΤΗΣΕΙΣ; Συνδυαστική απαρίθμηση; Τύπος αντιστροφής Lagrange; Dyck paths; Grand-Dyck paths; Catalan numbers; GENERATING FUNCTIONS; Combinatorial enumeration; Lagrange inversion formula

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Manes, K. (2014). Απαρίθμηση προτύπων σε μονοπάτια Dyck και Grand-Dyck. (Thesis). University of Piraeus (UNIPI); Πανεπιστήμιο Πειραιώς. Retrieved from http://hdl.handle.net/10442/hedi/34603

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Manes, Konstantinos. “Απαρίθμηση προτύπων σε μονοπάτια Dyck και Grand-Dyck.” 2014. Thesis, University of Piraeus (UNIPI); Πανεπιστήμιο Πειραιώς. Accessed January 15, 2021. http://hdl.handle.net/10442/hedi/34603.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Manes, Konstantinos. “Απαρίθμηση προτύπων σε μονοπάτια Dyck και Grand-Dyck.” 2014. Web. 15 Jan 2021.

Vancouver:

Manes K. Απαρίθμηση προτύπων σε μονοπάτια Dyck και Grand-Dyck. [Internet] [Thesis]. University of Piraeus (UNIPI); Πανεπιστήμιο Πειραιώς; 2014. [cited 2021 Jan 15]. Available from: http://hdl.handle.net/10442/hedi/34603.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Manes K. Απαρίθμηση προτύπων σε μονοπάτια Dyck και Grand-Dyck. [Thesis]. University of Piraeus (UNIPI); Πανεπιστήμιο Πειραιώς; 2014. Available from: http://hdl.handle.net/10442/hedi/34603

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Stellenbosch University

3. Selkirk, Sarah Jane. On a generalisation of k-Dyck paths.

Degree: MSc, Mathematical Sciences, 2019, Stellenbosch University

URL: http://hdl.handle.net/10019.1/107091

►

ENGLISH ABSTRACT: (Refer to full text abstract for symbols that did not transfer correctly). We consider a family of non-negative lattice paths consisting of the… (more)

▼

ENGLISH ABSTRACT: (Refer to full text abstract for symbols that did not transfer correctly). We consider a family of non-negative lattice paths consisting of the step set f(1; 1); (1;􀀀k)g called k-Dyck paths, which are enumerated by the generalised Catalan numbers 1 (k+1)n+1 􀀀(k+1)n+1 n . By removing the non-negativity condition but restricting the path to stay above the line y = 􀀀t we obtain a family of lattice paths called kt-Dyck paths which are enumerated by `generalised generalised Catalan numbers t + 1 (k + 1)n + t + 1 (k + 1)n + t + 1 n : We provide proofs of the enumeration of these paths by means of a bijection, the kernel method, the cycle lemma, and the symbolic method. Analysis of parameters associated with the paths is also performed using symbolic equations { particularly the number of peaks, the number of valleys, and the number of returns. These kt-Dyck paths nd application in enumerating a family of walks in the quarter plane (Z 0 Z 0) with step set f(1; 1); (1;􀀀k +1); (􀀀k; 0)g. Such walks can be decomposed into ordered pairs of kt-Dyck paths and thus their enumeration can be proved via a simple bijection. Through this bijection some parameters in kt-Dyck paths are preserved. Finally, we discuss two different families of lattice paths, S-Motzkin and T- Motzkin paths, which are related to kt-Dyck paths when k = 2 along with t = 0 and t = 1. We provide bijections between these paths and other combinatorial objects, and perform analysis of parameters in these paths.

AFRIKAANSE OPSOMMING: (Verwys na volteks opsomming vir simbole wat nie korrek oorgeskryf het nie). Ons beskou 'n familie van nie-negatiewe roosterpaaie wat bestaan uit die stap- versameling f(1; 1); (1;􀀀k)g genoem k-Dyck paaie, wat deur die veralgemeende Catalan getalle, 1 (k+1)n+1 􀀀(k+1)n+1 n , getel word. Deur die nie-negatiwiteitsvereiste te verwyder, maar die pad tot bokant die lyn y = 􀀀t te beperk kry ons 'n fami- lie roosterpaaie genaamd kt-Dyck paaie wat getel word deur `veralgemeende' veralgemeende Catalan getalle t + 1 (k + 1)n + t + 1 (k + 1)n + t + 1 n : Ons lewer 'n bewys van die aftelling van hierdie paaie deur middel van 'n bijeksie, die kernmetode, die sikluslemma en die simboliese metode. Analise van parameters wat met die paaie geassosieer word, word ook uitgevoer met behulp van simboliese vergelykings { veral die aantal pieke, die aantal valleie en die aantal terugkomste. Hierdie kt-Dyck paaie vind 'n toepassing in 'n familie van wandelinge in die kwartvlak (Z 0 Z 0) met stapversameling f(1; 1); (1;􀀀k + 1); (􀀀k; 0)g. Sulke wandelinge kan ontleed word in geordende pare kt-Dyck paaie en dus kan hul aftelling deur middel van 'n eenvoudige bijeksie bewys word. Deur hierdie bijeksie word 'n paar parameters in kt-Dyck paaie bewaar. Laastens bespreek ons twee verskillende families van roosterpaaie, S-Motzkin en T-Motzkin paaie, wat verband hou met kt-Dyck paaie wanneer k = 2 saam met t = 0 en t = 1. Ons bied bijeksies tussen hierdie paaie en ander kom- binatoriese voorwerpe,…

Advisors/Committee Members: Wagner, Stephan, Prodinger, Helmut, Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences..

Subjects/Keywords: Combinatorial analysis; Lattice paths; Combinational enumeration problems; Dyck paths; Catalan numbers (Mathematics); UCTD

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Selkirk, S. J. (2019). On a generalisation of k-Dyck paths. (Masters Thesis). Stellenbosch University. Retrieved from http://hdl.handle.net/10019.1/107091

Chicago Manual of Style (16^th Edition):

Selkirk, Sarah Jane. “On a generalisation of k-Dyck paths.” 2019. Masters Thesis, Stellenbosch University. Accessed January 15, 2021. http://hdl.handle.net/10019.1/107091.

MLA Handbook (7^th Edition):

Selkirk, Sarah Jane. “On a generalisation of k-Dyck paths.” 2019. Web. 15 Jan 2021.

Vancouver:

Selkirk SJ. On a generalisation of k-Dyck paths. [Internet] [Masters thesis]. Stellenbosch University; 2019. [cited 2021 Jan 15]. Available from: http://hdl.handle.net/10019.1/107091.

Council of Science Editors:

Selkirk SJ. On a generalisation of k-Dyck paths. [Masters Thesis]. Stellenbosch University; 2019. Available from: http://hdl.handle.net/10019.1/107091

Carnegie Mellon University

4. Allen, Emily. Combinatorial Interpretations Of Generalizations Of Catalan Numbers And Ballot Numbers.

Degree: 2014, Carnegie Mellon University

URL: http://repository.cmu.edu/dissertations/366

► The super Catalan numbers T(m,n) = (2m)!(2n)!=2m!n!(m+n)! are integers which generalize the Catalan numbers. Since 1874, when Eugene Catalan discovered these numbers, many mathematicians have… (more)

Subjects/Keywords: combinatorics; lattice paths; Dyck path; Catalan numbers; Ballot numbers; super Catalan numbers

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Allen, E. (2014). Combinatorial Interpretations Of Generalizations Of Catalan Numbers And Ballot Numbers. (Thesis). Carnegie Mellon University. Retrieved from http://repository.cmu.edu/dissertations/366

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Allen, Emily. “Combinatorial Interpretations Of Generalizations Of Catalan Numbers And Ballot Numbers.” 2014. Thesis, Carnegie Mellon University. Accessed January 15, 2021. http://repository.cmu.edu/dissertations/366.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Allen, Emily. “Combinatorial Interpretations Of Generalizations Of Catalan Numbers And Ballot Numbers.” 2014. Web. 15 Jan 2021.

Vancouver:

Allen E. Combinatorial Interpretations Of Generalizations Of Catalan Numbers And Ballot Numbers. [Internet] [Thesis]. Carnegie Mellon University; 2014. [cited 2021 Jan 15]. Available from: http://repository.cmu.edu/dissertations/366.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Allen E. Combinatorial Interpretations Of Generalizations Of Catalan Numbers And Ballot Numbers. [Thesis]. Carnegie Mellon University; 2014. Available from: http://repository.cmu.edu/dissertations/366

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of California – San Diego

5. Qiu, Dun. Combinatorics in the Rational Shuffle Theorem and the Delta Conjecture.

Degree: Mathematics, 2019, University of California – San Diego

URL: http://www.escholarship.org/uc/item/07v3n1wj

► The Classical Shuffle Conjecture proposed by Haglund, Haiman, Loehr, Remmel and Ulyanov gives a well-studied combinatorial expression for the bigraded Frobenius characteristic of Sn-module of… (more)

Subjects/Keywords: Mathematics; Catalan numbers; Dyck paths; Macdonald polynomials; ordered set partitions; parking functions; symmetric functions

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Qiu, D. (2019). Combinatorics in the Rational Shuffle Theorem and the Delta Conjecture. (Thesis). University of California – San Diego. Retrieved from http://www.escholarship.org/uc/item/07v3n1wj

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Qiu, Dun. “Combinatorics in the Rational Shuffle Theorem and the Delta Conjecture.” 2019. Thesis, University of California – San Diego. Accessed January 15, 2021. http://www.escholarship.org/uc/item/07v3n1wj.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Qiu, Dun. “Combinatorics in the Rational Shuffle Theorem and the Delta Conjecture.” 2019. Web. 15 Jan 2021.

Vancouver:

Qiu D. Combinatorics in the Rational Shuffle Theorem and the Delta Conjecture. [Internet] [Thesis]. University of California – San Diego; 2019. [cited 2021 Jan 15]. Available from: http://www.escholarship.org/uc/item/07v3n1wj.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Qiu D. Combinatorics in the Rational Shuffle Theorem and the Delta Conjecture. [Thesis]. University of California – San Diego; 2019. Available from: http://www.escholarship.org/uc/item/07v3n1wj

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Arizona

6. McNicholas, Erin Mari. Embedded Tree Structures and Eigenvalue Statistics of Genus Zero One-Face Maps .

Degree: 2006, University of Arizona

URL: http://hdl.handle.net/10150/194030

► Using numerical simulations and combinatorics, this dissertation focuses on connections between random matrix theory and graph theory.We examine the adjacency matrices of three-regular graphs representing… (more)

▼ Using numerical simulations and combinatorics, this dissertation focuses on connections between random matrix theory and graph theory.We examine the adjacency matrices of three-regular graphs representing one-face maps. Numerical studies have revealed that the limiting eigenvalue statistics of these matrices are the same as those of much larger, and more widely studied classes of random matrices. In particular, the eigenvalue density is described by the McKay density formula, and the distribution of scaled eigenvalue spacings appears to be that of the Gaussian Orthogonal Ensemble (GOE).A natural question is whether the eigenvalue statistics depend on the genus of the underlying map. We present an algorithm for generating random three-regular graphs representing genus zero one-face maps. Our numerical studies of these three-regular graphs have revealed that their eigenvalue statistics are strikingly different from those of three-regular graphs representing maps of higher genus. While our results indicate that there is a limiting eigenvalue density formula in the genus zero case, it is not described by any established density function. Furthermore, the scaled eigenvalue spacings appear to be described by the exponential distribution function, not the GOE spacing distribution.The embedded graph of a genus zero one-face map is a planar tree, and there is a correlation between its vertices and the primitive cycles of the associated three-regular graph. The second half of this dissertation examines the structure of these embedded planar trees. In particular, we show how the Dyck path representation can be used to recast questions about the probabilistic structure of random planar trees into straightforward counting problems. Using this Dyck path approach, we find:1. the expected number of degree k vertices adjacent to j degree d vertices in a random planar tree, 2. the structure of the planar tree's adjacency matrix under a natural labeling of the vertices, and 3. an explanation for the existence of eigenvalues with multiplicity greater than one in the tree's spectrum. Advisors/Committee Members: Flaschka, Hermann (advisor), Kenneth, McLaughlin (committeemember), Grove, Larry (committeemember), Flaschka, Hermann (committeemember).

Subjects/Keywords: planar trees; Dyck paths; eigenvalue statistics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

McNicholas, E. M. (2006). Embedded Tree Structures and Eigenvalue Statistics of Genus Zero One-Face Maps . (Doctoral Dissertation). University of Arizona. Retrieved from http://hdl.handle.net/10150/194030

Chicago Manual of Style (16^th Edition):

McNicholas, Erin Mari. “Embedded Tree Structures and Eigenvalue Statistics of Genus Zero One-Face Maps .” 2006. Doctoral Dissertation, University of Arizona. Accessed January 15, 2021. http://hdl.handle.net/10150/194030.

MLA Handbook (7^th Edition):

McNicholas, Erin Mari. “Embedded Tree Structures and Eigenvalue Statistics of Genus Zero One-Face Maps .” 2006. Web. 15 Jan 2021.

Vancouver:

McNicholas EM. Embedded Tree Structures and Eigenvalue Statistics of Genus Zero One-Face Maps . [Internet] [Doctoral dissertation]. University of Arizona; 2006. [cited 2021 Jan 15]. Available from: http://hdl.handle.net/10150/194030.

Council of Science Editors:

McNicholas EM. Embedded Tree Structures and Eigenvalue Statistics of Genus Zero One-Face Maps . [Doctoral Dissertation]. University of Arizona; 2006. Available from: http://hdl.handle.net/10150/194030

University of Vienna

7. Stump, Christian. q,t-Fuß-Catalan numbers for finite reflection groups.

Degree: 2008, University of Vienna

URL: http://othes.univie.ac.at/1091/

►

Im Typ A können die q,t-Catalan Zahlen und die q,t-Fuß-Catalan Zahlen als bigraduierte Hilbertreihe einesModuls über der symmetrischen Gruppe definiert werden. Wir verallgemeinern diese Konstruktion… (more)

▼

Im Typ A können die q,t-Catalan Zahlen und die q,t-Fuß-Catalan Zahlen als bigraduierte Hilbertreihe einesModuls über der symmetrischen Gruppe definiert werden. Wir verallgemeinern diese Konstruktion auf (endliche) komplexe Spiegelungsgruppen und beschreiben einige vermutete algebraische und kombinatorische Eigenschaften dieser symmetrischen Polynome in q und t mit nicht-negativen ganzzahligen Koeffizienten. Weiterhin definieren wir q-Fuß-Catalan Zahlen kombinatorisch als Erzeugendenfunktion einer Statistik auf dem verallgemeinerten Shi-Gefüge. Diese scheinen die Spezialisierung t =1 der q,t-Fuß-Catalan Zahlen zu beschreiben. Diese neue Statistik führt zu einer Definition von Catalan-Pfaden im Typ B, welche wir auf weitere Eigenschaften hin untersuchen. Unter anderem finden wir für die Typen A und B Bijektionen zwischen Catalan-Pfaden, nicht-kreuzenden Partitionen und Coxeter-sortierbaren Elementen, die Fragestellungen bzgl. der q,t-Catalan Zahlen von Catalan-Pfaden zu nicht-keuzenden Partitionen und Coxeter-sortierbaren Elementen transferiert. Schließlich präsentieren wir einige Ideen, wie die q,t-Fuß-Catalan Zahlen mit Moduln, die im Kontext von rationalen Cherednik-Algebren auftreten, in Beziehung stehen könnten. Dabei verallgemeinern wir bereits untersuchte Verbindungen.

In type A, the q,t-Catalan numbers and the q,t-Fuß-Catalan numbers can be defined as a bigraded Hilbert series of a module associated to the symmetric group. We generalize this construction to (finite) complex reflection groups and exhibit many nice conjectured algebraic and combinatorial properties of these symmetric polynomials in q and t with non-negative integer coefficients. We combinatorially define q-Fuß-Catalan numbers as the generating function of a statistic on the extended Shi arrangement which seem to describe the specialization t =1 in the q, t-Fuß-Catalan numbers. The exhibited statistic yields a definition of Catalan paths of type B of which we further investigate several properties. In particular, we define for types A and B bijections between Catalan paths, non-crossing partitions and Coxeter sortable elements which transfer arising questions concerning the q,t-Catalan numbers from Catalan paths to non-crossing partitions and to Coxeter sortable elements. Finally, we present several ideas how the q,t-Fuß-Catalan numbers could be related to some graded Hilbert series of modules arising in the context of rational Cherednik algebras and thereby generalize known connections.

Subjects/Keywords: 31.12 Kombinatorik, Graphentheorie; 31.23 Ideale, Ringe, Moduln, Algebren; Catalan Zahlen / Dyck-Pfade / Spiegelungsgruppen / nicht-kreuzende Partitionen / Coxeter-sortierbare Elemente / nicht-schachtelnde Partitionen / Shi-Gefüge; Catalan numbers / Dyck paths / reflection groups / non-crossing partitions / Coxeter sortable elements / non-nesting partitions / Shi arrangement

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Stump, C. (2008). q,t-Fuß-Catalan numbers for finite reflection groups. (Thesis). University of Vienna. Retrieved from http://othes.univie.ac.at/1091/

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Stump, Christian. “q,t-Fuß-Catalan numbers for finite reflection groups.” 2008. Thesis, University of Vienna. Accessed January 15, 2021. http://othes.univie.ac.at/1091/.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Stump, Christian. “q,t-Fuß-Catalan numbers for finite reflection groups.” 2008. Web. 15 Jan 2021.

Vancouver:

Stump C. q,t-Fuß-Catalan numbers for finite reflection groups. [Internet] [Thesis]. University of Vienna; 2008. [cited 2021 Jan 15]. Available from: http://othes.univie.ac.at/1091/.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Stump C. q,t-Fuß-Catalan numbers for finite reflection groups. [Thesis]. University of Vienna; 2008. Available from: http://othes.univie.ac.at/1091/

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Universitat Politècnica de Catalunya

8. Elizalde Torrent, Sergi. Consecutive patterns and statistics on restricted permutations.

Degree: 2004, Universitat Politècnica de Catalunya

URL: http://hdl.handle.net/10803/5839

► 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… (more)

▼ 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… Advisors/Committee Members: Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística, [email protected] (authoremail), false (authoremailshow), Noy, Marc (director).

Subjects/Keywords: consecutive patterns; tunnel; statistics; dyck paths; pattern avoidance; permutations; bijection; generalized patterns; restricted permutation; 1202. Anàlisi i anàlisi funcional - 1209. Estadística - 1201. Algebra - 1299. Altres especialitats m; 519.1

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Elizalde Torrent, S. (2004). Consecutive patterns and statistics on restricted permutations. (Thesis). Universitat Politècnica de Catalunya. Retrieved from http://hdl.handle.net/10803/5839

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Elizalde Torrent, Sergi. “Consecutive patterns and statistics on restricted permutations.” 2004. Thesis, Universitat Politècnica de Catalunya. Accessed January 15, 2021. http://hdl.handle.net/10803/5839.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Elizalde Torrent, Sergi. “Consecutive patterns and statistics on restricted permutations.” 2004. Web. 15 Jan 2021.

Vancouver:

Elizalde Torrent S. Consecutive patterns and statistics on restricted permutations. [Internet] [Thesis]. Universitat Politècnica de Catalunya; 2004. [cited 2021 Jan 15]. Available from: http://hdl.handle.net/10803/5839.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Elizalde Torrent S. Consecutive patterns and statistics on restricted permutations. [Thesis]. Universitat Politècnica de Catalunya; 2004. Available from: http://hdl.handle.net/10803/5839

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Victoria

9. Williams, Aaron Michael. Shift gray codes.

Degree: Dept. of Computer Science, 2009, University of Victoria

URL: http://hdl.handle.net/1828/1966

► Combinatorial objects can be represented by strings, such as 21534 for the permutation (1 2) (3 5 4), or 110100 for the binary tree corresponding… (more)

▼ Combinatorial objects can be represented by strings, such as 21534 for the permutation (1 2) (3 5 4), or 110100 for the binary tree corresponding to the balanced parentheses (()()). Given a string s = s1 s2 sn, the right-shift operation shift(s, i, j) replaces the substring si si+1..sj by si+1..sj si. In other words, si is right-shifted into position j by applying the permutation (j j−1 .. i) to the indices of s. Right-shifts include prefix-shifts (i = 1) and adjacent-transpositions (j = i+1). A fixed-content language is a set of strings that contain the same multiset of symbols. Given a fixed-content language, a shift Gray code is a list of its strings where consecutive strings differ by a shift. This thesis asks if shift Gray codes exist for a variety of combinatorial objects. This abstract question leads to a number of practical answers. The first prefix-shift Gray code for multiset permutations is discovered, and it provides the first algorithm for generating multiset permutations in O(1)-time while using O(1) additional variables. Applications of these results include more efficient exhaustive solutions to stacker-crane problems, which are natural NP-complete traveling salesman variants. This thesis also produces the fastest algorithm for generating balanced parentheses in an array, and the first minimal-change order for fixed-content necklaces and Lyndon words. These results are consequences of the following theorem: Every bubble language has a right-shift Gray code. Bubble languages are fixed-content languages that are closed under certain adjacent-transpositions. These languages generalize classic combinatorial objects: k-ary trees, ordered trees with fixed branching sequences, unit interval graphs, restricted Schr oder and Motzkin paths, linear-extensions of B-posets, and their unions, intersections, and quotients. Each Gray code is circular and is obtained from a new variation of lexicographic order known as cool-lex order. Gray codes using only shift(s, 1, n) and shift(s, 1, n−1) are also found for multiset permutations. A universal cycle that omits the last (redundant) symbol from each permutation is obtained by recording the first symbol of each permutation in this Gray code. As a special case, these shorthand universal cycles provide a new fixed-density analogue to de Bruijn cycles, and the first universal cycle for the "middle levels" (binary strings of length 2k + 1 with sum k or k + 1). Advisors/Committee Members: Ruskey, Frank (supervisor), Myrvold, W. J. (supervisor).

Subjects/Keywords: shorthand universal cycles; combinatorial generation; minimal-change order; loopless algorithm; efficient algorithm; combinations; multiset permutations; balanced parentheses; Dyck words; Catalan paths; Schroder paths; Motzkin words; linear-extensions; posets; connected unit interval graphs; inversions; binary trees; k-ary trees; ordered trees with fixed branching sequence; Lyndon words; pre-necklaces; theoretical computer science; discrete mathematics; combinatorics; brute forcs; de Bruijn cycles; bubble languages; cool-lex order; lexicographic order; combinatorial enumeration; stacker-crane problem; traveling salesman problem; middle levels; fixed-density de Bruijn cycle; fixed-content; UVic Subject Index::Sciences and Engineering::Applied Sciences::Computer science; UVic Subject Index::Sciences and Engineering::Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Williams, A. M. (2009). Shift gray codes. (Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/1966

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Williams, Aaron Michael. “Shift gray codes.” 2009. Thesis, University of Victoria. Accessed January 15, 2021. http://hdl.handle.net/1828/1966.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Williams, Aaron Michael. “Shift gray codes.” 2009. Web. 15 Jan 2021.

Vancouver:

Williams AM. Shift gray codes. [Internet] [Thesis]. University of Victoria; 2009. [cited 2021 Jan 15]. Available from: http://hdl.handle.net/1828/1966.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Williams AM. Shift gray codes. [Thesis]. University of Victoria; 2009. Available from: http://hdl.handle.net/1828/1966

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Open Access Theses and Dissertations