Finding a combinatorial formula for the following sequence of tables

Question

While studying a subject in mathematical physics and topology (which is not necessarily relevant to this question anyway), I bumped into the following sequence of tables, let's call them $M_0, M_1, M_2, M_3, M_4, \cdots$. (The table goes on, but it gets a little too big after $M_4$, so I could only write down one quarter of $M_5$.) These tables have some interesting patterns and symmetry, but a simple formula completely characterizing them is still missing. So the question is : what would be a simple (combinatorial) formula for $M_n$? Let me briefly explain the meaning of the entries. Each entry of these matrices is a multiset of integers. I used exponent for multiplicity; e.g. $6,4^2,2^2,0,-6,-8,-10$ actually means $6,4,4,2,2,0,-6,-8,-10$. Also in the last two tables overlined numbers $\overline{n}$ just mean $-n$. (I had to introduce this notation to save up space.)

Finally, let me list some of obvious patterns you can see :

1. $M_n$ is $(n+1)$-by-$ (n+1)$, and its entries are all even/odd depending on the parity of $\frac{n(n+1)}{2}$.
2. $M_n$ is symmetric under flipping along the diagonal.
3. If you flip $M_n$ either vertically or horizontally, you get $-M_n$.
4. Let's index rows and columns of $M_n$ by numbers $0, 1, \cdots, n$. Then the $(i,j)$-entry of $M_n$ is a multiset of size $\binom{n}{i}\binom{n}{j}$.
5. The very outer entries have a very natural combinatorial description : $(M_n)_{0,j} = \{p(1)+\cdots+p(n) \mid p\in P^{(n)}_{2j-n}\}$ as a multiset where $P^{(n)}_{m}:=\{p : \{0, 1, \cdots, n\}\rightarrow \mathbb{Z} \mid p(0)=0, p(n)=m, |p(i)-p(i+1)|=1\}$; i.e. the set of discrete paths. In other words, $(M_n)_{0,j} = \{\pm 1 \pm 2 \cdots \pm n \mid \text{there are exactly }j\text{ number of pluses}\}$
6. $(M_n)_{0,j}$ "divides" $(M_n)_{i,j}$ in a sense that $(M_n)_{i,j}$ can be expressed as a sumset of $(M_n)_{0,j}$ and some other set. For instance, for $n\geq 2$, $(M_n)_{1,1}=(M_n)_{0,1}+\{2n, 2n-2, \cdots, 6, 4, -2n\}$.

Hopefully, we can find a simple combinatorial formula for $M_n$ which makes all of the observations above manifest.

---

Added 9/5 :

I just realized that the pattern becomes so much clearer once you divide every column by the first column. From this I was able to figure out that if we represent each entry of the form $\{r_1, \cdots, r_k\}$ by the polynomial $q^{r_1/2}+\cdots+q^{r_k/2}$, $$(M_n)_{i,j} = q^{-\frac{n(n+1)}{4}}\cdot\left(\text{coefficient of }x^iy^j\text{ in }\prod_{k=1}^{n}{(1+q^k x)}\prod_{k=1}^{i}{(1+q^{k-n-1}y)}\prod_{k=i+1}^{n}{(1+q^k y)}\right)$$ This is nice, but still not completely satisfactory, as it doesn't seem quite clear from this formula that $(M_n)_{i,j}=(M_n)_{j,i}$. Hence my question becomes : Is there a nice symmetric formula for this?

Answer 1

We use q-binomial coefficients to obtain a symmetrical representation in $i$ and $j$ and particularly apply the following q-binomial identity with integral $n>0$: \begin{align*} \prod_{k=0}^{n-1}(1+q^kx)=\sum_{k=0}^nq^{\binom{k}{2}}\binom{n}{k}_qx^k\tag{1} \end{align*}

It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. In the following we omit the factor $q^{-\frac{n(n+1)}{4}}$.

We consider for $n>0, 0\leq i,j\leq n$ \begin{align*} [&x^iy^j]\prod_{k=1}^n(1+q^kx)\prod_{k=1}^{i}(1+q^{k-n-1}y)\prod_{k=i+1}^{n}(1+q^ky)\\ &=\left([x^i]\prod_{k=1}^n(1+q^kx)\right)\left([y^j]\prod_{k=1}^{i}(1+q^{k-n-1}y)\prod_{k=i+1}^{n}(1+q^ky)\right)\tag{2} \end{align*} with the usual convention that the empty product is set to $1$.

We start with the simpler part and calculate at first the coefficient of $[x^i]$ \begin{align*} [x^i]\prod_{k=1}^n(1+q^kx)&=[x^i]\prod_{k=0}^{n-1}(1+q^{k+1}x)\\ &=[x^i]\sum_{k=0}^nq^{\binom{k}{2}}\binom{n}{k}_q(qx)^k\tag{3}\\ &=q^{\binom{i}{2}+i}\binom{n}{i}_q\tag{4}\\ &=q^{\binom{i+1}{2}}\binom{n}{i}_q\tag{5} \end{align*}

Comment:

• In (3) we apply (1)

• In (4) we select the coefficient of $x^i$.

