3
$\begingroup$

I've written a function. I believe the function runs in complexity:

$$ T(m, n) = \begin{cases} T(m-1, n) + T(m, n-1) + T(m-1, n-1) + 1 &\text{if $m,n>0$}\\ 0 &\text{otherwise} \end{cases} $$

I have no idea how to simplify this. Can anyone help?

(No, this is not a homework assignment. Well, writing the function was, but after writing it I'm certain that I wrote a very inefficient implementation and am trying to figure out just how bad my version really is.)

$\endgroup$
2
$\begingroup$

Let $P = \sum_{n,m \geq 0} T(n,m) x^n y^m$. We have $$ \begin{align*} P &= \sum_{n,m \geq 1} T(n,m) x^n y^m \\ &= \sum_{n,m \geq 1} [T(n-1,m) + T(n,m-1) + T(n-1,m-1)+1] x^n y^m \\ &= \sum_{n \geq 0, m \geq 1} T(n,m) x^{n+1} y^m + \sum_{n \geq 1, m \geq 0} T(n,m) x^n y^{m+1} + \sum_{n,m \geq 0} T(n,m) x^{n+1} y^{m+1} + \sum_{n,m \geq 1} x^n y^m \\ &= (x+y+xy)P + \frac{xy}{(1-x)(1-y)}. \end{align*} $$ We deduce that $(1-x-y-xy)P = xy/(1-x)(1-y)$, and so $$ P = \frac{xy}{(1-x)(1-y)(1-x-y-xy)}. $$

At this point we could invoke multivariate asymptotic analysis, but instead we'll connect $P$ to the Delannoy numbers $D(n,m)$, which follow a similar recurrence $D(n,m) = D(n-1,m) + D(n,m-1) + D(n-1,m-1)$, with base case $D(0,0) = 1$. These numbers have generating series $Q = 1/(1-x-y-xy)$. Our formula above shows that $$ P = \frac{x}{1-x} \frac{y}{1-y} Q = \sum_{n,m \geq 1} x^n y^m Q, $$ and so we obtain the formula $$ T(n,m) = \sum_{n'<n,m'<m} D(n',m'). $$ This formula can also be derived directly in various ways.

Pemantle and Wilson shows that when $n,m \to \infty$ and $n/m,m/n$ are bounded, $$ D(n,m) \sim \frac{nm}{\sqrt{2\pi}(n+m-\sqrt{n^2+m^2})^2\sqrt{n^2+m^2}} \left(\frac{m}{\sqrt{n^2+m^2}-n}\right)^m \left(\frac{n}{\sqrt{n^2+m^2}-m}\right)^n $$ This should be compared to the similar frightening formula for the binomial coefficients, $$ \binom{n+m}{m} \sim \sqrt{\frac{n+m}{2\pi nm}} \left(\frac{n+m}{n}\right)^n \left(\frac{n+m}{m}\right)^m. $$ The asymptotic formula for $D(n,m)$ can probably be used to come up with an asymptotic formula for $T(n,m)$, or one can do the asymptotic analysis directly using the same methods, but I doubt that it would be very useful.

$\endgroup$
1
$\begingroup$

Hint: expand the equation: $$T(m,n) = T(m-2,n) + T(m-2, n-1) + T(m,n-2) + T(m-1,n-2) + 3T(m-1,n-1) + 1$$

As $T(m,n)$ is related to $3T(m-1,n-1)$ we can say $T(m,n) = \Omega(3^{min(m,n)})$.

$\endgroup$
  • $\begingroup$ The basic idea is sound, but it doesn't quite show what you claim. It suggests that $T(m,n) = \Omega(3^{\min(m,n)})$. $\endgroup$ – Yuval Filmus Feb 9 '18 at 19:59
  • $\begingroup$ @YuvalFilmus Thanks for your comments. $\endgroup$ – OmG Feb 9 '18 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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