1
$\begingroup$

Say you have a function: f (m,n)

f (m,n) =  m  if n = 1 f (m,n) =  n  if m = 1 otherwise f (m,n) = f (m - 1, n) + f (m, n - 1) 

Pre-calculated value:

1 2  3  4  5  6  2 4  7  11 16 3 7  14 25 4 11 25 5 16 6 

Just wondering if there could be formula of f(m,n), instead of doing a dynamic progrmming or recursive calculation to get the value.

2 Answers 2

5

There is indeed. Let $g(m,n)=f(m-n+1,n)$, so that for instance $g(5,3)=f(3,3)=14$. The corresponding table for $g$ is:

$\begin{array}{} 1\\ 2&2\\ 3&4&3\\ 4&7&7&4\\ 5&11&14&11&5\\ 6&16&25&25&16&6 \end{array}$

Now

$\begin{align*} g(m,n)&=f(m-n,n)\\ &=f(m-n-1,n)+f(m-n,n-1)\\ &=f\big((m-1)-n,n\big)+f\big((m-1)-(n-1),n-1\big)\\ &=g(m-1,n)+g(m-1,n-1)\;, \end{align*}$

which is the recurrence that generates Pascal’s triangle of binomial coeffients. Moreover, $g$’s table looks a lot like Pascal’s triangle in overall form:

$\begin{array}{} 1\\ 1&1\\ 1&2&1\\ 1&3&3&1\\ 1&4&6&4&1\\ 1&5&10&10&5&1\\ 1&6&15&20&15&6&1 \end{array}$

Ignore that first column of Pascal’s triangle:

$\begin{array}{} 1\\ 2&1\\ 3&3&1\\ 4&6&4&1\\ 5&10&10&5&1\\ 6&15&20&15&6&1 \end{array}\tag{1}$

Subtract this from $g$’s triangle:

$\begin{array}{} 0\\ 0&1\\ 0&1&2\\ 0&1&3&3\\ 0&1&4&6&4\\ 0&1&5&10&10&5 \end{array}\tag{2}$

Ignore the first column of this, and put $1$’s along the diagonal, and Pascal’s triangle shows up again. Now the $(m,n)$-entry in $(1)$ is $\binom{m}n$, and if $(2)$ really is Pascal’s triangle, its $(m,n)$-entry is $\binom{m-1}{n-2}$, so we conjecture that $g(m,n)=\binom{m}n+\binom{m-1}{n-2}$ and hence that

$f(m,n)=g(m+n-1,n)=\binom{m+n-1}n+\binom{m+n-2}{n-2}\;.$

We first verify the recurrence:

$\begin{align*} \binom{m+n-1}n+\binom{m+n-2}{n-2}&=\binom{m+n-2}{n-1}+\color{red}{\binom{m+n-2}n}+\binom{m+n-3}{n-3}+\color{blue}{\binom{m+n-3}{n-2}}\\ &=\binom{m+(n-1)-1}{n-1}+\color{red}{\binom{m+(n-1)-2}{n-3}}\\ &\qquad\qquad+\binom{(m-1)+n-1}n+\color{blue}{\binom{(m-1)+n-2}{n-2}}\\ &=f(m,n-1)+f(m-1,n)\;, \end{align*}$

as desired. Finally,

$f(1,n)=\binom{1+n-1}n+\binom{1+n-2}{n-2}=1+(n-1)=n$

and

$f(m,1)=\binom{m+1-1}1+\binom{m+1-2}{-1}=m+0=m\;,$

so the initial conditions are also satisfied. To repeat,

$f(m,n)=\binom{m+n-1}n+\binom{m+n-2}{n-2}\;,$

which can easily be manipulated into a variety of other forms involving binomial coefficients, e.g.,

$f(m,n)=g(m+n-1,n)=\binom{m+n-2}n+\binom{m+n-2}{n-1}+\binom{m+n-2}{n-2}\;.$

4

OEIS A072405 suggests

${n+m \choose m} - {n+m-2 \choose m-1}$

essentially the difference between two Pascal triangles. OEIS A051597, A122218 and A209561 are pretty much the same.