Trains

Trains are constructed by putting together two kinds of cars, those of length 1 and those of length 2. The problem is to find out how many different trains there are of total length 12 units

For example, here is one possibility, using 6 cars of length 1 and 3 cars of length 2.

Other possibilities are obtained by rearranging the cars, or using different numbers of short and long cars. 

It’s hard to know how to start thinking about this. We could try to list all the possibilities in some systematic order, but there are a large number of trains of length 12, and we hope there might be a better way.

One idea is to look at trains that are much shorter, find out how many there are by direct counting, and see if we can find a pattern. For example the table at the right shows that there are 8 different trains of length 5. This strategy will lead us to the wonderful Fibonacci sequence and from there to an argument using recursive thinking.

For example, here are the 8 trains of length 5

1-1-1-1-1

1-1-1-2

1-1-2-1

1-2-1-1

2-1-1-1

1-2-2

2-1-2

2-2-1