0
$\begingroup$

Four letters, $2$ '$a$'s and $2$ '$b$'s are to be filled in a $4×4$ matrix such that no $2$ same letters are in the same row or the same column. One cell can hold a maximum of one letter. In how many ways can this be done? Answer provided is $3960$.

I tried case analysis. Firstly, I assigned the 'a's in $(16 \cdot 9)/2! = 72$ ways. Then, I tried counting the number of ways as per the different possibilities for 'b's position. First I considered that one b is in the same column as a, second that one b is in the same row as a, third that it is in the same row as one a and the same column as another a. And fourth it isn't in any row or column as that of the previously assigned 'a's. But, in this method there is clearly over counting. And I don't know how to bypass that.

$\endgroup$
2
  • $\begingroup$ I tried case analysis. Firstly, I assigned the 'a's in (16*9)/2! =72 ways. Then, I tried counting the number of ways as per the different possibilities for 'b's position. First I considered that one b is in the same column as a, second that one b is in the same row as a, third that it is in the same row as one a and the same column as another a. And fourth it isn't in any row or column as that of the previously assigned 'a's. But, in this method there is clearly over counting. And I don't know how to bypass that. $\endgroup$ Commented May 13, 2018 at 7:40
  • $\begingroup$ Welcome to MathSE. When you pose a question here, it is expected that you include your attempt and explain where you are stuck in the question itself. Therefore, I copied that information from your comment into the question. What do you mean by four letters, $2$ $a$s and $2$ $b$s? Do you mean that there are four letters other than $a$ and $b$? $\endgroup$ Commented May 13, 2018 at 9:55

2 Answers 2

1
$\begingroup$

There are $\binom{16}2$ ways to place 2 a's without restriction

Subtract the ways in which they both appear in the same row or column

For each of the 4 rows there are $\binom 42$ ways to place both a's in the same row

For each of the 4 columns there are $\binom 42$ ways to place both a's in the same column So number of ways to place a's is $$N_a=\binom{16}2 - 8\binom 42=72$$ Now there are $\binom {14}2$ ways to place the b's without restriction.

Now there are 2 rows that have an a in them and 2 that don't , so the number of ways that both b's can appear in the same row is $2\binom 32 + 2\binom 42$ There are the same number of ways for both b's to appear in the same column $$N_b = \binom {14}2-4 \left [\binom 32 + \binom 42 \right]=91-36=55$$ Total number of ways is just $N_a N_b$

$\endgroup$
0
$\begingroup$

Hint: There are 16 ways to put down the first $a$.

There are 9 ways to put down the second $a$.

Hence there are $\frac{16*9}{2}=72$ ways to put down the two $a$s.

The key part is to count the number of ways to place the $b$s. Split into three cases.

The first case: $b$ is placed in a spot where there is an $a$ in the column and there is an $a$ in the row.

$\endgroup$
1
  • $\begingroup$ I tried this approach but can't avoid over counting. Could you please elaborate? $\endgroup$ Commented May 13, 2018 at 7:41

You must log in to answer this question.

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