Stepping Stones: solution with Young tableaux

About a year ago or so, I created a math problem and submitted it to CsTutoringCenter. Titled Stepping Stones, my problem statement went like this:

In a certain river, there are a bunch of stepping stones arranged from one side to the other. A very athletic person can cross the river by jumping on these stepping stones, one at a time.

A stepping stone is big enough for only one person, and the gap between two stepping stones is small enough that it is possible to jump between two adjacent stepping stones.

You are an army commander trying to get a group of soldiers across this river (using these stepping stones). Initially your n soldiers are placed on the first n stepping stones. Your task is to get all of them onto the last n stepping stones.

For example, here are the five possible ways to get a group of two soldiers across a river with five stepping stones:

1) ##---  #-#--  -##--  -#-#-  --##-  --#-#  ---##
2) ##---  #-#--  -##--  -#-#-  -#--#  --#-#  ---##
3) ##---  #-#--  #--#-  -#-#-  --##-  --#-#  ---##
4) ##---  #-#--  #--#-  -#-#-  -#--#  --#-#  ---##
5) ##---  #-#--  #--#-  #---#  -#--#  --#-#  ---##

Let C(k,n) be the number of ways of which n soldiers can cross a river with k stepping stones. In the example, C(5,2) = 5.

Find C(50,12) mod 987654321.

Of course, small values of C(k,n) may be bruteforced by a computer. But C(50,12) is well out of reach of brute force, and substantial mathematics is needed. Or for the lazy, it is possible to find small values by brute force, then look the sequence up on OEIS to find the formula.

Bijection to a matrix representation

We find that any instance of the problem can be represented, or bijected to a special matrix, one where each row and column is increasing.

Let us number the soldiers in the following fashion. Let the rightmost soldier, that is, the soldier first to move, be labelled 1. The soldier behind him is labelled 2, and so on, until the last soldier to move is labelled n. Since the order of soldiers cannot change, each soldier moves exactly k-n times.

Consider a very simple case, with 4 stones and 2 soldiers. One possible way is the first soldier moving twice, followed by the second moving twice.

This move sequence can be represented by [1,1,2,2]. The other sequence, and the only other sequence is [1,2,1,2].

Firstly a sequence like [1,1,1,2] is invalid because in a valid sequence, each soldier has to move the same number of times. Another invalid case is something like [2,1,1,2], since obviously 2 cannot move the first turn. But how can you tell whether [1,2,1,1,2,1,3,2,3,3,2,3] is valid or not?

It isn’t very easy to tell in sequence form. Instead we represent the sequence as a matrix form.

Let’s try some examples first, The sequence [1,1,2,2] in matrix form is:

\begin{array}{cc} 1&2 \\ 3&4 \end{array}

The other sequence, [1,2,1,2], is:

\begin{array}{cc} 1&3 \\ 2&4 \end{array}

Try a more complex example, [1,2,1,1,2,1,3,2,3,3,2,3]:

\begin{array}{cccc} 1&3&4&6 \\ 2&5&8&11 \\ 7&9&10&12 \end{array}

To create the matrix, first have a counter and initialize it to 1; when the first soldier moves, place the counter in the first cell that’s unfilled in the first row, and increment the counter. Now if the second soldier moves, we place the counter in the second row (first unfilled cell), and increment it again, and so on. By the time we’re through all of the soldier moves, the matrix should be nice and rectangular.

Perhaps a different explanation is more intuitive. If A_{3,2} = 7 (where A is the matrix, A_{3,2} means row 3, column 2), that means on move 7, soldier number 3 makes his move number 2.

From this interpretation, several important facts surface. The rows must be increasing, obviously, since if the row is not increasing, say 7 comes before 5, move 7 happened before move 5, which can’t be!

Less obviously, the column has to be increasing. Suppose that in some matrix, A_{2,7}=20, and the cell directly underneath, A_{3,7} = 19. In that case soldier 3 made his move 7 before soldier 2 made his move 7. This results in soldier 3 ahead of soldier 2 (or at least on the same stone)!

So with k stones and n soldiers, the matrix should have n rows and k-n columns. The m \times n cells contain the numbers 1 \ldots mn, while each row and each column is increasing. Our job is to enumerate these matrices, since such a matrix forms a 1-to-1 correspondence to a valid move sequence.

Enumerating matrices with the hook length formula

A Young tableau is an interesting combinatorial object, based on the Ferrers diagram. From a Ferrers diagram of size n, a Young tableau is one where every number from 1 \ldots n is filled in it and all rows and all columns are increasing:

From any cell of a Young tableau, a hook is formed by extending all the way down, and all the way to the right:

The hook length of a cell is the length of its hook (including itself). In the above picture, the hook length is 5. Each cell in the tableau has a hook and a hook length.

The number of valid Young tableaux with a given shape \lambda and with n cells is given by the hook length formula:

N = \frac{n!}{\prod_{x \in \lambda} \mathrm{hook}_x}

A special case of the hook length formula can be used to enumerate rectangular Young tableaux. For instance, we have a 3*4 Young tableau. If we fill each cell with its hook length we get:

The count would then be

\frac{12!}{6 \cdot 5 \cdot 4 \cdot 5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}

Or alternatively,

\frac{12!}{\frac{6!}{3!} \cdot \frac{5!}{2!} \cdot \frac{4!}{1!} \cdot \frac{3!}{0!}}


\frac{12! \cdot 0! \cdot 1! \cdot 2! \cdot 3!}{3! \cdot 4! \cdot 5! \cdot 6!}

This can be generalized to a formula. If we have x rows and y columns:

\frac{(xy)! \prod_{i=1}^{y-1}i!}{\prod_{j=x}^{x+y-1} j!}

For C(k,n), we have n rows and k-n columns, thus by substitution we arrive at our formula:

C(k,n) = \frac{[n(k-n)]! \prod_{i=0}^{k-n-1}i!}{\prod_{j=n}^{k-1}j!}

This can be used to compute C(50,12), trivial to implement in Haskell or any other language.

2 thoughts on “Stepping Stones: solution with Young tableaux

  1. The amount of math you know blows me away. I’m a grade 12 student in Toronto at the top of my class and you lost me at matrix. Where have you learned all this stuff?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s