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