Next we get the coefficient of $y^j$ \begin{align*} [y^j]&\prod_{k=1}^i(1+q^{k-n-1}y)\prod_{k=i+1}^n(1+q^ky)\\ &=[y^j]\prod_{k=0}^{i-1}\left(1+q^{k-n}y\right)\prod_{k=0}^{n-i-1}\left(1+q^{k+i+1}y\right)\\ &=[y^j]\sum_{k=0}^{i}q^{\binom{k}{2}}\binom{i}{k}_q\left(q^{-n}y\right)^k\sum_{l=0}^{n-i}q^{\binom{l}{2}}\binom{n-i}{l}_q\left(q^{i+1}y\right)^l\tag{6}\\ &=\sum_{k=0}^{\min\{i,j\}}q^{\binom{k}{2}-nk}\binom{i}{k}_q[y^{j-k}]\sum_{l=0}^{n-i}q^{\binom{l}{2}}\binom{n-i}{l}_q\left(q^{i+1}y\right)^l\tag{7}\\ &=\sum_{k=0}^{\min\{i,j\}}q^{\binom{k}{2}-nk}\binom{i}{k}_qq^{\binom{j-k}{2}}\binom{n-i}{j-k}_qq^{(i+1)(j-k)}\tag{8} \end{align*}

Comment:

• In (6) we apply (1) to each product

• In (7) we select the coefficient of $y^j$ and apply the rule $[y^j]y^pA(y)=[y^{j-p}]A(y)$.

• In (8) we select the coefficient of $y^{j-k}$.

Multiplying (5) with (8) we obtain \begin{align*} q^{\binom{i+1}{2}}&\binom{n}{i}_q\sum_{k=0}^{\min\{i,j\}}q^{\binom{k}{2}-nk}\binom{i}{k}_qq^{\binom{j-k}{2}}\binom{n-i}{j-k}_qq^{(i+1)(j-k)}\\ &=\binom{n}{i}_q\sum_{k=0}^{\min\{i,j\}}\binom{i}{k}_q\binom{n-i}{j-k}_qq^{\binom{i+1}{2}+\binom{k}{2}-nk+\binom{j-k}{2}+(i+1)(j-k)}\\ &=\binom{n}{i}_q\sum_{k=0}^{\min\{i,j\}}\binom{i}{k}_q\binom{n-i}{j-k}_qq^{\frac{1}{2}\left(i^2+j^2\right)+\left(\frac{1}{2}-k\right)(i+j)+ij+k^2-nk-k}\\ &=\binom{n}{i}_qq^{\frac{1}{2}\left(i^2+j^2\right)+\frac{1}{2}\left(i+j\right)+ij}\sum_{k=0}^{\min\{i,j\}}\binom{i}{k}_q\binom{n-i}{j-k}_qq^{k(-n-1-i-j+k)} \end{align*}

omitting in the last line the powers of $q$ symmetrically in $i$ and $j$ and using $q$-factorial notation $\binom{n}{k}_q=\frac{[n]_q!}{[k]_q![n-k]_q!}$ we finally obtain \begin{align*} \color{blue}{\binom{n}{i}_q}&\color{blue}{\sum_{k=0}^{\min\{i,j\}}\binom{i}{k}_q\binom{n-i}{j-k}_qq^{k(-n-1-i-j+k)}}\\ &=\sum_{k=0}^{\min\{i,j\}}\binom{n}{i}_q\binom{i}{k}_q\binom{n-i}{j-k}_qq^{k(-n-1-i-j+k)}\\ &=\sum_{k=0}^{\min\{i,j\}}\frac{[n]_q!}{[i]_q![n-i]_q!}\cdot\frac{[i]_q!}{[k]_q![i-k]_q!}\\ &\qquad\qquad\cdot\frac{[n-i]_q!}{[j-k]_q![n-i-j+k]_q!}q^{k(-n-1-i-j+k)}\\ &\,\,\color{blue}{=\sum_{k=0}^{\min\{i,j\}}\frac{[n]_q!}{[k]_q![i-k]_q![j-k]_q![n-i-j+k]_q!}q^{k(-n-1-i-j+k)}} \end{align*} From the last line, which is symmetrically in $i$ and $j$ a symmetrical representation of OPs expression can be easily derived.

Note: With respect to a comment from OP here is some material regarding $q$-binomials which was helpful for me.

The nice and gentle surveys

• The q-binomial Theorem by Shaun Cooper

• On the q-binomial coefficients and binomial congruences by Armin Straub

  The thesis

• A Tiling Interpretation of q-Binomial Coefficients by Jonathan Asoze

  The classics

• Integer Partitions by George E. Andrews and Kimmo Eriksson. This is the introductory text to integer partitions for beginners. $q$-related material starts with Chapter 7 Gaussian polynomials.

• The Theory of Partitions by George E. Andrews. This is the introductory text to integer partitions. $q$-related material starts with Section 3.3 Properties of Gaussian polynomials.

  A nice book about the development of $q$-calculus from a historical perspective is

• The History of q-Calculus and a new method by Thomas Ernst