Counting problem: Checking 9 squares out of $3\times 5$ board

Question

I'm self learning some combinatorics and I encountered the following counting problem:

How many ways are there to check 9 squares out of $3\times5$ boards such that in every column there's at least one checked square?

(To be more precise, the board has 3 rows and 5 columns)

I think I know the outline of the solution:

Let $C$ be the set of all possible checking of $9$ squares off the greed and let $C_i$ be the checking of the board where the $i^{th}$ column has no square checked- I then proceed by using the Inclusion - Exclusion principle and so the solution is $$|C|-|C_1\cup C_2\cup C_3\cup C_4\cup C_5|$$

So I have two questions:

1. How many ways there are actually to check the board without restrictions? When I try to think about it I think about selecting a subset of 9 squares out of 15 squares so $\binom{15}{9}$, is this correct? Somehow it does'nt feel like it's the right number ;
2. Is the outline to the solution I wrote above the right approach to this problem?

I know this is very elementary but I'm really confused by all the counting arguments and most of the time my initial intuition turns out to be wrong so any help would be much appreciated!

---

Update with solution

For each $C_i$ we restrict our board to be one column less now, so it's actually checking $9$ squares on a $3\times 4$ board- there are $\binom{12}{9}$ ways to do so. Furthermore, up to renaming the columns this procedure is symmetric so there are $5$ ways to do that.

For any intersection of the form $C_i\cap C_j$ (for $i\neq j$) we restrict our board to be $3\times 3$, and now there's a single way to check the board. There are $\binom{5}{2}$ such intersections. Any bigger intersection would be empty.

From the Inclusion - Exclusion principle we get: $$ \begin{aligned}\left|\bigcup_{i=1}^{5} C_{i}\right| &=5 C_{i}-\left(\begin{array}{c}{5} \\ {2}\end{array}\right)\left|C_{i} \cap C_{j}\right| \\ &=5\left(\begin{array}{c}{12} \\ {9}\end{array}\right)-\left(\begin{array}{c}{5} \\ {2}\end{array}\right) \end{aligned} $$

And so the number of possible checking that fit the decrepstion of the exercise is:

$$ |C|-\left|\bigcup_{i=1}^{5} C_{i}\right|=\left(\begin{array}{c}{15} \\ {9}\end{array}\right)-\left(5\left(\begin{array}{c}{12} \\ {9}\end{array}\right)-\left(\begin{array}{c}{5} \\ {2}\end{array}\right)\right)=3915 $$

Answer 1

I think you mean $$|\color{red}C|-|C_1\cup C_2\cup C_3\cup C_4\cup C_5|$$

Where $C$ is all possible ways to pick $9$ squares ... which is indeed ${15} \choose 9$

OK, but you still need to calculate $|C_1\cup C_2\cup C_3\cup C_4\cup C_5|$ .... easier said than done

Answer 2

I have found a different solution method which gives the same answer as the one you have, so your method must be sound!

We examine partitions of $9$ into $5$ positive parts, each part less than $4$.

These are $22221, 32211, 33111$.

These are our columns, and the number of permutations of each is:

$\binom{5}{4}=5, \binom{5}{1,2}=\frac{5!}{1!2!2!}=30, \binom{5}{2}=10$ respectively.

Each column value of $k$ can be displayed in $\binom{3}{k}$ ways.

All patterns have now been achieved once and once only (by inspection).

The total number is therefore $5\cdot 3^5 + 30\cdot 3^4 + 10\cdot 3^3 = 1215+2430+270=3915$.