Trains

It may not be immediately obvious how this list of the first four sets of trains is generated, but we can actually find them through a systematic process, and not trial and error. Before we get to that, let's make some other observations.

First, we should notice that the number of trains of each length are a power of 2. We have 1 train of length 1, 2 trains of length 2, 4 trains of length 3, and 8 trains of length 4. We can clearly see a pattern of the number of trains of length n is the (n – 1)th power of 2.

Next, let's investigate each set of trains a little bit more. Let's focus on the connections between "cars" on each train. In the train of length 1, there is 1 train with zero connecting cars. In the trains of length 2, 1 train has one connection and 1 train has zero. In the trains of length three, 1 train has three connecting cars, 2 trains have two connecting cars, and 1 train has zero connecting cars. What about trains of length four? We have 1 with four connecting cars, 3 with three connecting cars, 3 with two connecting cars, and 1 with zero connecting cars. If you aren't recognizing the pattern in this form, what do you think if we organize the pattern in this way?

Do you recognize Pascal's triangle? As you can see, the total number of trains of length n corresponds to the sum of the nth row of the triangle. Further, the numbers from left to right in that row represent how many trains of length n are made of some number of cars between 1 and n. So, you might be wondering what this pattern has to do with the binomial theorem. Once we have a train longer than 1 unit, at each unit marker on the rod we face a binary choice - split into two rods or keep as one. Finding the total number of trains of a specific length means that we are trying to count every possible combination rods length 1 to n that a rod of length n can be split.

Below, I illustrate how the last figure of trains can be used to generate the next sixteen trains. Since we face a binary choice, we can determine the sixteen trains of length 8 by duplicating our trains of length 4. On one set of trains, we simply add a car of length 1 - this means we make the choice to make a split before adding a new car. These are the first 8 trains on the left of the image below. Next, we make the decision to not split, or extend, the cars in the top row. This means the first 4 cars which had been 1 unit in length, will now be 2 units long. The 2 unit-long cars are now 3 units long. The 3 unit car is now 4 units long, and finally, the 4 unit car is now 8 units long. I've used transitioning colors to see what the original car length was and what the new car length is. Note that we would get the same result if we had extended the cars at the bottom of the row, they would just be in a different order.