2
$\begingroup$

If I have a $4\times 4$ chess board, in how many ways can I place four distinct pawns on the board such that each column and row of the board contains no more than one pawn?

I have a feeling this is a basic combination problem with cases. I don't see it yet.

$\endgroup$
2
$\begingroup$

We have 4 choices for the column of the pawn in the first row, 3 choices for the column of the pawn in the second row, 2 choices for the column of the pawn in row 3, and 1 choice for the column of the pawn in row 4, for a total of $4!$ places for the positions of the pawns.

Since the pawns are distinct, there are $4!$ ways to place them in these chosen positions; so there are $4!\cdot4!=576$ possibilities.


Alternatively, there are 16 places for the first pawn, then 9 places for the second pawn, only 4 choices left for the third pawn, and just 1 choice for the fourth pawn, giving $\;16\cdot9\cdot4\cdot1=576$ possibilities.

$\endgroup$
  • $\begingroup$ It's an interesting interpretation that four distinct pawns means four distinguishable pawns. I took it to mean merely that the pawns must occupy four distinct spaces. $\endgroup$ – hardmath Sep 11 '17 at 5:58
  • $\begingroup$ @hardmath Four distinct pawns does mean the pawns are distinguishable. $\endgroup$ – N. F. Taussig Sep 11 '17 at 8:25
1
$\begingroup$

Note: I assumed the pawns, characteristically the weakest and most numerous of chess pieces, are interchangeable (not individually distinguishable), but as user84413 interprets "four distinct pawns", they are distinguishable. That leads to an extra factor of permutations (of the individual pieces), and hence to a different answer, $(4!)^2 = 24^2 = 576$.


Yes, it is a basic combinatorial problem, with $4!= 24$ solutions.

The key to seeing this is to consider the pawns must be one in each column and one in each row. Therefore if we enumerate the pawns by row, their column indexes are a permutation of the row indexes. Hence (for $4$ pawns on a $4\times 4$ board) we get $4!$ placements.

$\endgroup$
  • $\begingroup$ How do we know it's a 4x4 board? $\endgroup$ – Derek Sep 10 '17 at 19:50
  • $\begingroup$ @Derek: From the body of the Question: "If I have a $4\times 4$ chess board..." We could treat the case of extra rows and columns by counting subsets, but I think this is what the OP was asking. $\endgroup$ – hardmath Sep 10 '17 at 19:52
  • $\begingroup$ Wow. I totally skipped over that part. $\endgroup$ – Derek Sep 10 '17 at 19:54
  • 1
    $\begingroup$ @Derek: So did I at first. The more general problem is perhaps more interesting. $\endgroup$ – hardmath Sep 10 '17 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.