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!
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!
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
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$?