Block Patterns in Permutations and Words and Generalized Clusters

Download or read book Block Patterns in Permutations and Words and Generalized Clusters written by Ran Pan and published by . This book was released on 2016 with total page 189 pages. Available in PDF, EPUB and Kindle. Book excerpt: Goulden and Jackson introduced a very powerful method to study the distributions of certain consecutive patterns in permutations, words, and other combinatorial objects which is now called the cluster method. There are a number of natural classes of combinatorial objects which start with either permutations or words and add additional restrictions. These include up-down permutations, generalized Euler permutations, words without consecutive repeats, colored permutations without consecutive repeated colors, Carlitz integer compositions, Young tableaux, non-backtracking random walks, ordered set partitions, cycle structures in permutations and so on. We develop an extension of the cluster method which we call the generalized cluster method to study the distribution of certain consecutive patterns in such restricted combinatorial objects. The generalized cluster method enables us to express the generating function for distribution of a pattern in such restricted combinatorial objects in terms of so-called generalized cluster polynomials. Compared to the original problem, computing generalized cluster polynomials is usually more tractable. We also generalize a multi-variate version of both cluster method and generalized cluster method which is used to study joint distribution of multiple patterns. We use combinatorial objects mentioned above as concrete examples to demonstrate our method.