Artificial intelligent assistant

Another form of Menage Problem : Place 8 more cherries(maroon) removing berries(black) 1 from each row and each column. No of ways? I tried to see it as a matrix where for a position (i,j) , i+j = 8, 9, 16 means you can't change that position. Any help? ![enter image description here](

Let $A^n_k$ be the number of derangements of $\\{1,2,\ldots,n\\}$ such that exactly $k$ of the elements map to their right neighbor (viewed cyclically). Then you're looking for $A^8_0$.

For $0\le k \le n$ we have $$A^n_k = \binom{n}{k} A^{n-k}_{0}$$ This is also true for $k=n$ if we declare that $A^0_0=1$, which doesn't seem unreasonable (after all, the empty map is a derangement of the empty set which doesn't map any element to its right neighbor). On the other hand, we have $A^1_0=A^2_0=0$.

The above recurrence doesn't tell us anything useful for $k=0$, but since $\sum_i A^n_i$ is the number of derangements of $n$ elements, which is known to be $\lfloor n!/e + 1/2\rfloor$, we can write a recurrence for the $A^n_0$s:

$$ A^n_0 = \left\lfloor \frac{n!}{e} + \frac12\right\rfloor - \sum_{j=0}^{n-1} \binom nj A^j_0 $$

which one can use directly to compute $A^8_0$ without too much trouble.

xcX3v84RxoQ-4GxG32940ukFUIEgYdPy 14a4e2b93dea80dbcd36178dc0ab03e3