Block patterns in permutations and words and generalized clusters

Goulden and Jackson introduced a very powerful method to study the distributions ofcertain consecutive patterns in permutations, words, and other combinatorial objects which isnow called the cluster method. There are a number of natural classes of combinatorial objectswhich start with either permutations or words and add additional restrictions. These includeup-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 ofthe cluster method which we call the generalized cluster method to study the distribution ofcertain 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