UC San Diego
Block patterns in permutations and words and generalized clusters
- Author(s): Pan, Ran
- Advisor(s): Remmel, Jeffrey Brian
- et al.
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.