# Balls-and-bins type problem

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!

• @Gerry: It is not the same problem. Given these numbers, you can choose bins from each row in different ways. – Sergei Ivanov Feb 8 '11 at 0:09
• Scott - what are you driving at here? You surely have something in mind when you make a comment like that, but reading the "how to ask" page doesn't make it obvious what that is. Perhaps mention what sort of revision you think is appropriate? – James Martin Feb 8 '11 at 9:10
• Either people have this confused with a different problem, or else there is something I am overlooking. For example, I don't see a closed form expression for the count when $k=2n$. For $n=4, k=8$, the count is $10896 = 2^4 \times 3 \times 227$. I voted to reopen. – Douglas Zare Feb 8 '11 at 9:52
• This "looks like homework" / "too localized" / "give motivation" / "looks too elementary" policy is beginning to go berserk. The problem is definitely not trivial. I'd suggest the Sylvester sieve (aka principle of inclusion and exclusion) for a sum formula, but I don't know whether an explicit one exists. – darij grinberg Feb 8 '11 at 10:56
• @Sheldon, your question is much better than I originally gave it credit for, but it's still missing one important thing, namely, any evidence that you have put any thought into it yourself. It's hard to get other people interested in a problem when it looks as though you weren't interested enough to do any work on it yourself. – Gerry Myerson Feb 8 '11 at 11:59

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