Problem 778

Solution: This is a permutation problem with restrictions, and the corresponding $5 \times 5$ chessboard $R_{5}$ with forbidden cells is shown in Figure 4.5. The rook polynomial of the forbidden cell chessboard $C$ of $R_{5}$ is
$$\begin{array}{l} =t \cdot(\times \times) \cdot\left(\begin{array}{cc} & \times \\ \times & \times \\ \times & \end{array}\right)+\left(\begin{array}{ll} \times & \times \\ & \times \end{array}\right) \cdot\left(\begin{array}{ll} \times \\ \times & \times \\ \times & \times \end{array}\right) \\ =t(1+2 t)\left(1+4 t+3 t^{2}\right)+ \\ \left(1+3 t+t^{2}\right)\left(1+5 t+6 t^{2}+t^{3}\right) \\ =\left(t+6 t^{2}+11 t^{3}+6 t^{4}\right)+ \\ \left(1+8 t+22 t^{2}+24 t^{3}+9 t^{4}+t^{5}\right) \\ =1+9 t+28 t^{2}+35 t^{3}+15 t^{4}+t^{5} \text {, } \\ \end{array}$$

Therefore, the hit polynomial of $R_{5}$ is
$$\begin{aligned} E(t)= & 5!+9 \cdot 4!(t-1)+28 \cdot 3!(t-1)^{2}+ \\ & 35 \cdot 2!(t-1)^{3}+15(t-1)^{4}+(t-1)^{5}, \end{aligned}$$

Thus, the number of all permutations is
$$\begin{aligned} N & =E(0) \\ & =5!-9 \cdot 4!+28 \cdot 3!-35 \cdot 2!+15-1 \\ & =120-216+168-70+15-1 \\ & =16 . \end{aligned}$$