Main Theorems

We now present theorems that give the number of elements of maximum gravity in Sing_n. From Theorem 2.2 it is clear that all elements of maximum gravity are to be found in the 95#95-class D_{n - 1}consisting of elements of defect 1. A typical 96#96-class within this 95#95-class may be denoted by 97#97: it consists of all elements 1#1 for which 23#23 is the equivalence whose only non-singleton class is 98#98. A typical 99#99-class within D_n-1 may be denoted by 100#100: it consists of all 1#1 for which 22#22 101#101. There are 102#10296#96-classes and n 99#99-classes, and each 4#4-class contains (n - 1) ! elements.

We may write 103#103 for the 4#4-class that is the intersection of 104#104 and L(k). It is a group 4#4-class if and only if 105#105. Thus each 96#96-class in D_{n - 1}contains exactly two group 4#4-classes (and n - 2 non-group 4#4-classes).

As in the proof of Theorem 2.2 we shall find elements of maximum gravity by having as many cyclic components as possible and as few fixed points as possible. This will frequently involve constructing a number pof 2-cycles from 2 p elements of X_n, and it may be useful to note now that the number of ways of doing this is (2p)! / (p!2^p).

Theorem 3.1   Let n = 2m be even, with 106#106. Then the number of elements of Sing_n with maximum gravity (equal to 3m - 2) in a single group 4#4-class is

107#107

and the number in a nongroup 4#4-class is

108#108

The total number is

109#109

Proof: Consider first a typical group 4#4-class 110#110.

 

Figure: Configurations of Group Elements of Maximum Gravity (n even)

111#111

Within this 4#4-class the configurations that lead to maximum gravity are as shown in Figure 4, so the number of elements of maximum gravity in this class is

112#112

Now consider a typical non-group 4#4-class 103#103, where 113#113. Recalling Lemma 1.1, we see that the only possible maximum gravity configurations are as in Figure 5.

 

Figure: Configurations of Non-Group Elements With Maximum Gravity (n even)

114#114

Hence the number of elements of maximum gravity is

115#115

Since there are 2m(2m - 1) group 4#4-classes and m(2m - 1)(2m - 2)non-group 4#4-classes in the 95#95-class D_{2m - 1} one may easily calculate that the total number of elements of maximum gravity is

116#116

These formulae were verified at Argonne National Laboratory for m = 3, 4, and 5, when the results 1,050, 17,640, and 311,850 respectively agreed with the theorem. In fact, several test runs of the PROLOG program were very useful in suggesting both the formulae and the methods of establishing them. To generate all the elements of maximum gravity is a very time consuming task, even on a fast computer; for example, for n = 8 one has to check 1,128,960 elements. But breaking the task down to one 96#96-class at a time reduces it to 40,320 elements per computer run, and further breaking it down to one 4#4-class at a time requires only 7! = 5,040 elements per run. The PROLOG program is designed to generate all elements of defect one in a given nongroup 4#4-class and to decide which of those have maximum gravity. It can perform the (easier) task for group 4#4-classes too, and accumulate the totals.

In the case m = 2 the fourth of the configurations listed in Figure 4 cannot arise, and the number of elements of maximum gravity is 60.

For odd n the situation is much less complicated because nongroup elements play no role.

Theorem 3.2   Let n = 2m + 1 be odd, with 117#117. Then the elements of maximum gravity (equal to 3m) are all group elements, and the number in any one group 4#4-class is

118#118

The total number of elements of Sing_n with maximum gravity is

119#119

Proof: Here the only possible configuration giving maximum gravity is as shown in Figure 6, and by Lemma 1.1 all elements having this configuration are group elements. Within a typical group 4#4-class 110#110 the nodes in Figure 6 at a and b must be i,j respectively, and so the number of elements of maximum gravity within the 4#4-class is

120#120

 

Figure: Single Configuration With Maximum Gravity (n odd)

121#121

The proof is completed with the observation that the 95#95-class D_2m contains 2m(2m + 1) group 4#4-classes. 32#32

These formulae also were verified at Argonne National Laboratory, again for m = 3, 4 and 5. This time n = 7, 9 and 11 respectively, and the corresponding results were 630, 7,560 and 103,950.

At this point it becomes convenient to develop a little more notation. Given integers 122#122 and g, let N(n, r, g) denote the number of elements 1#1 in T_nsuch that 123#123 and 124#124. Thus Theorem 3.2 can be restated in the form

125#125

Having investigated elements of maximum gravity we now turn our attention to elements whose gravity is small. Elements of minimum gravity 1 are simply idempotents of defect 1 by the theorems of [5] and [2], and in our new notation the well-known result concerning the number of idempotents of defect 1can be expressed as

 

N(n, n - 1, 1) = n(n - 1). (2)

Theorem 3.3   For all 126#126,

N(n, n - 1, 2) = n(n - 1)(n - 2).

