How many ways to place A’s and B’s.

combinatoricsrecursion

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?

Best Answer

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]$.

We have a final total then:

$$n!\cdot !n$$

Related Question