2

I have a problem which I would like to have a general formula for. Here is the description.

There are island aligned by a grid. Every cell contains an island. Every adjacent island is connected by vertical or horizontal bridges. Each bridge has a value. The vertical ones have value of 1. The horizontal ones have a value of the row number in the grid. You start from the left top island which is in the (0,0) position, 0. column and 0. row. You can travel only to the direction of right or down. A route to any islands have a value of multiplying the value of the bridges used in the route. An island has a value of adding up the value of all possible routes leading to the island. Is there a general formula depending on the row and column number? The column No1. has the formula of n*(n+1)/2. But the others are more complex which I couldn't really figure out. I I'm correct, the table looks like this:

0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1

1 3 7 15 31 63

1 6 25 90 301

1 10 65 350

1 15 140

1 21

1

Thank you for the answers!

Peter
  • 121

1 Answers1

0

Some experimentation shows that these are shifted Stirling numbers of the second kind. Specifically, the entry in row $n$, column $k$ is $t(n,k)=\begin{Bmatrix} n+k \\ n\end{Bmatrix}$. There is likely a combinatorial proof of this, which I don't see right off the bat. But here is a less intuitive proof. The numbers in your table clearly obey the recurrence $$s(n,k) = n s(n,k-1) + s(n-1,k).$$ Further, using the recurrence for the Stirling numbers of the second kind, we have $$t(n,k) = \begin{Bmatrix} n+k \\ n\end{Bmatrix} = \begin{Bmatrix} n+k-1 \\ n-1\end{Bmatrix} + n \begin{Bmatrix} n+k-1 \\ n\end{Bmatrix} = t(n-1,k) + n t(n,k-1).$$ Thus $s$ and $t$ satisfy the same recurrence; it can easily be checked that they have the same initial values, so they are the same sequence.

rogerl
  • 22,399