I have a problem and a solution, but the problem is nice, so lemme tell you about it first.. The problem is as follows:

We have got 31 tracks and 10 trains, Each train is so big, that between two there needs to be at least one free track. Now, how many valid combinations do exist to place the 10 trains on the 31 tracks?

Read on if you think that you have got the solution and want to compare it with mine (no guarantee that I’ve got it right though..)

My solution:

A valid combination needs to have the remaining 31 - 10 = 21 tracks (after the trains have been placed) distributed between the trains in such a way, that there is at least one (free) track between two trains.

If s_0, …, s_10 represent the number of free tracks between two trains, respectively for s_0 and s_10 between the outer most trains and the outside world, then s_0, s_10 >= 0 and s_1, … ,s_9 >= 1 (for a valid combination). Now we can add two tracks left and right that may not be used, so that we can then require s_0, s_10 >= 1, too. That is 21+2=23 tracks distributed on 11 (s_0 to s_10) numbers, and each needs to be >= 1.

Have you heard of ordered number partitions? An ordered number partition is a partition of a (natural) number n into k (natural) numbers, so that the sum of those k numbers is equal to n, and because natural numbers are greater 0, all numbers have to be at least 1.

If you want to determine the count of possible partitions, you can imagine it as sum of n 1s: 1 + 1 + 1 + 1 + … + 1
That is: n 1s and n-1 ‘+’ signs. We can now group the sum into k sub-sums by selecting k - 1 + signs and separate the sum into sub-sums at that position. E.g.:
1 + 1 + 1 + 1 + 1 + 1 divided in 3 sub-sums: ( 1 + 1 + 1 ) + 1 + ( 1 + 1 )

The number of selecting k - 1 + signs out of n - 1 is simply the binomial coefficient of \(\binom {n - 1} {k - 1}\)!

So with our numbers we get: {11-1} = 10 = 646646

\o/

Excellent work, soldier!

Cheers, Black