Premium
An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
Author(s) -
Goulden I. P.,
Jackson D. M.
Publication year - 1979
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-20.3.567
Subject(s) - inversion (geology) , mathematics , cluster (spacecraft) , combinatorics , computer science , geology , paleontology , structural basin , programming language
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.