0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Just to check my logic, is there 9 ways in the 3x3 case? $\endgroup$ Oct 2, 2018 at 18:03
  • $\begingroup$ I believe so. I'm not 100% sure though; I could've made a mistake. $\endgroup$
    – Kurns
    Oct 2, 2018 at 18:06
  • $\begingroup$ @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. $\endgroup$
    – JMoravitz
    Oct 2, 2018 at 18:08
  • $\begingroup$ Oops, my mistake. I overlooked some cases. $\endgroup$
    – Kurns
    Oct 2, 2018 at 18:08

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How does one calculate !n? @JMoravitz $\endgroup$
    – Kurns
    Oct 2, 2018 at 18:05
  • $\begingroup$ @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$. $\endgroup$
    – JMoravitz
    Oct 2, 2018 at 18:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .