[r-t] Parity

[Fred Bone]

On 19 Jun 2007 at 19:35, Leigh Simpson said:

> > On 19/06/07, Matt Dawson
> > <m.d.dawson at student.liverpool.ac.uk> wrote:
> > > here's a counterexample:
> > >
> > > 15423 -
> > > 15432 +
> > > 21345 -
> > > 21354 +
> 
> > I don't understand what you are saying.
> > 
> > With 15 in 1-2, the correct sequence should be
> > 15234 -
> > 15243 +
> > 15324 +
> > 15342 -
> > 15423 -
> > 15432 +
> > = as I said, - + + - - +
> 
> You've both got the correct sequence. The system works
> very nicely when you have n-4 bells fixed on the
> front.
> 
> I was hoping to find a quick way to find the parity
> based on finding an index of the row and analysing
> that index. Since the parity doesn't behave nicely
> that avenue seems prohibitive.

If you express the permutation index (zero-origin, so that rounds has 
index zero) in factorial base, then the parity of the sum of the digits 
equals the parity of the row.

For example, 5647321 has permutation index 3455 (i.e. 3455 rows precede 
it in a lexicographically-ordered list of all possible rows on 7). In 
factorial base, this is 443321. The sum of digits is odd, so the row is 
odd.

You can get the factorial base representation by successive integer 
division by 2,3,4,..., noting the successive remainders.
 3455 / 2 = 1727 remainder 1
 1727 / 3 =  575 remainder 2
  575 / 4 =  143 remainder 3
  143 / 5 =   28 remainder 3
   28 / 6 =    4 remainder 4
    4 / 7 =    0 remainder 4
This is precisely equivalent to saying that
 3455 = 4*720 + 4*120 + 3*24 + 3*6 + 2*2 + 1
For parity determination, of course, all you need to note is the 
cumulative parity.