# How many ways to place A's and B's.

The problem: You are given a n*n grid. In how many ways can you place A's and B's in the grid so that there is exactly one 'A' and one 'B' on each row and each column? There may be 0 or 1 letters in each square.

An example:

n = 2

way 1:

A B
B A

way 2:
B A
A B

ans: 2


I have tried to figure this out but it is very slow to calculate all cases by hand. Is there a smart mathematical formula for the general case?

• Just to check my logic, is there 9 ways in the 3x3 case? Oct 2, 2018 at 18:03
• I believe so. I'm not 100% sure though; I could've made a mistake. Oct 2, 2018 at 18:06
• @Kurns my formula would give $3!\cdot !3 = 6\cdot 2 = 12$ ways for the $3\times 3$ case. This should be easy to check that the total should be even since given any way of arranging the $A$'s, there are exactly two ways that you can arrange the $B$'s without overlap. Oct 2, 2018 at 18:08
• Oops, my mistake. I overlooked some cases. Oct 2, 2018 at 18:08

First place the $$A$$'s in $$n!$$ ways. This can be seen through the lens of permutation matrices.
Next, given some placement of the $$A$$'s, we wish to place the $$B$$'s in such a way as to never reuse the same positions. Through a relabeling of indices, this is effectively asking for a derangement and can be done in $$!n$$ ways where $$!n$$ is the subfactorial counting the number of derangements of $$[n]$$.
$$n!\cdot !n$$
• @Kurns the wikilink provided gives multiple ways of calculating it. For small values, the recurrence $!n = (n-1)(!(n-1)+!(n-2))$ is easiest, noting that $!0=1$ and $!1=0$. Oct 2, 2018 at 18:07