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.

  • $\begingroup$ Perhaps rewriting the above identity using ${a+b\choose a}={a+b\choose b}$ might ease the way for discovering such an interpretation. $\endgroup$ – Lucian May 12 '17 at 6:57
  • 3
    $\begingroup$ 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. $\endgroup$ – Fedor Petrov May 12 '17 at 11:02
  • 6
    $\begingroup$ I can only assume this is also going to be the title of your memoir. $\endgroup$ – 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.

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

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.