Laying Track
When our children were little, one of their favorite activities was playing with a train set. Much of the fun came from the act of assembling the pieces of wooden track, along with tunnels, bridges, switches, crossings, ramps, and other paraphernalia, into interesting arrangements. Our usual goal (I couldn't resist the temptation to assist) was to create a layout that used every component that we had on hand.
A recent paper in Mathematics Magazine about train track layouts reminded me of these long-ago endeavors. It also neatly illustrated the power of mathematics in delineating a realm of possibilities. The paper showed track arrangements that my children and I had never thought to consider building.
The mathematical problem addressed by Mark R. Snavely of Carthage College and former students James D. Beaman and Erin J. Beyerstedt concerned layouts with switches. A switch is a piece of track that offers two or more alternative paths for a train to follow.
"Without switches, you either make a circuit or a one-way path," Snavely and his coworkers write in the December 2006 Mathematics Magazine. "When switches are included, potential layouts become fascinatingly complex."
 |
A 2-way switch (with three nodes) and a 3-way switch (with four nodes). |
Inspired by young Brian Snavely's love of Thomas the Tank Engine, the researchers tackled the following question: How many different layouts can be made from a track set that has exactly one n-way and one m-way switch?
You can start with two 2-way switches. In this case, the layout would contain three lengths of track connecting six nodes (where a node is a point on a track to which other pieces can be attached).
From a combinatorial perspective, there are 15 ways to connect the first piece of track to the available nodes, two ways to connect the second piece of track to the remaining nodes, and only one way to connect the last piece. Because the first two pieces of track are placed in order, you divide by 2 and find that there are 15 possible layouts.
 |
An example of a layout with two 2-way switches. |
But many of these 15 layouts aren't distinct. Depending on how you define equivalence in this context, several layouts actually represent the same arrangement.
To establish equivalence, Snavely and his coworkers constructed a directed graph (an arrangement of vertices and edges) to represent the structure of each layout. They decided that two layouts are "tour equivalent" if their corresponding directed graphs are isomorphic.
"Using an exhaustive search, we found that there are five distinct layouts using two 2-way switches," the researchers report. They use the notation L(2, 2) = 5 to represent this result.
 |
The remaining four layouts using two 2-way switches. |
How many distinct layouts can you construct using two 3-way switches? two n-way switches?
Snavely and his coworkers present an argument establishing that L(n, n) = 2n + 1. So, two 3-way switches would yield seven distinct layouts.
Similar arguments provide formulas for finding the number of layouts involving an n-way switch and an m-way switch. There are 16 layouts using a 5-way switch and a 2-way switch, for example.
 |
This layout uses just one 3-way switch. |
There's much more to study, including the use of other notions of equivalence. And, even in the case of tour equivalence, you can try to find the number of distinct layouts when you have more than two switches.
"We found 34 distinct layouts using three 2-way switches," the researchers say. "Of these, 24 are connected."
"We hope to continue our analysis to include larger numbers of switches with more options," they note.
It's time to get out the old train set!
References:
Beaman, J.D., E.J. Beyerstedt, and M.R. Snavely. 2006. Counting train track layouts. Mathematics Magazine 79(December):347-359. Abstract.
Comments
There is better terminology for this. My husband was able to get college funding for equipment for student project work on packet-switching networks. (Choo choo!)
Posted by: A | January 5, 2007 07:08 PM
This is mildly interesting. But not all track layouts are interesting. For example, several of the layouts shown result in a train visiting one part of the layout once, then being trapped in another part. Another uninteresting layout is one where the train traverses the entire track, but only in one direction. I'm interested in layouts that allow the train to traverse almost all the parts in both directions.
Posted by: Jim McDaniel | January 8, 2007 01:14 PM
the original and the bottom left shape are the only two that don't get stuck in on one loop. if you select a direction and travel it on the other three, you will be left in a boring loop.
Posted by: Gary Cerar | January 10, 2007 11:57 AM
Thank you for this thought provoking article. As a program developer for a Faith-Based Non Profit seeking to kick-start the thinking process in youth through non-computerized, hands-on projects, this article reminds me of the hours I spent trying to create new track designs. Although we are a Robotics Learning Group, we believe that simplicity is the key to sparking creativity in Kids.
Again, Thank You
David
Posted by: David Lee | January 13, 2007 12:23 AM
I you look at the URL I provided you'll see some layouts where the train goes everywhere - like I see 'A' on January 5 was talking about. I've attached some SVG to the layouts to animate them if you click them - but that doesn't seem to be well supported yet.
Posted by: David McQuillan | July 16, 2007 07:44 PM
Well I had fun making tracks where the train went everywhere when going forwards, but now I have a remote control one where it can go backwards as well! Stritly for my grandson of oourse.
So the problem I currently have is how to characterise all the layouts where one can go from anywhere to anywhere using reversing but not swthing any of the points. It seems a bit harder than the one way version in http://www.fano.co.uk/pancursal/
Posted by: David McQuillan | October 16, 2007 06:22 AM
I found this page while looking for a program to figure out the best usage of the track pieces I have in the alotted space. where's a good mathematician when you need one? :-)
Posted by: sarah | April 10, 2008 09:44 PM