An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences

Abstract

Certain enumeration problems may be expressed in terms of sequences possessing a specified number of subsequences which are elements of a prescribed set of distinguished sequences. We obtain an inversion theorem which expresses the required generating function in terms of one connected with the set of overlapping distinguished sequences called clusters. Techniques are given for determining the cluster generating function both in the general case and in the case in which combinatorial methods are more effective. By specialising the set of distinguished sequences we may solve a number of classical permutation and sequence problems. A number of other examples is also given.