3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ A 3 by 5 board has 15 squares. There are 15 ways to select the first square, 14 ways to select the second square down to 15- 8= 7 ways to select the 9th square. There are $15*14*13*...*8*7= \frac{15!}{6!}$ to select 9 squares out of the 15 in that particular order. If we consider the same 9 square, no matter what the order in which order they are selected, we need to divide by 9!, the number or different ways 9 things can be selected. That gives $\frac{15!}{6!9!}$, the binomial coefficient. $\endgroup$
    – user247327
    Dec 23, 2019 at 5:00

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you very much! I fixed the typo and updated the solution. Does it look fine? $\endgroup$
    – omer
    Dec 22, 2019 at 20:56
  • $\begingroup$ @omer Yes, well done! $\endgroup$
    – Bram28
    Dec 22, 2019 at 20:59
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you very much for the time and effort! Would it be a bother for you to elaborate on the the relation between partitions of 9 into 5 positive parts, each part less than 4- to the problem? I can't see it :( It's a really interesting solution and I'd like to understand it better! $\endgroup$
    – omer
    Dec 23, 2019 at 12:47
  • 1
    $\begingroup$ 5 parts is one for each column, hence positive because each column must be contain at least one filled cell, and each column can have a maximum height of 3, hence less than 4. $\endgroup$
    – JMP
    Dec 23, 2019 at 12:48
  • $\begingroup$ Thank you again! This is a great new way to see this problem! $\endgroup$
    – omer
    Dec 23, 2019 at 12:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .