[r-t] FW: A compositional question I am hoping a change-ringing theorist could help with! (re-sending)
Mark Davies
mark at snowtiger.net
Wed Jun 16 21:13:18 UTC 2010
Thank you Philip for the "Bucephalus" reference. I will accept this as a
suitably classical yet virile eponym...
Anyway, this is interesting. So Mark's rows are really derived from a
pattern in the deltas or intervals between the numbers, not the numbers
themselves; the first derivative, if you will. It seems worth exploring
the relationship bewteen this original pattern and the circular
permutations in the numbers themselves which I found last time.
So, we are talking clock arithmetic here, modulus 7. The basic set of
numbers is {1...7}, leaving the 4 in for now. The biggest difference
between any two numbers in this set (modulo 7) is 3 or -3, equivalent to
Mark's ascending or descending fourth. As he says, there are six
possible deltas between numbers, ignoring 0: {-3, -2, -1, +1, +2, +3}.
His "EIR" rows are then generated when we manage to use all six deltas
to visit six distinct numbers, and return to the number we started with.
An example is:
+1, +3, +2, -1, -2, -3
If we start at 1, this sequence of deltas gives us:
1, 2, 5, 7, 6, 4, 1
This works, in that we have visited six different numbers and returned
to the start, but doesn't match Mark's criteria exactly because we have
included the forbidden 4. But that's fine, because, for any successful
sequence of deltas, there is always one particular number we can pick to
start on which then avoids the 4. You can find the correct starting
number by identifying the one number, x, from the set {1..7} *not*
visited by the sequence. Add (4-x) to your original starting number and
you're away. In this case, x=3, so we add one to our original number,
and start from 2:
2, 3, 6, 1, 7, 5, 2
And that is a row on Mark's EIR list: rotated, it is 175236. (Notice how
6+2 = 1 and 1-1 = 7 in this base-7 clock arithmetic).
So basically we can generate EIRs simply by finding the permutations of
(-3, -2, -1, +1, +2, +3) which obey the two rules:
(a) they must visit 6 different numbers;
(b) they must end on the same number as they began.
In fact, (b) is always true, because if you add up -3, -2, -1, +1, +2,
+3 you get 0, so the total delta is always zero. So that's easy!
And in fact this does look a lot more like changeringing, now. The
deltas are a bit like different permuations - place notations, or
leadhead permutations perhaps - and the individual numbers are whole
changes, more like node numbers in terms of computer composition search
engines. Imagine a graph with the seven numbers as nodes, and with six
edges emanating from each node, representing the six possible deltas and
where you end up if you apply each. I can't easily draw that in plain
text, but here's a bit of it, showing the number 1 as a node with its
connections:
7 2
(-1)| |(+1)
\ /
6 - (-2) - 1 - (+2) - 3
/
(-3)|
5 4 missing because it's forbidden!
The sequences of deltas we are looking for are (I think) in mathematical
language Hamiltonian cycles of the complete graph, or in bellringing
terms, true extents. In fact, this looks to me very much like the
bellringing problem of getting a course of spliced Major from six
methods with different leadhead orders. The set of deltas {-3...+3}
corresponds to the leadhead orders (a..f) and the numbers {1..7}
correspond to the 7 plain bob leadheads at the Major stage. Example
methods might be Lancashire, Yorkshire, Adelaide, Ashtead, Silchester
and London; my example sequence of deltas +1, +3, +2, -1, -2, -3 then
corresponds to this 6-lead course:
2345678
3527486 Lancashire
8674523 Adelaide
4263857 Yorkshire
6482735 London
7856342 Silchester
2345678 Ashtead
Anyway, so the next question is, how many sequences of methods (deltas)
are there which give us a true six lead course (an EIR)?
This is pretty easy to calculate. The only reason a sequence can fail is
if it comes back to the starting number too early (comes round too
soon). There are only two ways this can happen:
1. If you have a delta and its inverse next to each other: -2, +2 is
obviously bad. There are six of these bad pairs, if you count e.g. -1,
+1 and +1, -1 separately.
2. There are also two sets of three deltas which bring you back to the
start: (+1, +2, -3) and the reverse (-1, -2, +3). They are the only
triplets which add up to 0, modulus 7. You can each set in any order, so
there are a total of 6 x 2 = 12 "bad triplets".
And that's it. Logically, if you have a sequence of 6 deltas in which
the first four bring you back to the start, well the last two must be a
bad pair. And you can't possibly have a sequence of 5 that comes back,
because you have one delta left over and they must all add up to 0. So
the two cases above are enough to weed out all bad sequences.
There are 6! = 720 different sequences of 6 deltas, but taking rotations
out of the equation we are left with 5! = 120. Let's exclude the bad
sequences one by one:
a) There are 2x2x2x2=16 sequences with all three bad pairs:
-1, +1, -2, +2, -3, +3
and the 8 swaps within the pairs plus the reversal
-1, +1, -3, +3, -2, +2
and its 8 swaps.
b) There are 3x2x2x2=24 sequences with two bad pairs:
-1, +1, -2, -3, +3, +2
with 8 swaps, plus 3 versions of this with a different pair split up.
c) There are 3x2x2x2x2=48 sequences with just one bad pair:
-1, +1, -2, -3, +2, +3
with 8 swaps, then change over 2s and 3s for 8 more, then do the same
again with 2 and then 3 as the bad pair together.
d) That leaves just the sequences with bad triplets but *no* bad pairs.
There are 6x3=18 of these. If you have one bad triplet (e.g. +1,+2,-3),
you always have the other one too, because exactly those deltas are left
over (-1,-2,+3). You can choose the first triplet in 6 ways, i.e. any
order, but there are only three rotations of the second triplet that
don't generate a bad pair where the two triplets meet.
So that is a total of 16+24+48+18=106 sequences which are ruled out.
That leaves 120-106 = 14 good ones! Exactly the number of EIRs which
Mark found.
The question remaining is, from my circle diagram of the previous email
it seemed obvious that two of the fourteen rows were "special". It's not
so obvious to me why, or even if, two of the fourteen delta sequences
are special.
However, there is still a unique property in the delta sequences that
correspond to the special rows. Most sequences look like this:
+1, +2, -1, -3, -2, +3
The special sequences take the form:
1, a, b, -1, -a, -b
where a and b are +-2 or +-3. In other words, a delta and its inverse
are always at opposite ends of the sequence (viewed as a circle):
1
-b a
-a b
-1
There are actually only two such sequences which work:
+1, +3, +2, -1, -3, -2
+1, -2, -3, -1, +2, +3
Any other possibilites, e.g. +1, +2, +3, -1, -2, -3 fail because they
break down into bad triplet in them - in this case (+3, -1, -2) = 0 and
(-3, +1, +2) = 0.
Does this tell us anything? Hopefully some proper mathematicians will
come back from their extended tea-drinking session and put us out of our
misery. ;-)
MBD
More information about the ringing-theory
mailing list