9
$\begingroup$

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.

$\endgroup$
4
  • 11
    $\begingroup$ 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.) $\endgroup$ Apr 14, 2011 at 21:21
  • 2
    $\begingroup$ @Darij, I also remember giving the same answer when you asked this question on ML a while back. :) $\endgroup$ Apr 14, 2011 at 23:32
  • $\begingroup$ 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}$...? $\endgroup$ Apr 15, 2011 at 2:57
  • 1
    $\begingroup$ 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 artofproblemsolving.com/Forum/viewtopic.php?f=43&t=299793 . $\endgroup$ Apr 15, 2011 at 6:23

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
0
7
$\begingroup$

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$.)

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.