# Seeking for a meaning: a curious symmetry

Suppose $\Phi(m,n)=(2m)!^n\prod_{k=1}^n\binom{2m+2k+x}{2k+x}$. Then, algebraically, it is trivial to see that $$(2m)!^n\prod_{k=1}^n\binom{2m+2k+x}{2k+x}=(2n)!^m\prod_{k=1}^m\binom{2n+2k+x}{2k+x}.$$

Question. Is there a combinatorial (or anything but algebraic) reason why $\Phi(m,n)=\Phi(n,m)$?

UPDATE. I still await for any suggestion.

• Perhaps rewriting the above identity using ${a+b\choose a}={a+b\choose b}$ might ease the way for discovering such an interpretation. – Lucian May 12 '17 at 6:57
• It is not only symmetric, but has a form $f(n+m)/f(n)f(m)$, where $f(n)=\prod_{k=1}^{n} (x+2k)!$. Maybe this suggests some binomial-like interpretation. – Fedor Petrov May 12 '17 at 11:02
• I can only assume this is also going to be the title of your memoir. – Jair Taylor May 12 '17 at 16:32

The question is a bit strange, because it would also be true if one removes all the $2$ from the statement. Namely: $$\Phi'(m, n):=m!^n \prod_{k = 1} ^ n \binom{m+k+x}{m}$$ is also symmetric.

Let me explain the symmetry of this modified function $\Phi'$, and you can certainly adapt it to your $\Phi$. But the explanation is somewhat artificial.

Assume harmlessly that $x$ is a non-negative integer. Consider a grid of size $m \times n$. The rows and columns are indexed $0, \cdots, m - 1$ and $0, \cdots, n - 1$, respectively, and a cell is indexed $(i, j)$ if it is in row $i$ and column $j$.

Now one wants to fill in the grid with integers, one in a cell, with the following restriction: every integer is at most $m + n + x$, and the integer in the cell $(i, j)$ should be strictly larger than $i + j$.

Here is the claim:

## For every $k \in \{0, \cdots, n - 1\}$, the number of different ways to fill in the column $k$ is equal to $$m!\binom{m + n - k + x}{m}.$$

This explains everything.

To prove the claim, it is (again) algebraically obvious, but if you really want a combinatorial proof, then there is the following bijection:

$$\{(a_1, \cdots, a_m): a_i \in \{1, \cdots, M\}, a_i \neq a_j \} \longleftrightarrow \{(c_1, \cdots, c_m): c_i \in \{1, \cdots, M - i\}\},$$

which is described as follows: given such $(a_i)_i$, define $c_i$ to be the integer such that $a_i$ is the $c_i$-th largest number in the set $\{1, \cdots, M\} \backslash \{a_1, \cdots, a_{i - 1}\}$. The procedure is obviously reversible, hence gives a bijection.

Rewriting $\Phi(m,n)$ as $$\prod_{k=1}^n P_{2m}^{2m+2k+x},$$ where $P_m^n:=\frac {n!}{(n-m)!},$ the asserted symmetry is equivalent to $$\prod_{k=1}^n P_{2m}^{2m+2k+x}=\prod_{k=1}^m P_{2n}^{2n+2k+x}.$$ This can be explained by the following observation.

Lemma. $P_{m_1+m_2}^n=P_{m_2}^{n-m_1}\cdot P_{m_1}^n,$ for $m_1,m_2\geq 0$ and $m_1+m_2\leq n.$

Let $$P_{ij}:=P_2^{2(m-i+1)+2j+x},1\leq i\leq m,1\leq j\leq n.$$ Repeated use of Lemma shows that $$\prod_{j=1}^n P_{ij}=P_{2n}^{2(m-i+1)+2n+x}$$ and $$\prod_{i=1}^m P_{ij}=P_{2m}^{2m+2j+x}.$$ It follows that $$\prod_{j=1}^n P_{2m}^{2m+2j+x}=\prod_{j=1}^n\prod_{i=1}^m P_{ij}=\prod_{i=1}^m\prod_{j=1}^n P_{ij}$$ $$=\prod_{i=1}^m P_{2n}^{2(m-i+1)+2n+x}=\prod_{k=1}^m P_{2n}^{2n+2k+x},$$ as required.

EDIT: For $r\geq 1$, the following holds: $$(rm)!^n\prod_{k=1}^n {rm+rk+x\choose rk +x}=(rn)!^m\prod_{k=1}^m{rn+rk+x\choose rk +x},$$ since both sides equal $$\prod_{1\leq i \leq m,1\leq j\leq n}P_r^{r(i +j)+x},$$ which follows from the product formula for permutations as in the Lemma. This may still be too algebraic but hope it helps.

• OK, but OP asked for a combinatorial, not algebraic, reason. – Gerry Myerson Jun 19 '17 at 2:31