Balls-and-bins type problem

Question

Suppose I have an n-by-n array of bins, and I want to choose k (k >= n) bins from these n^2 bins such that each row of the array has at least one bin chosen. How many ways are there of doing this?

Thanks!

Answer 1

The comments were, in my opinion, closer the first time -- this is a standard application of inclusion-exclusion and could be a homework exercise. The number of ways to choose $k$ boxes from a set of $i$ rows (without worrying about hitting all the rows) is $\binom{in}{k}$. The number of ways to choose $i$ rows is $\binom{n}{i}$. Thus the total number of ways to make your choices so that every row gets hit is $$\sum_{i = 0}^n (-1)^{n - i} \binom{in}{k} \binom{n}{i}.$$ (Perhaps this can be rewritten in other ways that appeal to you more.)

A suggestion to Sheldon: this question has a very elementary look and feel (and indeed it turns out to be very elementary). When posting a problem of this sort, you should provide some information about why it's of interest to you, so as to help distinguish the homework-cheaters from people who have interesting (e.g., research-related) reasons for needing the solution to elementary problems. I also agree with Gerry's final comment and an-mo-user's comment here: http://mathoverflow.tqft.net/discussion/947/ballsandbins-type-problem-question-closed

Answer 2

More information would be nice. The answer by JBL above is perfectly fine but there might be other forms for the answer. In the special case $k=n$ the answer is $n^n$, that is indeed $\sum_{i = 0}^n (-1)^{n - i} \binom{in}{n} \binom{n}{i}$ but I like the first form better.For $k$ past $n^2-n$ the answer is just $\binom{n^2}{k}$. In this case the formula given quickly reduces to that.

One could do the sum over all ordered partitions $k=\sum_1^nk_j$ of $k$ into $n$ positive parts of $\prod\binom{n}{k_j}$. That would be practical if $k-n$ is small. One can collect like terms so essentially use unordered partitions with appropriate multinomial coefficients. Hence for $k=n+3$ (if I made no errors) one either has a row with 4 OR a row with 3 and one with 2 OR three rows with 2 things in them (and one thing in each other row). $$\binom{n}{1,n-1}\binom{n}{4}^1\binom{n}{1}^{n-1}+\binom{n}{1,1,n-2}\binom{n}{3}^1\binom{n}{2}^1\binom{n}{1}^{n-1}+\binom{n}{3,n-3}\binom{n}{2}^3\binom{n}{1}^{n-3}$$ $$=n^n\left(\binom{n}{4}+(n-1)\binom{n}{3}\binom{n}{2}+\binom{n}{3}\left(\frac{n-1}{2}\right)^3\right)$$ $$=n^n\binom{n}{3}\frac{5n^3-11n^2+9n-7}{8}$$

A similar thing would work for $k $ slightly less than $n^2-n.$

So what kind of answer are you looking for and what can you say about $k$?