Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
10  
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 2: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 artofproblemsolving.com/Forum/viewtopic.php?f=43&t=299793 . –  darij grinberg Apr 15 '11 at 6:23

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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