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$? enter image description here 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?


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


  • 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*}


  • 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

  • $\begingroup$ Thank you so much for your clear answer! Is there any book where I can learn the q-binomial identity and other similar useful identities? $\endgroup$ – Henry Sep 18 '18 at 13:22
  • $\begingroup$ @SunghyukPark: Many thanks for accepting the answer and granting the bounty. $\endgroup$ – Markus Scheuer Sep 18 '18 at 15:47
  • $\begingroup$ @SunghyukPark: At the time I'm writing from my mobile. I will soon add some refs when I'm at home. $\endgroup$ – Markus Scheuer Sep 18 '18 at 15:48
  • $\begingroup$ @SunghyukPark: I've added some references to $q$-related material. $\endgroup$ – Markus Scheuer Sep 18 '18 at 18:30
  • $\begingroup$ Awesome! Thank you again for the wonderful answer. $\endgroup$ – Henry Sep 18 '18 at 20:43

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.