Solving a two-variable recurrence
Let $P = \sum_{n,m \geq 0} T(n,m) x^n y^m$. We have
$$
\begin{align*}
P &amp;= \sum_{n,m \geq 1} T(n,m) x^n y^m \\ &amp;=
\sum_{n,m \geq 1} [T(n-1,m) + T(n,m-1) + T(n-1,m-1)+1] x^n y^m \\ &amp;=
\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 \\ &amp;= (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'&lt;n,m'&lt;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.