Ytukyg

Consider a $5x5$ array. In how many ways can we fill the array with $X$'s and $O$'s so that no two consecutive rows are identical?

My tutor gave us the following answer:

$2^{(25)} - [4*2^{(20)} - 6*2^{(15)} + 4*2^{(10)} - 2^{(5)}]$

A ---------- B --------- C ---------- D --------- E

Where:

$A$ - all possible fillings

$B$ - fillings where 2 cons. rows are the same

$C$ - fillings where 3 cons. rows are the same + 2 cons. rows are the same, and another 2 rows are the same, leaving us with 1 row that can be freely changed

$D$ - $4$ cons. rows are same + $3$ cons rows , and another $2$ rows are same

$E$ - All rows are the same

I hope that my description is rather clear.

The real question is.. Why do we subtract $C$ and $E$, and add $B$ and $D$?
I understand that it has something to do with the intersection(Possibility of some fillings being the same as others), but some fillings also intersect with others, and yet - we add them.

Please, explain it to me.

Your tutor used inclusion–exclusion principle formula in order to count when 2, 3, 4 or 5 rows are the same. Then from all possible fillings he subtracted B-C+D-E. The whole statement for the formula I mentioned, you can find on Inclusion - exclusion principle

A - all possible fillings : since we have 5 rows and 5 columns, in total we have 25 places where we can put either X or O. So from 2 letters (X, O) we choose 1 for each place. We do it in ${2 choose 1}^{25}$ ways.

B - fillings where 2 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^{5}$ ways. Then from the rest 4 rows we choose 1 that we want to look exactly the same as the chosen row. We do it in ${4 choose 1}$ ways. We don't really care about remaining 3 rows - we just have to fill them in ${2 choose 1}^{15}$ ways. In total we have ${4 choose 1}$ ${2 choose 1}^{20}$ ways to do so.

C - fillings where 3 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Then from the rest 4 rows we choose 2 that we want to look exactly the same as the chosen row. We do it in ${4 choose 2}$ ways. Remaining 2 rows can be filled in ${2 choose 1}^{10}$ ways. In total we have ${4 choose 2}$ ${2 choose 1}^{15}$ ways to do so.

D - fillings where 4 consecutive rows are the same : we repeat same algorithm as we used in previous points. In total we have ${4 choose 3} {2 choose 1}^{10}$ ways to do so (since from 4 rows we choose 3 to be exactly the same as the first row).

E - fillings where 5 consecutive rows are the same : we fill 1 random row using X's and O's and we do it in ${2 choose 1}^5$ ways. Thus in total we have ${2 choose 1}^5$ ways.