I was solving a question that says that we're spreading $N^2$ balls into a grid $N \times N$, that has $N^2$ $1\times 1$ squares.
I had these two questions one after another and I failed the second one:
- In how many ways we can spread the balls such that we get exactly two empty columns and in the rest of the little squares there's atleast one ball.
So I just went and did $N \choose 2$${N^2-2N + 2N +1} \choose2N$, and got my answer.
2) In how many ways we can spread the balls such that we have exactly 2 empty columns?
And here I did the same thing I chose $2$ to be empty, and spread the balls in the rest of the empty squares.
When I went to look for the answer, this was answered using inclusion-exclusion principle, and I realized I have a big problem with understanding when should I really think about inclusion-exclusion, It's still my first practice exam, but I think it's a very big problem that I couldn't find the difference in this question and know in which way to answer.
I would appreciate any tips about this topic from experienced people, that would really help me improve my understanding of this subject.
Thanks in advance to everyone.
In the first problem you have two empty columns, and each of the remaining $N(N-2)$ squares is non-empty. This makes it a simple stars and bars problem: after you put one ball on each of those squares, you can distribute the remaining $2N$ balls to them arbitrarily, and this can be done in $\binom{N(N-2)+2N-1}{2N}$ ways.
In the second problem you must have exactly $2$ columns that are completely empty, so you must have at least one ball in each of the other $N-2$ columns, but any (or all) of those columns can be partly empty. It’s harder to count these arrangments. You might at first think that there are
$$\binom{N(N-2)+N^2-1}{N^2}=\binom{2N^2-2N-1}{N^2}$$
of them, since you’re distributing $N^2$ balls amongst $N(N-2)$ squares, but that includes all of the arrangements that leave one or more of the $N-2$ columns completely empty, and we don’t want to count those.
We can start with $\binom{2N^2-2N-1}{N^2}$ as a first approximation, but then we have to subtract the number of arrangements that leave one of those $N-2$ columns empty. For each of the $N-2$ columns there are
$$\binom{N(N-3)+N^2-1}{N^2}=\binom{2N^2-3N-1}{N^2}$$
ways to distribute the $N^2$ balls to the remaining $N-3$ columns, so a better approximation is
$$\binom{2N^2-2N-1}{N^2}-(N-2)\binom{N^2-3N-1}{N^2}\,.$$
Unfortunately, we’ve now subtracted too much: any arrangement of the balls that leaves $2$ of the $N-2$ columns completely empty has been counted once in the first term and subtracted twice in the second term, once for each of the $2$ extra empty columns, so it’s been counted altogether $-1$ times. We need to add it back in. There are $\binom{N-2}2$ pairs of columns that are not supposed to be completely empty, and for each pair there are
$$\binom{N(N-4)+N^2-1}{N^2}=\binom{2N^2-4N-1}{N^2}$$
arrangements that leave that pair completely empty, so the next correction gives us
$$\binom{2N^2-2N-1}{N^2}-(N-2)\binom{N^2-3N-1}{N^2}+\binom{N-2}2\binom{N^2-4N-1}{N^2}$$
as a third approximation. The full inclusion-exclusion computation leaves us with
$$\sum_{k=0}^{N-2}(-1)^k\binom{N-2}k\binom{2N^2-(k+2)N-1}{N^2}$$
ways to distribute the $N^2$ balls to the other $N-2$ columns so that each of them gets at least one ball, and since there are $\binom{N}2$ pairs of columns to be the empty ones, the final answer is
$$\binom{N}2\sum_{k=0}^{N-2}(-1)^k\binom{N-2}k\binom{2N^2-(k+2)N-1}{N^2}\,.$$