Does this bivariate function have a non-summation form or a good looking generating function?

Question

The function is this one: For $m,n$ positive integers, $$a(m,n)=\sum_{k=0}^n\sum_{i=0}^m {n\choose k}{m\choose i}(-1)^{n-k}(-1)^{m-i}2^{ki}$$ $$ = \sum_{k=0}^n {n\choose k}(-1)^{n-k}(2^k-1)^m.$$

I also know that:

1. It satisfies the recurrence equation $$\left( \sum_{j=1}^m\sum_{k=1}^n{m \choose j}{n \choose k}a(j,k)\right)-(2^{mn}-1)=0.$$ Note that when $m=n=1$ the summation only has one term and we get the base case $a(1,1)=1$. I also want to note that $$2^{mn}-1=\sum_{i=1}^{mn}{mn \choose i}$$ but I couldn’t come up with a binomial relation which let me simplify the recurrence.
2. $a(m,n)\sim 2^{mn}$, so I think that $a(m,n)$ is not an holonomic “sequence”. Hence it doesn’t exist a $P$-finite recurrence for $a(m,n)$, so I it’s possible that the recurrence in 1. cannot be simplified either.
3. $a(m,n)=$ A183109 sequence of OEIS.
4. $a(n,n)=$ A048291 sequence of OEIS. There appears: $$\text{e.g.f.} \sum_{n=0}^\infty((2^n-1)^n\exp((1-2^n)x)\frac{x^n}{n!}$$ I guess that “e.g.f.” stands for “exponential generating function”, but I don’t think this is an exponential generating function (is it?).
5. $a(m,n)$ appears in this forum (Number of $(0,1)$ $m\times n$ matrices with no empty rows or columns), and the main answer also conjectures no better form exists.
6. If $$g(x)=\sum_{k=0}^\infty (2^k-1)^m \frac{x^k}{k!},$$ i.e. $g$ is an e.g.f. of $(2^k-1)^m$, then $$e^{-x}\cdot g(x)=\sum_{n=0}^\infty a(m,n)\frac{x^n}{n!},$$ i.e. $e^{-x}\cdot g(x)$ is an e.g.f. of $a(m,n)$. The thing is that I wasn’t able to find a good looking function $g(x)$.

I want to find a way to efficiently calculate $a(m,n)$ (that’s why my interest in finding a non-summation form or a generating function for the bivariate sequence).

The thing is that I suspect that not non-summation form nor good looking function exist, but I’m not an expert so maybe somebody sees the function and can find one of those, or explain why none of those exist.

Thanks in advance.

Answer 1

You can "factor" out one summation as follows. (It doesn't matter which one, as the expression is symmetric w.r.t. $m$ and $n$.) I don't think we can simplify it further, but I might be wrong.

$$\begin{align} a(m,n)&=\sum_{k=0}^n\sum_{i=0}^m {n\choose k}{m\choose i}(-1)^{n-k}(-1)^{m-i}2^{ki} \\ &=\sum_{k=0}^n {n\choose k}(-1)^{n-k} \sum_{i=0}^m {m\choose i}(-1)^{m-i}(2^{k})^i \\ &=\sum_{k=0}^n {n\choose k}(-1)^{n-k} (2^k-1)^m \end{align}$$

Answer 2

Let me make some preliminary considerations about the properties of such a bivariate function

Matricial form

If we write $a(n,m)=a(m,n)$ into a square symmetric matrix, of whichever dimension, indexed from $0$ $$ {\bf A} = \left\| {\,a(n,m)\;} \right\| $$ then $\bf A$ is real symmetric (real Hermitian).
Thus we can transform the same into the product of a lower triangular matrix $\bf L$, of a diagonal matrix $\bf D$ and of the transpose of $\bf L$. $$ {\bf A} = {\bf L}\,{\bf D}\;\overline {\bf L} $$

It comes out that $L$ is the Triangular matrix in OEIS A139382, and if ${\bf G}_{\,{\bf q}} $ denotes the matrix of the q-binomial coefficients $$ {\bf G}_{\,{\bf q}} = \left\| {\,\binom{n}{m}_{\,q} \;} \right\| $$ then $\bf L$ is given by $$ {\bf L} = {\bf G}_{\,{\bf 1}} ^{\, - \,{\bf 1}} \;{\bf G}_{\,{\bf 2}} $$ being ${\bf G}_{\,{\bf 1}}$ the Pascal matrix and ${\bf G}_{\,{\bf 2}} $ the matrix.

Instead the non-null elements of $\bf D$ are given by $$ {\bf D} = \left\| {\,d(n)\,{\rm dia}\;} \right\|\quad :\quad d(n) = \prod\limits_{k = 0}^{n - 1} {\left( {2^{\,n} - 2^{\,k} } \right)} $$ which is seq. A002884: "Number of nonsingular n X n matrices over GF(2); order of Chevalley group A_n (2); order of projective special linear group PSL_n(2)".

The matrix equivalent of the symmetric formula for $a$ is $$ \bbox[lightyellow] { \eqalign{ & {\bf T} = \left\| {\,2^{\,n\,m} \;} \right\|\quad \overline {{\bf G}_{\,{\bf 1}} } = transpose\;{\bf G}_{\,{\bf 1}} \cr & {\bf A} = {\bf G}_{\,{\bf 1}} ^{\, - \,{\bf 1}} \;{\bf T}\;\overline {{\bf G}_{\,{\bf 1}} } ^{\, - \,{\bf 1}} \quad \Leftrightarrow \quad {\bf T} = {\bf G}_{\,{\bf 1}} \;{\bf A}\;\overline {{\bf G}_{\,{\bf 1}} } \cr} } \tag{1}$$

q_Analog

The tie with q-Analog calculuscomes from the fact that $$ \eqalign{ & a(n,m) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} { \left( { - 1} \right)^{\,n - k} \binom{n}{k}\left( {2^{\;k} - 1} \right)^{\,m} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} { \left( { - 1} \right)^{\,n - k} \binom{n}{k} \left( {{{1 - 2^{\;k} } \over {1 - 2}}} \right)^{\,m} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,n - k} \binom{n}{k} \left[ k \right]_{\,2} ^{\,m} } \cr} $$

