APPENDIX C

PERMUTATIONS, COMBINATIONS, AND RELATED TOPICS

      Table C-l. Permutations and Partitions

      Table C-2. Combinations and Samples

      Table C-3. Occupancy of Cells or States

      C-l. Use of Generating Functions

      C-2. Polya's Counting Theorem

      References and Bibliography

Refer to Sec. 1.2-4 and Table 21.5-1 for definitions and properties of factorials and binomial coefficients. Stirling's formula (Sec. 21.4-2) is useful in numerical computations.

Table C-1. Permutaions and Partitions

Table C-2. Combinations and Samples (see also Table C-3 and Sec. 18.7-2).

Each formula holds for N < n, N = n, and N > n

EXAMPLES: Given a set of N = 3 distinct types of elements a, b, c. For n = 2, there exist 3 combinations without repetition (ab, ac, bc); 6 combinations with repetition (aa, ab, ac, bb, bc, cc); 6 distinguishable samples without replacement (ab, ac, ba, bc, ca, cb); and 9 distinguishable samples with replacement (aa, ab, ac, ba, bb, bc, ca, cb, cc).

Table C-3. Occupancy of Cells or States (see also Table C-2 and Sec. 18.7-2).

Each formula holds for N < n, N = n, and N > n

C-4. Use of Generating Functions(Refs. C-l, C-3). (a) Combinations. The combinations of n distinct objects A₁, A₂, . . . ,A_n, taken k at a time without repetition, are all “exhibited” as the coefficients a_k generated by the generating function (Sec. 8.)

The numbers of such combinations of n objects are the coefficients generated by the enumerating generating function (enumerator)

This “product model” for combinations can be generalized. Thus, if the object A₁ may be repeated 0, r₁ or r₂ times while A₂, A₃, . . . , A_n may each occur once or not at all, the corresponding generating functions take the form

If there is no restriction on the number of repetitions,

If each of the n objects must occur at least once,

(b) Permutations. To enumerate the permutations of n distinct objects taken k at a time without repetition, one may use the exponential generating function (Sec. 8.7-2.)

If one of the n objects can be repeated 0, r₁ or r₂, times, then

If any number of repetitions are allowed,

If each object must occur at least once,

C-2. Polya's Counting Theorem. Consider a finite set D of n “points” p each to be associated with one of the elements (figures) ƒ of a second finite set R (figure store, figure collection); more than one p may be associated with the same ƒ. One desires to investigate the class of such arrangements or configurations (patterns, mappings from D into R, Fig. C-l) subject to a given group G of permutations of the points p (Sec. 12.2-8). Two configurations C₁, C₂ are equivalent with respect to G if and only if a permutation in G transforms C₁ into C₂); equivalent configurations necessarily contain the same figures.

FIG. C-l. Two configurations are shown. The right-hand one is obtained from the left-hand one through a permutation of the points p_i. Two such configurations can be equivalent by virtue of some previously defined symmetry in the point set D and/or because two (or more) of the figures (in this case, f₁ and f₃) are indistinguishable.

The cycle index Z_G(s₁, s₂, . . . , s_n) of the permutation group G is a generating function defined as follows. Every permutation P of G classifies the points p of D into uniquely determined subsets (cycles) such that P produces only cyclic permutations of each subset (Sec. 12.2-8). Let b_k be the number of such cycles of length k for a given permutation (b₁ + 2b₂ + … + nb_n = n). Then the cycle index is defined as the polynomial

where g is the total number of permutations in (i.e., the order of) G, and gb₁b₂... is the number of permutations, with b₁ cycles of length 1, b₂ cycles of length 2, etc.

Assuming that each type of figure ƒ in R is associated with a non-negative integer w (weight or content of ƒ), let a_w be the number of distinguishable ƒ′s of weight w. The figure-counting series (store enumerator) is the generating function

The content (weight) of a configuration is the sum of its figure weights; equivalent configurations have equal content. Let A_w be the number of nonequivalent configurations of content w; then the configuration-counting series (pattern enumerator) is the generating function

The generating functions (12) and (13) are related by

In particular, the configuration inventory is related to the figure inventory

The theorem can be generalized to apply to situations where figures and configurations are labeled with two or more weights (Ref. C-l).

References and Bibliography

      C-l. Beckenbach, E. F. (ed.): Applied Combinatorial Mathematics, Wiley, New York, 1964.

      C-2. MacMahon, P. A.: Combinatory Analysis (2 vols.), Cambridge, London, 1915-1916.

      C-3. Riordan, J.: An Introduction to Combinatorial Analysis, Wiley, New York, 1958.

      C-4. Ryser, H. J.: Combinational Mathematics, Wiley, New York, 1963.