2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ what are your thoughts on this problem? what have you tried? where did you come across this problem? $\endgroup$ – clathratus Jan 7 at 16:12
  • 1
    $\begingroup$ Edited the question. Didn’t want to “pollute” with my thoughts as I don’t think this can help. $\endgroup$ – 100r Jan 7 at 17:19
  • $\begingroup$ Thank you for editing your question so well (+1). it is rare that new users respond to the request for question edits $\endgroup$ – clathratus Jan 7 at 17:21
  • 1
    $\begingroup$ I’ve been a passive user of this forum many years, so I was expecting someone to ask for what I had previously tried XD. I know that new users asking easy things they need to do as homework is annoying, but is not the case. $\endgroup$ – 100r Jan 7 at 17:28
  • $\begingroup$ @100r Just to clarify the your first additional point: Is it correct that $-2^{mn}+1$ are not part of the summation? $\endgroup$ – flawr Jan 7 at 23:21
2
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Yep, I got this form. I posted the double-summation one because I thought it showed better the symmetry between $m$ and $n$. Thanks for answering, though. Do you know if it can be proved that no better simplification exists? $\endgroup$ – 100r Jan 7 at 16:15
  • $\begingroup$ Proving this is probably not an easy task, but judging by the form it must involve a binomial, as we have found it. It doesn't have the form of a multinomial so I do think this is all we can do. $\endgroup$ – flawr Jan 7 at 16:20
  • $\begingroup$ An idea, (probably not a good one...) : as $2^k-1$ possesses a simple binary expansion ($1111...1$ with $k$ ones), work on bi-cimals. $\endgroup$ – Jean Marie Jan 8 at 7:19
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I’ve been trying to think about a way of using this decomposition LDU to efficiently compute a(m,n), but I couldn’t come up with anything. Is there something that I’m missing or your answer was not directed towards efficiency? Thanks for answering anyway. $\endgroup$ – 100r Jan 12 at 16:21
  • $\begingroup$ @100r: for the moment, I posted these preliminary considerations to show : the matrix approach, the connection with N. of non-singular matrices, the connection with q-binomials which may be of help for further developments. I also will see if it is possible to come out with some result of interest. $\endgroup$ – G Cab Jan 12 at 17:21
  • $\begingroup$ Nice, thank you so much. $\endgroup$ – 100r Jan 12 at 17:31
  • $\begingroup$ @100r: are you looking for an exact o.g.f, or for an asymptotic one ? $\endgroup$ – G Cab Jan 12 at 23:30
  • $\begingroup$ A “good looking” exact o.g.f. (or an exact exponential g.f., or another kind if exact g.f.). I say good looking because the idea is easily compute a(m,n) from it. I added an item in my question about finding an e.g.f. $\endgroup$ – 100r Jan 13 at 9:11

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.