For the Binomial Inversion (also from the matrix representation above) we get $$ \left[ n \right]_{\,2} ^{\,m} = \left( {2^{\;n} - 1} \right)^{\,m} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} { \binom{ n}{k}a(k,m)} $$

Finite Difference

Indicating the finite difference of a function $f(x,y)$ wrt the variable $x$ as $$ \Delta _{\,x} f(x,y) = f(x + 1,y) - f(x,y) $$ then the iterations are $$ \Delta _{\,x} ^{\,n} f(x,y) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,n - k} \binom{n}{k}f(x + k,y)} $$

Therefore $$ \bbox[lightyellow] { \eqalign{ & a(n,m) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\sum\limits_{\left( {0\, \le } \right)\,i\,\left( { \le \,m} \right)} { \left( { - 1} \right)^{\,n - k} \binom{n}{k} \left( { - 1} \right)^{\,m - i} \binom{m}{i} 2^{\;ki} } } = \left. {\Delta _{\,x} ^{\,n} \Delta _{\,y} ^{\,m} \;2^{\;x\,y} } \right|_{\,x\, = \,y\, = \,0} \quad \Leftrightarrow \cr & \Leftrightarrow \quad 2^{\;n\,m} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} { \sum\limits_{\left( {0\, \le } \right)\,i\,\left( { \le \,m} \right)} { a(k,i) \binom{n}{k} \binom{m}{i} } } \cr} } \tag{2}$$ which is the equivalent of (1).

That means that $a$ is the coefficient of the double Newton Series of $2^{nm}$.