Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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}\;.$$

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.