Occupancy Problems with Pairwise Exclusion Constraints—An Aspect of Gait Enumeration
Said H. Koozekanani, Robert B. McGhee · Journal of Cybernetics · 1972
Occupancy problems generally relate to ordered partitions of a set of objects. Often such partitions are subject to constraints which prevent certain types of objects from being placed in the same block of the partition. This paper is addressed to a particular problem of this type in which pairwise exclusion constraints are imposed. Specifically, what is sought is an enumeration of all possible partitions of a set of k pairs of objects such that no partition block contains two elements from the same pair. The results obtained are generally in the form of recursion relations. These relations have been solved completely for k ≤ 4 and partially for larger values of k. Numerical results are presented in the form of tables. An application of these tables to an enumeration of the theoretically possible gaits of bipeds, tripeds, and quadrupeds concludes the paper. It is found that the total number of such gaits is somewhat larger than previously suspected.