From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Patterns in permutations
Date: 4 Jul 1998 06:06:40 GMT
In article <359CFE39.CC247C5C@x400.icl.co.uk>,
Nick Battle wrote:
>After once hearing the "ringing of the changes" at Wells Cathedral
>(where the N bells are rung in every N! permutation) I started thinking
>about the various orderings of the permutations of N numbers and the
>patterns in the various orderings. Bell ringer friends told me of the
>various orderings used to ring the changes, most of them using a simple
>swap or shift of bell positions between adjacent peels so that they are
>simple to play.
Bell-ringers work with the natural period of oscillation of the bells
so they only have to pull a little once the bells are already swinging.
It takes some work to make the bells peal early or late, so one seeks
to interchange just one adjacent pair with each permutation.
This is a fun example of group theory at work, and it affords one the
opportunity to use "campanological" in a sentence. Here's the
relevant literature from MathSciNet:
Matches for: Anywhere=(change-ringing or bell-ringing or
campanological)
___[1] 90a:20010 White, Arthur T. Ringing the cosets. Amer. Math.
Monthly 94 (1987), no. 8, 721--746. (Reviewer: Norman Biggs) 20B99
(05C10 05C25 20D60)
___[2] 86h:00006 Bennett, R. G. T. Ringing the changes. New Zealand
Math. Soc. Newslett. No. 30 (1984), 16--21. (Reviewer: Peter M.
Neumann) 00A08 (01A99 05A99 20B99)
___[3] 84a:05025 Proulx, Viera Kr\v nanová On the genus of symmetric
groups. Trans. Amer. Math. Soc. 266 (1981), no. 2, 531--538.
(Reviewer: A. T. White) 05C10 (05C25 20B05 20F32)
___[4] 32 #7424 Rankin, R. A. A campanological problem in group
theory. II. Proc. Cambridge Philos. Soc. 62 1966 11--18. (Reviewer: M.
J. Wonenburger) 05.04
___[5] 22 #2039 Papworth, D. G. Computers and change-ringing. Comput.
J 3 1960/1961 47--50. 68.00
___[6] 19,13i Dickinson, D. J. On Fletcher's paper "Campanological
groups". Amer. Math. Monthly 64 (1957), 331--332. (Reviewer: R. A.
Rankin) 20.0X
___[7] 18,377d Fletcher, T. J. Campanological groups. Amer. Math.
Monthly 63 (1956), 619--626. (Reviewer: R. A. Rankin) 20.0X
___[8] 9,267f Rankin, R. A. A campanological problem in group theory.
Proc. Cambridge Philos. Soc. 44, (1948). 17--25. (Reviewer: H. S. M.
Coxeter) 20.0X
© Copyright American Mathematical Society 1998
([3] isn't really a match here. -- djr)
==============================================================================
From: scott@math.csuohio.edu (Brian M. Scott)
Newsgroups: sci.math
Subject: Re: Patterns in permutations
Date: Sun, 05 Jul 1998 02:53:39 GMT
On 05 Jul 1998 01:45:54 GMT, kramsay@aol.com (KRamsay) wrote:
>Here again to tell you more than you might have wanted to know about
>change ringing... and some ObMaths farther down.
>Somewhere out there I suspect there is a web page having a ton of
>methods and principles described using place notation. If not, there
>ought to be!
A Yahoo search on 'change ringing' turned up an interesting and
extensive FTP library at
ftp://sunsite.doc.ic.ac.uk/recreation/change-ringers/
not to mention a host of organization and personal pages for change
ringers. (And as I recall, a few methods are given in whole or in
part in Dorothy L. Sayers' Lord Peter Wimsey mystery _Nine Tailors_.)
Brian M. Scott
==============================================================================
From: kramsay@aol.com (KRamsay)
Newsgroups: sci.math
Subject: Re: Patterns in permutations
Date: 05 Jul 1998 01:45:54 GMT
Here again to tell you more than you might have wanted to know about
change ringing... and some ObMaths farther down.
In article <359CFE39.CC247C5C@x400.icl.co.uk>, Nick Battle
writes:
>After once hearing the "ringing of the changes" at Wells Cathedral
>(where the N bells are rung in every N! permutation) I started thinking
>about the various orderings of the permutations of N numbers and the
>patterns in the various orderings. Bell ringer friends told me of the
>various orderings used to ring the changes, most of them using a simple
>swap or shift of bell positions between adjacent peels so that they are
>simple to play.
Each ordering of the N bells is called a "row" (not a peal, see below),
and the transitions between rows are called "changes" (although people
often call rows "changes" too). Each row takes about 2 seconds to ring,
and change-ringing consists of ringing a sequence of rows. It's done
either with bells in towers, or with hand-bells. Tower bells are rung
for changes turning them through slightly more than full-circle swings,
close to balanced at the end of each swing.
We start and try[*] to end with the bells in their original order,
1 2 3 ... n, which is by convention a descending scale, typically a
major scale with bell n the tonic. That row is called "rounds".
[* Sometimes when we get all chaotic we just stop.]
For mechanical reasons we usually only move each bell by at most one
position from each row to the next. You can't cause a heavy bell to
ring again too quickly, especially if it has to rotate through a more
than 360 degree rotation, and it's much easier if you can keep the
bell swinging with about a 4 second period, slowing down somewhat to
move to later in the row, and speeding up a little to get earlier.
The exceptions to that rule are either party tricks, like "firing",
where we try to ring all the bells simultaneously (which people do to
celebrate holidays; ringers in Boston might be "firing" this evening--
they will also presumedly be ringing the bells for the Boston Pops'
performance of the 1812 overture, pretty soon in fact), or more often,
for fixing mistakes, as when the conductor says to someone, LEAD NOW
(i.e., you are supposed to be ringing *first* in the very next row,
hurry up!).
One simple way of ringing is called "call changes". The conductor
tells pairs of adjacent bells to trade places. The rest of the time,
though, we usually have most of the bells move from one row to the
next. Only in certain special cases do we leave a bell in the same
position in four successive rows, during call changes for example, or
when one of the bells is acting as a "cover", ringing last in every
change while the other bells' ringers get to have most of the fun.
This means that change ringing can be described using a fairly
condensed notation, known as place notation, in which for each change
you write down the numbers of the positions in which bells are staying
put. If there are an even number of bells, and none are saying put,
that's called a "cross", x. The first and last positions can be omitted
when they can be inferred. For example, if there are 8 bells, "3" is
short for "38"; if the pairs of positions 12, 45, 67 are swapping, we
still need to have the eighth bell stay put. "6" would similarly be an
abbreviation for "16".
Once someone has learned how to ring rounds (which is harder than you
might think) and call changes, the next most complicated thing to
learn is called "plain hunt". In place notation, we could write it as
x.1n.x.1n.x.1n... (for n bells, n even) or n.1.n.1.n.1.... (for n odd).
With six bells, we get
123456
214365 (x)
241635 (16)
426153 (x)
462513 (16)
645231 (x)
654321 (16)
563412 (x)
536142 (16)
351624 (x)
315264 (16)
132546 (x)
123456 (16)
and then we're back to rounds again. Note how each bell moves back and
forth across the row, ringing twice at either end ("leading full" or
"lying behind full"). It takes 12=2*6 changes.
This gets a bit dull after awhile, and we like to have it take longer
to get back to rounds, so one of the next things we do is to ring
"plain bob". In plain bob, the last change is "12" (or "12n" if n is
odd) instead of "16" (or whatever). This makes the last change above
132546
135264 (12)
This permutation is in mathematical terms a "5-cycle"; the positions
get mapped 2->4->6->5->3->2. As a result, you go through this "lead"
5 times before it gets back to rounds, or 2*6*5=60 changes in all.
The person ringing the #1 bell (the "trebel") gets a relatively easy
job; they just have to keep moving their bell back and forth just like
in plain hunt, while the other bells "dodge" back a step each time
the trebel leads.
This is characteristic of what are called "methods". The #1 bell
follows some fixed track, and on each cycle of it's work, called a
"lead" of the method, the remaining n-1 bells undergo an n-1-cycle.
By contrast, in a "principle", in each lead, all n bells undergo an
n-cycle. One of my favorite principles is called "Stedman":
3.1.n.3.1.3.1.3.n.1.3.1 repeated over and over, where n is odd.
1234567
2135476 (3)
2314567 (1)
3241657 (7)
2346175 (3)
2431657 (1)
4236175 (3)
4321657 (1)
3426175 (3)
4362715 (7)
4637251 (1)
6432715 (3)
6347251 (1) <-- The 7-cycle, 1->7->4->3->2->5->6->1
etc.
So it takes 7*12 changes to get back to rounds. Nobody has to play a
boring role, unless you decide to have an eighth bell "covering" and
keeping a steady rhythm.
It breaks naturally up in to "sixes", in which the first three bells
braid their way through all 6 possible arrangements. It's slightly
confused by the fact that we start in the middle of a six. The changes
"n" are to allow bells to move into and out of the front three. In
between those, you either have a six with changes 1.3.1.3.1 or with
3.1.3.1.3, braiding first one way ("right" hunting) and then the other
way ("wrong" hunting).
Somewhere out there I suspect there is a web page having a ton of
methods and principles described using place notation. If not, there
ought to be!
Since ringing methods get a little dull eventually, we also like to
have what are called "calls" for methods and principles too. In a
"call", the change at certain selected points (when the #1 bell is
leading, typically) is replaced with something else. For example, in
plain bob on six bells, we go ringing along x.16.x.16.... until we
get to where the #1 bell is ringing first again. Then because it's
plain bob, normally we have a 12 change. But if the conductor so
chooses, they can call a "bob", giving some advance warning of it,
and one rings a "14" instead.
351624 (x)
315264 (16) "Bob!"
132546 (x)
123564 (14)
Or one can call a "single", and the place notation is "1234":
351624 (x)
315264 (16) "Sin-gle!"
132546 (x)
132564 (1234)
This is what allows us to ring more than just 2*6*5 of the rows
possible. With judiciously placed bobs and singles, one can ring all
of them without duplicating any of them. (Proof left to reader.)
In stedman, one has bobs (n-2-nd position bell stays put instead of
the n-th position bell) and singles (last three bells stay put instead
of just the last one) which are executed in the transitions between
sixes.
On three occasions, people have rung all 8!=40320 possible rows on
eight bells. Once at least, 8 crazy people spent all day doing this
in tower. In hand, it only took 4 crazy people to spend all day
sitting and doing this (not switching places or otherwise taking
breaks...).
On a more sane level, all 7!=5040 permutations of 7 bells can be
rung in around 3 hours, or around 2 and a half hours with handbells,
which can be rung faster. Ringing 5040 changes on 7 bells, or at
least 5000 on another number of bells, is called a "peal". More
casually, we ring quarter-peals too.
Here is an amusing fact. The number of ways you can go from one row
to the next, swapping only adjacent pairs of bells, is given by the
n-th Fibonacci number.
>Consider the N! permutations of the numbers (1, 2,..., N). If you
>take each permutation as the coordinates of a point in N-space,
>then all the N! points are equi-distant from the origin. For example,
>if N=3 then the six points lie on the vertices of a regular hexagon,
>each point being sqrt(2) from two other points. In the general case, I
>believe the N! points are equi-distant from the origin and have N-1
>nearest neighbours which are sqrt(2) away (the neighbours are the other
>permutations that are one pair-swap away).
In order to have this property, we need to have the k-th coordinate be
the number of the position occupied by the k-th bell (rather than the
bell occupying the k-th position).
To answer other mathematical questions about bell-ringing, one can
think also of the graph, whose vertices are the n! rows, and whose
edges join the pairs of rows which can be reached from each other by
swapping nonoverlapping adjacent pairs. It would be interesting to
have a good estimate, for example, of the number of Hamilton circuits
in this graph, corresponding to ways of ringing all rows without
duplication. Even better, I'd like an estimate of the number of
circuits containing rounds, without duplicates.
>The set of points also have
>an N-fold rotational symmetry along a line passing through the origin.
>You could see the points as representing the various unique ways of
>fitting a solid block of sides 1, 2, ..., N into an N dimensional
>"corner", each point representing the corner of the block furthest away
>from the origin.
This set of points has lots of symmetries. To get N-fold symmetry, you
don't have to permute the coordinate axes in their original order; any
other order will also give you a symmetry. Although, if N is even, the
resulting symmetries are orientation-reversing, and hence not usually
called "rotations". To define a rotation in >3 dimensions, one axis is
not enough anyway.
In fact, any permutation of N elements gives you a symmetry of your
set of points, so you really have a lot of symmetry. You have symmetry
by S_N, the group of permutations of N elements.
>I have difficulty picturing what the N=4 "shape" made by joining the
>points to their nearest neighbours would look like, though trying to
>project it into 3-space I think the points form some sort of regular 4
>dimensional polygon (with 24 vertices). Beyond four dimensions I can't
>really picture what is happening at all.
The points are not only on a sphere around the origin; they are also
all on a plane x1+...+xN=N(N-1)/2. So it makes good sense to think of
the points as points in N-1 space, lying on a sphere. S_4 acts on a
tetrahedron by rotations and reflections, and your set has this same
symmetry. If you truncate a tetrahedron, you get something a bit like
it, although I guess you have to deform it somewhat?
>Is this sequence of shapes (as N increases) following some well known
>pattern itself?
It seems like there should be a name for it, although I don't know
what it is.
>As N becomes larger (and so N! is very large), do the
>shapes converge towards something (perhaps an N-dimensional polygon with
>so many faces that it approximates an N-sphere?).
The plane x1+x2+...+xk-x_{k+1}-...-xN=1+2+...+k-(k+1)-...-N has
the k!(N-k)! points on it where the first k coordinates are some
permutation of 1,...,k and the remaining coordinates are some
permutation of k+1,...,N. All the remaining vertices are on the same
side of that plane. So one face is contained in that plane. The
centroid of the face is ((k+1)/2,...,(k+1)/2,(N+k+1)/2,...,(N+k+1)/2)
or the average of the points (since they are symmetrically placed).
The distance to the center of the figure at ((N+1)/2,...,(N+1)/2) is
sqrt(k(N-k)^2/4+(N-k)k^2/4). When N is large and k~N/2, this is
~ N^{3/2}/4 while the distance between the center of the figure as a
whole and the vertices is ~ N^{3/2}/2sqrt(3).
So the answer is no; there are (many) points on the polytope which are
somewhat closer to the origin than the vertices are, and in that sense
it doesn't very well approximate a sphere, in spite of having a lot of
vertices and faces.
We don't have nearly as many towers with bells hung for change-ringing
in North America as in the U.K., but there are more (thirty-something)
than when I started learning how to ring in the 1980s (25). There are
such bells in Chicago, Boston, Quebec city, Vancouver, Victoria,
Honolulu, and a bunch of places I haven't been to yet, like Toronto
which has North America's first 12-bell tower set for change ringing.
This is small potatoes compared with the U.K. where there are 5000+
towers.
Keith Ramsay "Thou Shalt not hunt statistical significance with
kramsay@aol.com a shotgun." --Michael Driscoll's 1st commandment
==============================================================================
From: kramsay@aol.com (KRamsay)
Newsgroups: sci.math
Subject: Re: Hobbies for mathematicians
Date: 22 Dec 1998 08:50:49 GMT
In article <367eecf7.0@news.isni.net>, "Dan" writes:
|Personally, I enjoy chess, backgammon, bridge et cetera.
|However, combinatoric games hardly seems the proper
|way to get away from combinatoric work. What are some
|favorite hobbies of others who do alot of math? This is
|actually a serious question. Do many mathematicians find
|other interests to be just as rewarding?
In the U.S., change ringing seems to attract bands with a fair share
of mathematicians and computer programmers in them. It's combinatorial
in a way, and one has to pay attention to what one is doing, but is
more rhythmic and relaxing than competitive games are. It's absorbing
without necessarily involving a lot of thought. Many gradations of
skill and difficulty are possible. Some people just know a simple
method or two and like to ring those a little bit each week, to hear
the bells as they ring; some people make more of a sport of it,
memorize whole batches of methods, performing marathon-like feats of
endurance, and so on.
If it's not clear what I'm talking about, a likely possibility :-),
an explanation of what change ringing all about is can be found at
http://www.nagcr.org/. One disadvantage is that change ringing is only
done in certain places. There's a paper in the American Math Monthly
(I forget which year) by a professor White describing some of the
associated mathematics.
I have some friends who are both change ringers and square dancers,
and they claim there are many similarities between them. Fortunately,
square dancing is done in more places than change ringing, at least
in North America. One such group has a web page.
http://www.mit.edu/afs/athena.mit.edu/activity/t/tech-squares/
Keith Ramsay "Thou Shalt not hunt statistical significance with
kramsay@aol.com a shotgun." --Michael Driscoll's 1st commandment