Proof: For 3#3 to equal 2 we require to have 127#127. If there were n - 1 fixed points and one cycle the total number of elements of X_n would have to be at least (n - 1) + 2, which is not possible. So 1#1 must have n - 2 fixed points and no cycles. Since 128#128 the only possible configuration is as shown in Figure 7.

 

Figure: Single Configuration with 2#2

121#121

The number of elements corresponding to this configuration is n(n - 1)(n - 2). 32#32

Formula (2) and Theorem 3.3 might appear to suggest a general result. The next theorem shows that one's first guess at a general result will not work.

Theorem 3.4   For all 129#129

N(n, n-1, 3) = n(n - 1)(n - 2)²;

for all 130#130

N(n, n-1, 4) = n(n - 1)(n - 2)(n - 3)(2n - 3)/2.

Proof: Let 128#128 and 131#131, so that 132#132. On the face of it, a configuration involving n - 2 fixed points and one cycle is possible, but this would result in all n elements of X_n lying in 22#22and so cannot occur. There must therefore be n - 3 fixed points and no cycles. There are two ways this can occur, namely with the configurations shown in Figure 8,

 

Figure: Two Possible Configurations

133#133

giving n(n - 1)(n - 2) and n(n - 1)(n - 2)(n - 3) elements respectively. The sum of these numbers is n(n - 1)(n - 2)².

Now let 128#128 and 134#134, so that 135#135. Here we have n - 4 fixed points and no cycles or n - 3 fixed points and one cycle. Possible configurations are shown in Figure 9,

 

Figure: Possible Configurations

136#136

giving a total of

n(n - 1)(n - 2)(n - 3) + n(n - 1)(n - 2)(n - 3)

+ n(n - 1)(n - 2)(n - 3)(n - 4) + n(n - 1)(n - 2)(n - 3)/2

137#137

This last result was verified at Argonne for n = 5 and 6.

It would doubtless be possible to find formulae for N(n, n - 1, k)for 138#138, but a general formula does not seem to be obtainable easily.

There is, however, some interest in looking at the bottom end of Sing_n rather than at the top. If 139#139 then 1#1 is necessarily idempotent. There is one fixed point and there are no cycles; hence 140#140, and N(n, 1, n - 1) = n.

In the case where 141#141 the situation is more interesting.

Lemma 3.5   Let 54#54, with 141#141. Then 142#142 or n - 1 or n - 2.

Proof: First, notice that every fixed point is in the image of 1#1, and so if 141#141 then there cannot be any cycles at all, for every cycle contributes at least 2 elements to 22#22 and the remaining n - 2 elements then have nowhere to go. Hence 142#142 (no fixed points) or n - 1 (1 fixed point) or n - 2 (2 fixed points).

We conclude that N(n, 2, g) = 0except when g = n, n - 1, or n - 2. 32#32

Theorem 3.6   Let 126#126. Then

143#143

144#144

Proof: Suppose first that 145#145. Since there are no fixed points the digraph of 1#1 must have a single component whose core is a 2-cycle. The remaining points must map to one or other element of the core, as shown in Figure 10.

  

Figure: Pre-image of Core

146#146

The elements of this core can be chosen in 102#102 ways, and the remaining n - 2 elements can be assigned in 2^{n - 2}, making 2^{n - 3}n(n - 1) ways in all.

Next, suppose that 147#147. There are two fixed points, and the remaining elements map directly to one or other of them. Hence again we obtain 2^{n - 3}n(n - 1) maps in all.

Now suppose that 148#148. There cannot be more than one component of 1#1, since two acyclic or singleton components would imply that there were two fixed points, and the existence of a standard or cyclic component in addition to the component containing the fixed point of 1#1 would immediately give 149#149. So there is just one component, containing a fixed point p and exactly one other element q in 22#22, as shown in Figure 11.

  

Figure: One Fixed Point

150#150

The choice of p and q can be made in n(n - 1) ways. The remaining n - 2 elements map either to p or to q, but cannot all map to p, since that would give 139#139. So the total number is

151#151

Note: The sum of N(n, 2, n), N(n, 2, n - 1) and N(n, 2, n - 2) is n(n - 1)(2^{n - 1} - 1), in agreement with the general formula given in 152#152 that the number of elements of rank r in T_n is 153#153, where S(n, r) is the Stirling number of the second kind. It is well known (see [1]) that S(n, 2) = 2^{n - 1} - 1.

Remark: It is significant that successful ``counting'' formulae have been obtained only when 79#79 is large (that is, close to n), or small (that is, close to 1). For values of 79#79 in the middle, the situation appears to much more complex. By direct computation we know that

N(6, 3, 3) = 540, N(6, 3, 4) = 2280, N(6, 3, 5) = 4560, N(6, 3, 6) = 3420,

but only the first of these exemplifies a general formula known to us. The elements in T_nof rank r and gravity n - r are simply the idempotents of rank r, and it is known 154#154 that there are 155#155 such elements.