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."
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.
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.
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.
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!
If you wish to comment on this article, see the MathTrek blog version. For more math fun, go to http://blog.sciencenews.org/mathtrek/.
