# [r-t] Parity

Fred Bone Fred.Bone at dial.pipex.com
Sun Jun 24 22:28:54 UTC 2007

```On 23 Jun 2007 at 17:59, Robin Woolley said:

> More than 30 years ago (!), the late Tony Carter (of Luton & Harpenden)
> published an article dealing with the material given in Fred Bone's reply. I
> have not been able to find my copy so have done my best to reconstruct the
> contents. Please bear with me if any errors have crept it over that time,
> but see what you can make of it.
>
> First. It is not necessary to sort the changes to derive the 'factorial
> index'. It can be done straight from the change. For example, on 6 bells,
> the change 213456 must give the index 120. To obtain the index, we reduce
> each bell by the number of bells smaller than it to its left. So 213456
> becomes 211111, but as Fred notes, we require rounds to be the zeroth index
> so reduce the result by one in each posiiton to give 100000. On mutliplying
> by the appropriate factorial, one gets the 'lexicographical-order' number.

A more direct approach (to my mind) is to count the smaller bells on the
right. (Proof: for any given bell, k, there are (k-1) smaller bells. If l
of these are to the left and r to the right, then r = k-1-l, which is
exactly the number obtained above).

Using this method, as you say, you get the factorial base representation
first, so the parity follows trivially. However, I understood the OP to
have the permutation index already and to want a way to derive the parity
from that.

BTW the representation you give for the factorial base will always end in
zero (the multiple of 0!). I prefer to write it without that, i.e. with
the last digit being the multiple of 1!, which amounts to ignoring the
final bell in the calculation (it having none after it ...), hence I
would write the factorial base representation

> Second. Tony told me that the above was known long before he published the
> article. He claimed the following extension. It is possible to generate the
> next factorial index *directly* from the previous using place notation only.
> The advantage of this is that one only needs to evaluate the actual change
> for the changes you require. Checking is done by checking the index which,
> inter alia, needs only one 'bit' - useful on a 48k Spectrum.
> As far as I can remember/see, the algorithm goes as follows:
>
> Consider 213456, index 100000 followed by 14 then 'x' place notations. The
> change are 231465 and 324156 respec. which (seem) to have indices 110010 &
> 211011. The algorithm (seems) to be this. In swapping AB, then i if A=>B, we
> have B+1.A else B.A

The last digit (in 6-digit notation) is always zero. 324156 is perm-index
270 = 21100[0]. It is (fairly) obvious that restoring 56 to their
previous position (which is what 14.x does) must restore their
corresponding digits, given that they come last.

This algorithm (which I think you have the wrong way round, even in your
subsequent e-mail) holds only for neighbouring bells, i.e. you can only
apply it one change at a time. For example,
324156 gives 21100[0] = 270
624153 gives 51201[0] = 637

Writing A,B for the (two successive) digits in factorial base and a,b for
the corresponding bell numbers,
A>B if and only if a>b
so that the swap (a,b)->(b,a) results in
(A,B)->(B,A-1) if A>B, and
(A,B)->(B+1,A) otherwise.

For example,
231465 gives 110010 (145)
324156 gives 211000 (270)

```