perm filename PAPER.PUB[1,LMM] blob sn#026771 filedate 1973-02-27 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00028 PAGES C REC PAGE DESCRIPTION C00001 00001 C00003 00002 .<<pub declarations>> C00004 00003 PART A. THE LABELLING PROBLEM. C00007 00004 SYMMETRY AND ITS RELATIONSHIP TO LABELLING C00009 00005 .<< Figure 2 >> C00012 00006 .<<TABLE I>> C00014 00007 .<< DEF EQUIVALENT >> C00016 00008 .<<Figure 3>> C00018 00009 PERMUTATIONS AND PERMUTATION GROUPS C00021 00010 .<< TABLE III >> C00024 00011 .BEGIN NOFILL GROUP C00027 00012 .BEGIN NOFILL GROUP C00028 00013 PART B. SOLUTION TO THE LABELLING PROBLEM C00030 00014 ∪A_∪Better_∪Method C00032 00015 .<<figure 6>> C00034 00016 2. Computing orbits C00037 00017 2. The reduced symmetry group. C00040 00018 .SEND FOOT ⊂ C00042 00019 ∪LABEL_∪RECURSION C00044 00020 .<<figure 7>> C00045 00021 ∪ORBIT_∪RECURSION C00048 00022 In some of these cases there are more than one possibility (cases C00050 00023 Second, label {2,4,7,9} with 1 N (and 3 blanks). Note that {2,4,7,9} is no C00054 00024 FINAL TECHNIQUE. C00056 00025 For example, the cyclohexane skeleton has a group of order twelve C00059 00026 Fortunately, this technique is rarely necessary -- usually C00061 00027 C.∪SUMMARY_∪OF_∪LABELLING_∪STEPS C00064 00028 REFERENCES C00065 ENDMK C⊗; .<<pub declarations>> .every heading({DATE}, LABELLING OBJECTS WITH SYMMETRY,PAGE {PAGE}) .NEXT PAGE .TURNON "↑↓[]∪" PART A. THE LABELLING PROBLEM. .BREAK The problem attacked is one of finding all distinct ways to assign a given number of labels or colors to the parts of a symmetric object when it is also known how many parts get each of the labels or colors. This problem is encountered in a wide range of applications beyond chemistry-- within many areas of graph theory and combinatorics, for example. It has been known how to compute the number of solutions [1], but an efficent method of actually constructing the solutions has not previously been reported. The discussion in this paper is restricted to the labelling of graphs with the "topological" symmetry groups; the algorithm, however, is immediatly applicable to other types of labellings; one could, for example, generate all distinct "permutational isomers" for a given three dimensional ring system as defined in Ruch [2]. .BEGIN NOFILL ---------------------------------------------------------------------- | INSERT HERE | | a long discussion with several examples - define permutational | |isomers from Ruch, explain how the algorithm is applicable. Perhaps | |the queen's problem might also be worthwhile. | |anyway, need to read up Ruch and use it. | ---------------------------------------------------------------------- .END SYMMETRY AND ITS RELATIONSHIP TO LABELLING .BREAK Consider the special case of the general problem: suppose all of the labels are distinct. This means that, for example,one wishes to number the faces of a cube with the numbers {1,2,3,4,5,6}, or the "nodes" (atom positions in a graph) of the decalin skeleton with numbers {1,2,3,4,5,6,7,8,9,10}. There are n! (n factorial) ways of labelling where n is the number of parts. If the object has no symmetry then each of these n! ways are distinct from the rest. However for the decalin skeleton (where n! = 10! = 10x9x8x7x6x5x4x3x2x1 = 3,628,800 ways) there is some symmetry. Pick one of the numberings as a point of reference (Fig 2a). Some of the 10! ways are different (Fig 2b); some of them are essentially the same (Fig 2c). .BEGIN NOFILL GROUP ------------------------------------------------------------ Figure 1 The Decalin Skeleton ⊗ ⊗ / \ / \ / \ / \ ⊗ ⊗ ⊗ | | | | | | ⊗ ⊗ ⊗ \ / \ / \ / \ / ⊗ ⊗ ------------------------------------------------------------ .END .<< Figure 2 >> .BEGIN NOFILL GROUP ------------------------------------------------------------ Figure 2 Three of the 10! numberings of the Decalin Skeleton. 2 4 7 1 4 2 / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ 1 3 5 2 8 9 5 3 1 | | | | | | | | | | | | | | | | | | 10 8 6 3 4 5 6 8 10 \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / 9 7 6 10 7 9 (2a) (2b) (2c) ------------------------------------------------------------ .END Intuitively, Figs 2a and 2c are equivalent because one could take 2a, flip it over and get 2c. There is another way of determining the "sameness" of such numberings which is easier in the more complicated cases and is in general more suited to computer application: .BREAK Write down the respective "connection tables". (See Table I). Note that the connection table for Fig 2c is identical to that of Fig 2a; that of Fig 2b is different. .<<TABLE I>> .BEGIN VERBATIM GROUP ------------------------------------------------------------ Table I. node|connected | node|connected | node|connected | to | | to | | to | | 1 2,10 | 1 8,9 | 1 2,10 2 1,3 | 2 7,3 | 2 1,3 3 2,4,8 | 3 2,6 | 3 2,4,8 4 3,5 | 4 6,8,10 | 4 3,5 5 4,6 | 5 9,10 | 5 4,6 6 5,7 | 6 3,4 | 6 5,7 7 6,8 | 7 2,8 | 7 6,8 8 3,7,9 | 8 1,4,7 | 8 3,7,9 9 8,10 | 9 1,5 | 9 8,10 10 1,9 | 10 4,5 | 10 1,9 ------------------------------------------------------------ .END .<< DEF EQUIVALENT >> .BEGIN INDENT 6,6,6 DEFINITION: two numberings of the nodes of a graph are ∪equivalent if the connection tables of the respective numberings are identical when the node numbers are written in ascending order and each "connected to" is in ascending order. .END This means, among other things, that properties such as valency are preserved: If two numberings are equivalent and in the first, node 1 is trivalent then in the second, node 1 is trivalent. If there are other properties of the nodes (already colored or labelled, for example), then this definition can be extened to include the preserving of those properties. .BREAK For example, suppose there are atom names associated with (some of) the nodes of the graph. Then one can define equivalent numberings to be those which not only have identical connection tables, but also the same atom names for the corresponding nodes. Then Fig 3a would still be equivalent to Fig 3c but no longer to Fig 3b since, although the connection tables of 3a and 3b are identical, node 1 in Fig 3a is labelled with an "N" while while in 3b it unlabelled. .BREAK .<<Figure 3>> .BEGIN NOFILL GROUP ---------------------------------------------------------- Figure 3. Partially labelled graphs reduce the equivalencies. 2 4 9 7 4 2 / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ N1 3 5N N10 8 6N N 3 1N | | | | | | | | | | | | | | | | | | 10 8 6 1 3 5 6 8 10 \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / 9 7 2 4 7 9 (3a) (3b) (3c) ---------------------------------------------------------- .END PERMUTATIONS AND PERMUTATION GROUPS .BREAK Given one numbering, one can use a condensed notation to write down others in terms of the first. In Table II, take the 2b case. The row of numbers means that, in sequence, the node numbered 1 in the reference numbering 2a is now numbered 2, the node originally numbered 2 is now numbered 10, and so on. All of these are written down with respect to the original "reference" numbering of figure 2a. .BEGIN NOFILL GROUP ------------------------------------------------------------- Table II Condensed Notation for Numberings Figure 2a numbers: 1 2 3 4 5 6 7 8 9 10 Figure 2b numbers: 2 10 3 7 4 6 5 8 1 9 Figure 2c numbers: 5 4 3 2 1 10 9 8 7 6 ------------------------------------------------------------- .END One can conceptualize a numbering as a transformation or as a function: The transformation for 2c is π↓2↓c(1)=5, π↓2↓c(2)=4, π↓2↓c(3)=3, ... π↓2↓c(10)=6. These transformations are ∪permutations: one to one mappings from the integers {1,2,...,n} to themselves. The transformation for the "reference" numbering is the identity i(x)=x. It can be shown that whatever the graph, the set of transformations satisfying the "equivalency" requirement above satisfies the property of a group. One may then say: .BEGIN INDENT 6 The ∪symmetry ∪group of a graph is the set of all transformations which yield identical connection tables. (If there are other properties to be considered, one may include them as part of the connection table). For the decalin skeleton there are 4 permutations in the group. .END .<< TABLE III >> .BEGIN NOFILL GROUP -------------------------------------------------------------------- Table III The Symmetry Group of the Decalin Skeleton π↓i 1 2 3 4 5 6 7 8 9 10 π↓v 5 4 3 2 1 10 9 8 7 6 π↓h 10 9 8 7 6 5 4 3 2 1 π↓[180] 6 7 8 9 10 1 2 3 4 5 ------------------------------------------------------------------- .END These correspond directly to the intuitive geometric symmetries π↓i=identity, π↓h=reflection about horizontal axis, π↓v=reflection about vertical axis, π↓[180] = rotation 180 degrees. It is not too difficult for a computer program to figure out the symmetry group of a graph given its connection table. .BREAK In many cases, one might wish to label the "edges" (interconnecting lines) of a graph. In this case, the symmetry group on the edges rather than on the nodes is required. It is very easy to calculate this group. First find the group on the nodes. Then, for each edge in the graph, write down the nodes that form the end-points. Then the corresponding permutations can be obtained as follows: .BEGIN NOFILL π↓i{n↓1,n↓2}={π↓i(n↓1),π↓i(n↓2)} .END This is most easily shown by way of an example. (Table IV). .BEGIN NOFILL GROUP ------------------------------------------------------------------ Table IV Group of Decalin Skeleton acting on the edges π↓i 1-2 2-3 3-8 3-4 4-5 5-6 6-7 7-8 8-9 9-10 1-10 π↓v 4-5 3-4 3-8 2-3 1-2 1-10 9-10 8-9 7-8 6-7 5-6 π↓h 9-10 8-9 3-8 7-8 6-7 5-6 4-5 3-4 2-3 1-2 1-10 π↓[180] 6-7 7-8 3-8 8-9 9-10 1-10 1-2 2-3 3-4 4-5 5-6 ------------------------------------------------------------------ .END Finding the group of an object is a special kind of labelling problem. Given one way of numbering (labelling with distinct labels) the parts of the object, one finds all other ways which are equivalent. The labelling problem attacked in this paper is the convers: to find a maximal list of labellings, none of which are equivalent to each other. In general the set of all posssible labellings can be split into subsets, such that: .BEGIN INDENT 6,6,6 1) If two labellings are in different subsets, they are not equivalent. .BREAK 2) If two labellings are in the same subset, they are equivalent. .END These subsets are called ∪equivalence ∪classes. .BREAK The relationship of finding the group, and of finding labellings where all the labels are distinct, can be viewed as follows: Take the n! possible labellings and lay them out in a matrix: each row will contain one equivalence class. (It can be shown that in this special cases where the labels are distinct, all of the equivalence classes are of the same size). To find the group, one needs to find a row. To find the labellings, one needs to pick one element from each row. .BEGIN NOFILL GROUP ------------------------------------------------------------- Figure 4 Equivalence classes, Groups, and Labellings ;.diagram here; .GROUP SKIP 30 ------------------------------------------------------------- .END PART B. SOLUTION TO THE LABELLING PROBLEM .BREAK ∪A_∪Naive_∪Method .BREAK An obvious method to find the distinct labellings would be to generate all n! of the possible ones, and for each one to check if an equivalent one was previously generated. Unfortunately, this method takes an exhorbitant amount of computation (proportional to n! squared). Below is discussed a method which takes an amount of time roughly proportional to the number of solutions (i.e. the number of equivalence classes of labellings) and requires only knowledge of the symmetry group (thus it is useful for labelling objects using their geometric symmetry as well as the topological symmetry defined above). .BREAK ∪A_∪Better_∪Method .BREAK 1. Special case: distinguish 1 node. .BREAK First consider the special case where there are only two types of labels and furthermore that there is only one of one of the types. (E.g., color one red, and the rest green, or label one N and the rest C.) Intuitively, for the decalin skeleton, one can see that there are three "types" of nodes, labelled with "⊗", "+" and "&" in Fig. 5, and that each distinct labelling corresponds to selecting one node from each type. (see Fig 6.) .BEGIN NOFILL GROUP ------------------------------------------------------------- Figure 5 Orbits in the Decalin Skeleton ⊗ ⊗ / \ / \ / \ / \ + & + | | | | | | + & + \ / \ / \ / \ / ⊗ ⊗ ------------------------------------------------------------- .END .<<figure 6>> .BEGIN NOFILL GROUP ------------------------------------------------------------- Figure 6 Three Labellings of Decalin with 1 N and 9 C's. ⊗ ⊗ N ⊗ ⊗ ⊗ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ N ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ N ⊗ | | | | | | | | | | | | | | | | | | ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ ------------------------------------------------------------- .END Thus there are three distinct labellings (the ten possible labellings split into three equivalalence classes). .BREAK 2. Computing orbits .BREAK In general, the parts of an object with symmetry split into different "types" (sometimes there is only one type, as in the faces of a cube, or the nodes of the cyclohexane skeleton). To label the parts of an object such that one is distinguished, it is necessary only to find the "types" and then, for each type, pick one of the parts in that type arbitrarily. Note that if the object has no symmetry each type has exactly one part in it. .BREAK It is very simple to find the different types from the table of the symmetry group: if one writes out the group, as in Table III, with each permutation as a row, then the numbers in each column, taken as a set, form a "type". Such "types" are called ∪orbits of the symmetry group. The orbits of the group in Table III are: {1,5,6,10}, {2,4,7,9}, {3,8}. .BREAK After finding the set of orbits, one then can do this special labelling: the number of distinct labellings is the number of orbits. Each corresponds to selecting an element from an corresponding orbit and labelling it. For reasons to be explained later, the first element of each orbit should be chosen (i.e. the one with the smallest number in the reference numbering). .BREAK One might note here that if one has n-1 labels and 1 "blank" it is the same as 1 label and n-1 "blanks". This special case can be applied here as well. 2. The reduced symmetry group. .BREAK Once a group has been calculated for a structure, many times one wants to know what the group is after some labels have been attached. The group of a labelled structure is always a ∪subset of the group of the unlabelled structure. Thus one needs to know which permutations in the group must be thrown out. To do this, write the "labels" associated with each node next to the node number in the permutation table as in Table II. If in any column, there is an element which has a different label than the label in the "reference" numbering (identity permutation), then that row can be discarded. That is, every permutation in the reduced symmetry group must satisfy: .BEGIN NOFILL for every node i, label(π(i))=label(i). .END Exactly those permutations in the original group that satisfy this equation are the ones in the reduced symmetry group of the labelled structure. .BREAK 3. Reduction techniques .BREAK In the general labelling problem, there are two important techniques used to reduce the problem. The first is called LABEL RECURSION↑* and the second ORBIT RECURSION. The idea behind LABEL RECURSION is that one can do one label at a time. The idea behind ORBIT RECURSION is that one can label one orbit at a time. These reductions are discussed in detail below. .BREAK .SEND FOOT ⊂ ------------------------ .BREAK .INDENT 0,6,6 * A ∪recursive technique is one which is defined in terms of itself. For example, n! can be defined by: .begin nofill { 1 if n=1 n! = { { n*(n-1)! otherwise .END .CONTINUE The computation of 10! involves computing another factorial. It is necessary that at each step, the problem is reduced. Here the general solution of the labelling problem is described in terms of less complicated labellings. Several special cases (analogous to the n=1 case in the definition of factorial) are also defined. .⊃; ∪LABEL_∪RECURSION .BREAK If one is given many (more than 2) kinds of labels, say n↓1 of type 1, n↓2 of type 2, ... n↓k of type k, proceed as follows: (1) solve the labelling problem for n↓1 of one type of label and n↓2+n↓3+...+n↓k of another type. (Call the second type of label "blank"). The result will be a list of partially labelled objects (along with their reduced symmetry groups). Take each of the results and label the "blank" parts with n↓2 labels of one kind, n↓3 of another, ... ,n↓k of another. It can be proved that the results will be a list of all distinct solutions to the original problem. For example, to label the decalin skeleton with 1 label "N", 1 label "S" and 8 labels "C", one first labels with 1 "N" and 9 "blanks" obtaining the 3 results in figure 7a. (Fig 7a1,7a2,7a3). There are now 3 new problems to label The "blanks" if Figs 7a1-3 (under their respective reduced symmetry), with 1 "S" and 8 "C"'s. In Figs 7a1 and 7a2, there is no symmetry left, and so each of the "blanks" has its own orbit, thus there are 9 distinct labellings apiece. In Fig. 7a3, there are 5 orbits under the reduced symmetry, and thus there are 5 additional possiblities. (Fig 7b). .BREAK .<<figure 7>> .BEGIN NOFILL GROUP ------------------------------------------------------------- Figure 7 Labellings with 1 N, 1 S, and 8 C's. ⊗ ⊗ / \ / \ N ⊗ ⊗ 7a1 | | | ⊗ ⊗ ⊗ \ / \ / ⊗ ⊗ N ⊗ / \ / \ ⊗ ⊗ ⊗ 7a2 | | | ⊗ ⊗ ⊗ \ / \ / ⊗ ⊗ ⊗ ⊗ / \ / \ ⊗ N ⊗ 7a3 | | | ⊗ ⊗ ⊗ \ / \ / ⊗ ⊗ ------------------------------------------------------------- .END ∪ORBIT_∪RECURSION .BREAK There are 3 cases in the 1 N, 9 C on the decalin skeleton problem. .BEGIN NOFILL (case 1) 1 N goes to orbit {1,5,6,10}. (case 2) 1 N goes to orbit {2,4,7,9}, (case 3) 1 N goes to orbit {3,8}. .END There is only one possibility in each of these cases. Suppose there were 3 N's. Then there would be 9 cases. (Table IV). .BEGIN VERBATIM GROUP ------------------------------------------------------------ Table IV. (3 N's on a decalin) # N's going to case orbit orbit orbit number {1,5,6,10} {2,4,7,9} {3,8} 1 3 - - 2 2 1 - 3 2 - 1 4 1 2 - 5 1 1 1 6 1 - 2 7 - 3 - 8 - 2 1 9 - 1 2 ------------------------------------------------------------ .END In some of these cases there are more than one possibility (cases 2,3,4,5 and 8). However, every labelling fits into one of these cases, and labellings from different cases cannot be equivalent. .BREAK Thus, each of these cases can be done independantly, and the results collected together. To do any one of the cases, the labellings of the orbits can be done sequentially. .BREAK Take case 5. First label one of {1,5,6,10} with one N, (and the rest "blanks"). Since {1,5,6,10} is an orbit, we can chose one arbitrarily and get Fig 8. (The first one is chosen). .BEGIN NOFILL GROUP ------------------------------------------------------------ Figure 8 1 N to orbit {1,5,6,10} ⊗ ⊗ / \ / \ / \ / \ N ⊗ ⊗ | | | | | | ⊗ ⊗ ⊗ \ / \ / \ / \ / ⊗ ⊗ ------------------------------------------------------------ .END Second, label {2,4,7,9} with 1 N (and 3 blanks). Note that {2,4,7,9} is no longer an orbit under the reduced group. Stick to the original plan-- it is just necessary to find ∪new orbits under the reduced group to label {2,4,7,9}. Since there is no symmetry left, each of {2,4,7,9} falls into its own orbit. The "special case" can be used directly to find the 4 solutions (Fig 9). .BEGIN NOFILL GROUP ------------------------------------------------------------ Figure 9 Second step of case 5 N ⊗ ⊗ N / \ / \ / \ / \ N ⊗ ⊗ N ⊗ ⊗ 9a | | | 9b | | | ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ \ / \ / \ / \ / ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ / \ / \ / \ / \ N ⊗ ⊗ N ⊗ ⊗ 9c | | | 9d | | | ⊗ ⊗ ⊗ ⊗ ⊗ ⊗ \ / \ / \ / \ / ⊗ N N ⊗ ------------------------------------------------------------ .END Then, for each of these solutions, {3,8} must be labelled with 1 N (and 1 blank). The final result is 8 possibilities for case 5, none of which have any remaining symmetry. .BREAK FINAL TECHNIQUE. .BREAK Now the only problem to be solved is this: suppose there are two types of labels, n↓1 of the first, and n↓2 of the second, neither n↓1 or n↓2 are 1, and there is only one orbit. No more simple reductions left. The solution, however, is another trick. Pick the first node and label it, calculating the reduced symmetry group and new orbits. Label the rest of the nodes (under the reduced group) with n↓1-1 labels of type 1 and n↓2 labels of type 2. The result will contain a representative of each equivalence class of labellings; however, if n↓1>2 then there may be some duplicates (i.e., two of the results may actually be equivalent). .BREAK For example, the cyclohexane skeleton has a group of order twelve (has twelve permutations), and there is only one orbit. To label it with three N's, one labels node 1 with a N, calculates the reduced group and new orbits; then finds the various cases for distributing the remaining two N's among those orbits. (Table V.) Then for each case, do each orbit sequentially. Cases 1, 3, 4 and 5 are fairly straightforward; in case 2, first label {1,2} with 1 N. (Figure 9). Now the group reduces even further, and one gets the two results depicted in Figure 9b. Note that in cases 1 and 2a are equivalent as well as 2b, 3, and 5. What to do? Fortunately, there is a good way of throwing out the impostors without having to check each of the results against each other result checking for equivalency: if one takes each of the results and tests with each permutation of the group if .begin group nofill π↓i(labelled set)≤labelled set .end continue if any permutation can so transform a labelled set, then it is an impostor-- throw the bum out. Furthermore, every impostor is detected this way. All that is necessary is that when does these "lower level" labellings, that one is careful to pick the "first" element of each orbit to label and the "first orbit" when there are a choice of orbits. .BEGIN GROUP NOFILL ------------------------------------------------------------ Table V cases for 2 N's on {2,3,4,5,6} of cyclo- hexane case {2,6} {3,5} {4} 1 2 - - 2 1 1 - 3 1 - 1 4 - 2 - 5 - 1 1 ------------------------------------------------------------ .END Fortunately, this technique is rarely necessary -- usually in the course of a computation, the "special cases" catch almost everything. For example, to label the decalin skeleton, it is never needed since even when one is labelling say orbit {2,4,7,9}, there is either 1, 2, n-1 or n-2 labels to be attached. For the cyclohexane skeleton, it is only needed if there are 3 of one label and 3 of another (if there were 3,2 and 1 of 3 respective label types, just do the singleton first -- the group will then reduce and again this "FINAL TECHNIQUE" will not be necessary. Only in cases where there is at least 6 fold symmetry (i.e., every orbit has at least 6 elements) and there are at least 3 of each of the label types is this technique required. .NEXT PAGE C.∪SUMMARY_∪OF_∪LABELLING_∪STEPS .begin nofill 1) if not previously calculated, find the group 2) if more than 2 different node types, do the entire labelling process with 1 of the label types, and the rest "blanks"; then for each of the solutions obtained, label the "blanks" with the remaining label types using the reduced symmetry group. and collect the results. 3) otherwise, a) find the orbits b) if more than one orbit, then 1) find the different "cases" -- ways of distributing the labels among the orbits 2) for each case, a) label the first orbit b) label the rest of the orbits using the reduced symmetry group obtained from a). and collect the results c) otherwise (only 1 orbit and 2 label types) 1) if there is only one of one of the label types, pick the "first" node and label it with that label type. This is the only distinct possibility. 2) otherwise, if there are two of one of the label types, label the first node with that label type, calculate the reduced symmetry group and new orbits, and from each of the new orbits, pick the "first" node. The solutions consist of those possibilities (one for each new orbit). 3) otherwise, (3 or more of each label type, and one orbit) label the "first" node, calculate the reduced symmetry group, label the rest of the nodes under the reduced group, and for each of the results, check if for every permutation π in the original group that π(labelled set)≥labelled set If this is not true of a labelled set, discard it as a solution. The result is every such labelling that satisfies this property. .end .next page REFERENCES .BREAK [1] De Bruijn, N. G., Generalization of Polya's Fundamental theorem in Enumerative Combinatorial Analysis, Nedarl. Akad. Wentensh. Proc. Ser. A, 62 (1959), 59-69; also Polya's Theory of Counting, in Applied Combinatorial Mathematics, E. Beckenbach, ed, Wiley, New York, 1964, pp 144-184.