9

I know Vandermonde's convolution for binomial coefficients:

$$\sum_{j=0...k} \binom{n}{j} \binom{m}{k-j} = \binom{n+m}{k}$$

Is there a similar multiplicative convolution? More precisely, is there a simple formula for the coefficients $a(k_j,k'_j,k)$ in the following identity?

$$\sum_{j} a(k_j,k'_j,k) \binom{n}{k_j} \binom{m}{k'_j} = \binom{n \cdot m}{k}$$

Thanks.

Hoffjan
  • 93
  • 11
    No formula, but a combinatorial definition: $a\left(k_j,k_j^{\prime},k\right)$ is the number of all ways to fill a $k_j\times k_j^{\prime}$ matrix with $0$'s and $1$'s such that there are altogether $k$ $1$'s and such that every row has at least one $1$ and such that every column has at least one $1$. (This interpretation I learnt from Christian Sattler when I asked him pretty much the same question.) – darij grinberg Apr 14 '11 at 21:21
  • 2
    @Darij, I also remember giving the same answer when you asked this question on ML a while back. :) – Gjergji Zaimi Apr 14 '11 at 23:32
  • Can either of you find that thread? It was really fairly interesting. I recall one of you asked a follow-up question about ${ {n \choose a} \choose b}$...? – Qiaochu Yuan Apr 15 '11 at 02:57
  • 1
    Oh, probably it was you, Gjergji, and I have confused you with Christian since he did another nice combinatorial solution about 0-1-matrices on ML. The thread is http://www.artofproblemsolving.com/Forum/viewtopic.php?f=43&t=299793 . – darij grinberg Apr 15 '11 at 06:23

3 Answers3

10

Riordan and Stein, in "Arrangements on Chessboards" (Journal of Combinatorial Theory, Series A, 12 72-80, 1972) consider the numbers $A(r,s,k)$ defined by $$\sum_{r,s} \binom{n}{r} \binom{m}{s} A(r,s,k) = \binom{nm}{k},$$ or, as others have pointed out, the number of $r \times s$ $(0,1)$-matrices with $k$ $1$'s and with at least one $1$ in every row and every column. They obtain two formulas for these numbers:

$$A(r,s,k) = \sum_{i,j} (-1)^{i+j+r+s} \binom{r}{i} \binom{s}{j} \binom{ij}{k},$$

$$A(r,s,k) = \sum_n \frac{r! s!}{k!} S(n,r) S(n,s) s(k,n),$$ where $S(n,r)$ and $s(k,n)$ are Stirling numbers of the second and first kinds, respectively.

They also obtain the recurrence relation $$(k+1)A(r,s,k+1) +k A(r,s,k) $$ $$= rs \left(A(r,s,k) + A(r-1,s,k) + A(r,s-1,k) + A(r-1,s-1,k)\right)$$ and that $A(r,s,k)$ is the coefficient of $t^k$ in $$\sum_j (-1)^{s+j} \binom{s}{j} \left( (1+t)^j-1) \right)^r,$$ as in Richard Stanley's answer.

Mike Spivey
  • 3,253
7

The interpretation darij gives in the comments has a fairly straightforward proof: ${nm \choose k}$ is precisely the number of $n \times m$ matrices of $0$s and $1$s with exactly $k$ $1$s. One can think of the terms ${n \choose k_j}$ and ${m \choose k_j'}$ as picking out the rows and columns that these $1$s inhabit, and then the coefficient $a(k_j, k_j', k)$ describes precisely the number of ways to distribute the $1$s given these constraints.

(Note that the coefficients $a(k_j, k_j', k)$ are unique, for example by repeatedly applying finite difference operators in $m$ and $n$.)

Qiaochu Yuan
  • 114,941
7

By a simple Inclusion-Exclusion argument, the number of $r\times s$ (0,1)-matrices with $k$ 1's and with at least one 1 in every row and column is the coefficient of $x^k$ in $$ \sum_{j=0}^s (-1)^j{s\choose j}((1+x)^{s-j}-1)^r. $$ This gives a formula for $a(k_j,k'_j,k)$ as a triple sum.

Richard Stanley
  • 49,238