recursion number of possible paths

Question

There is a terraced structure with N floors (here, for example 4 floors). Each floor has 4 cells.

Write the recursive function that describes the number of all the possible paths from the left bottom cell to the top right cell. We can go up, down, right but not left and we can't visit in the same cell again. Use only one variable.

Answer 1

You can make a total of $9$ moves to get to the right upper cell in the grid starting from the lower left cell. At any given moment during your moves, The number of right moves made so far is always larger than or equals to the number of up moves made so far. Also, at any given time, the difference between number of right moves and the number of up moves seen so far should not be greater than $3$.

We can translate those condition into restriction on formulas, so we first give definition of some variables.

We let $r$ denote the number of possible right moves that you can still make so far, let $l$ be the number of possible left moves you can still make so far and let $t$ be the number of moves you can still make. Then $r+l=3$(because each time you make a right move, the number of right moves you can still make decreases by $1$ and the number of up moves that you can make increases by $1$) and $t=9$ initially.

let $H(r,l,t)$ be the number of ways to finish all your moves where you can still make $r$ right moves, $l$ left moves and $t$ more moves. Then $H(r,l,t)=1+H(r-1,l+1,t-1)+H(r+1,l-1,t-1)$ The base cases is: $H(r,l,t)=0$ if $(t=0) \vee (r<0) \vee (l<0)$ and you want to solve $H(3,0,9)$.

Hope this is a good recursion.

Answer 2

Here is one way to break it down. The terraced structures can be composed by combining two consecutive triangular shapes from this series:

n=2    n=3      n=4
                      1
           1        O 2
  1      O 2      O O 3
O 2    O O 3    O O O 4  ...

so now the question becomes:

How many paths (using NSE-directions, ie. north south east) can be formed in $T_n$, the triangular shape with $n$ layers ending at one of the numbered positions? Let $P_n(k)$ denote the number of paths in $T_n$ starting from the bottom left corner ending in the numbered position $k$ on the right side of the triangle.

Analysis of triangular shapes

For $n=2$ we have $P_2(1)=P_2(2)=1$, because we have one path leading to each numbered position:

   1*      1
 ──┘     ──2*

For $n=3$ this becomes $P_3(k)=2$, since you can make a path to either one of the end positions in $T_2$ and then move into the last column in $T_3$ and reach the desired end position:

     1*      1       1             1*      1       1
   ┌─┘     ┌─2*    ┌─┐           O │     O 2*    O 2
 ──┘ 3   ──┘ 3   ──┘ 3*   and  ────┘   ────┘   ────3*

This principle generalizes, and it follows that $P_n(k)$ is equal for all $k$. Let us hence denote this number simply by $P_n$. Then we have the recursive formula (and obvious solution to it): $$ P_n=(n-1)P_{n-1}=(n-1)! $$

Analysis of terraced structure

Given the terrace of size $n$, $S_n$, this can be combined from two triangles: $$ S_n\sim T_n + T_{n-1} $$ so for instance $S_3$ can be seen as follows

    3─2 2
  3 3─2
3 3 3

where the top right corner is $T_2$ placed upside down. Any solution to the original problem will be a connection of paths in the two triangular shapes through one of the connections marked with a line in the figure above. Hence we have:

A solution to the $S_n$ terrace problem, can be constructed by combining a path to one of the top $n-1$ positions in $T_n$ to any end position in $T_{n-1}$. Let $K_n$ denote the number of such paths.

This leads to the recursive formula: $$ K_n=(n-1)P_n\cdot P_{n-1}=(n-1)!^2 $$

---

For instance we get $K_2=1!^2=1$ and $K_3=2!^2=4$ and $K_4=3!^2=36$ which you can easily make a sanity check for.

---

It just occurred to me that one could simply place two $T_n$ triangles with a one column overlap in the middle. This leads directly to: $$ K_n=(P_n)^2=(n-1)!^2 $$