UC San Diego

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.