Combinatorial identity concerning integral matrices with prescribed row sums and column sums

Question

How to prove the following identity?

Let $r = (r_1, r_2, \ldots, r_d)$ and $c = (c_1, c_2, \ldots, c_d)$ be sequences of natural numbers such that $s = r_1 + r_2 + \cdots + r_d = c_1 + c_2 + \ldots + c_d$.

Denote by $\mathcal{M}(r,c)$ the set of matrices whose rows sums and column sums are $r$ and $c$ respectively.

Then $$ \sum_{M = (m_{i,j}) \in \mathcal{M}(r,c)} \prod_{i,j} \frac{1}{m_{i,j}!} = \frac{s!}{(\prod_{i=1}^d r_i!) (\prod_{j=1}^d c_j!)}. $$

I remember that once I saw this identity, but I could not find the source now.

Answer 1

Here is a quick way to see this with generating functions. By using the notation $[\mathbb x^r]f(\mathbb x)$ for the coefficient of a monomial $\mathbb x^r$ in a formal power series $f(\mathbb x)$, we can write:

$$LHS=\left[\prod_{i,j}x_i^{r_i}y_j^{c_j}\right]\prod_{i,j}e^{x_iy_j}=\left[\prod_{i,j}x_i^{r_i}y_j^{c_j}\right]e^{(x_1+\cdots+x_d)(y_1+\cdots+y_d)}$$ $$=\frac{1}{s!}\binom{s}{r_1,r_2,\dots,r_d}\binom{s}{c_1,c_2,\dots,c_d}=RHS$$

Answer 2

A more combinatorial approach might be like this: The given sum is $$I=\frac{1}{s!} \sum_{M = (m_{i,j}) \in \mathcal{M}(r,c)} \prod_{i,j} \frac{s!}{m_{i,j}!}$$

We can write, $$I=\frac{1}{s!}\binom{s}{r_1,r_2,...,r_d}\sum_{M = (m_{i,j}) \in \mathcal{M}(r,c)} \prod_{i} \binom{r_i}{m_{i,1},m_{i,2}...,m_{i,d}}$$

Let, denote the summation inside as $J$. Then $J$ is the number of ways in which we can break the groups $A_i$ each having $r_i$ elements into further subgroups $A_i\rightarrow \{b_{i,1},b_{i,2},..,b_{i,d}\}$ such that each $b_{i,j}$ has $m_{i,j}$ elements and $\sum_{i}m_{i,j}=c_j$.

W.l.o.g let, $A_1$ has elements $1,2...r_1$; $A_2$ has $r_1+1,r_1+2,...,r_2$ and so on. Now if we see aforementioned grouping as collections $B_j=\{b_{1,j},b_{2,j}....,b_{d,j}\}$ we can see each $B_j$ has always $c_j$ elements and each $B_j$ has all possible combinations from $1,2,...,s$. So, $J=\binom{s}{c_1,c_2,...,c_d}$.

Hence, $I=\frac{s!}{(\prod_{i}r_i!)(\prod_{j}c_j!)}$