A Formal Calculus for the Enumerative System of Sequences—I. Combinatorial Theorems
The enumeration of sequences plays an important part in combinatorial enumeration since sequences may be used as a means for encoding combinatorial structures. In the main, the enumeration of sequences has been treated by a collection of methods individually applied in particular cases. We present here a uniform constructive method for dealing with a large class of sequence problems. We obtain the generating function as the trace of an expression involving certain incidence matrices, expressions which are obtainable immediately from the combinatorial structure of a problem. The method relies on certain properties of matrices whose rank is equal to one. We demonstrate that these properties may be used to derive the required generating functions explicitly or, in more complex cases, as solutions to systems of linear equations. Results for permutations may be derived from those for sequences, and in certain frequently encountered special cases this operation may be carried out by a straightforward substitution. Applications of the method presented here will be given in Part II.
No Supplementary Data
No Article Media
Document Type: Research Article
Affiliations: University of Waterloo
Publication date: October 1, 1979