25 small squares of a 5×5 chess board are coloured with 5 different
colours available, such that each row contains all 5 available colours
and no two adjacent squares have same colour. Then the no. of
different arrangements possible are?
My attempt:
Let the colours be R,B,G,W,V
To fill the first row I have 5×4×3×2×1
Now for the second row I am sort of messing up I am able to determine 4 cases only but I am getting it at all messed up again and again.
Help me with the editing as well please.
Best Answer
Consider the following chess table: $$\begin{array} {|r|r|}\hline & & & & \\ \hline & & & & \\ \hline & & & & \\ \hline & & & & \\ \hline & & & & \\ \hline \end{array}$$
Let's fill the first row with any colors:
$$\begin{array} {|r|r|}\hline a& b& c& d& e \\ \hline & & & & \\ \hline & & & & \\ \hline & & & & \\ \hline & & & & \\ \hline \end{array}$$
The ways to choose $(a,b,c,d,e)$ is $5!$
For the second row, apply inclusion-exclusion.
$$\begin{array} {|r|r|}\hline a& b& c& d&e \\ \hline a'&b' &c' &d' &e' \\ \hline & & & & \\ \hline & & & & \\ \hline & & & & \\ \hline \end{array}$$
Total possible concievable arrangements of $(a',b',c',d',e')$ are again $5!$ but we must remove some unfavorable cases.
This is known as a derangement. So, we have counted in our $5!$ some cases where one of $l = l'$ where $l$ is one of ${a,b,c,d,e}$. The number of such cases is $\binom 514!$. But, in this, we have removed some cases where $l=l'$ for two $l$ twice (once for one $l$, another time for the other). The number of such cases is $\binom 523!$. Continuing like this, we have the total good arrangements as $5!\left(\displaystyle\sum_{k = 0}^5\left(-1\right)^k\frac 1{k!}\right)$. Once we have set the arrangement for this row, we may repeat the process for the next row, and so on. $$\begin{array} {|r|r|}\hline a& b& c& d&e \\ \hline a'&b' &c' &d' &e' \\ \hline a''&b'' &c'' &d'' &e'' \\ \hline & & & & \\ \hline & & & & \\ \hline \end{array}$$
So, by my calculation, the total favorable arrangements is $$5!^5\left(\displaystyle\sum_{k = 0}^5\left(-1\right)^k\frac 1{k!}\right)^4$$ $$= 120*44^4\boxed{=449771520}$$