Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

On the chess board 8x8, we have 8 Rooks that , each Rook don't atack the other. How many situation if we give out: a) 1 main diagonal b) 2 main diagonals That's mean we can't put the Rook to the cells of diagonal

share|improve this question
    
I'm too young to understand the solution what you means . I need the solution with combination or conformable, a simple solution –  LevanDokite Sep 20 '12 at 7:19

2 Answers 2

up vote 2 down vote accepted

In general, if you want to count the number of ways of placing $n$ non-attacking rooks on an $n \times n$ chessboard (with some squares that the rooks must avoid), you can do it by calculating the permanent of a $(0,1)$-matrix: we place a $1$ wherever a rook is allowed to go, and a $0$ wherever the rook is not allowed to go.

Calculating the permanent of $(0,1)$-matrices is a #P-complete problem. So we cannot, in general, expect a simple "one size fits all" formula for these problems.

Here's GAP code that solves the counting problem:

Permanent(
[[0,1,1,1,1,1,1,1],
 [1,0,1,1,1,1,1,1],
 [1,1,0,1,1,1,1,1],
 [1,1,1,0,1,1,1,1],
 [1,1,1,1,0,1,1,1],
 [1,1,1,1,1,0,1,1],
 [1,1,1,1,1,1,0,1],
 [1,1,1,1,1,1,1,0]]
);

gives 14833 which is the number of derangements (as previously mentioned; see also Sloane's A000166). It is also the number of $2 \times 8$ Latin rectangles whose first row is $(0,1,\ldots,7)$. In this instance, there's fairly simple formulae (see the links).

For the second question:

Permanent(
[[0,1,1,1,1,1,1,0],
 [1,0,1,1,1,1,0,1],
 [1,1,0,1,1,0,1,1],
 [1,1,1,0,0,1,1,1],
 [1,1,1,0,0,1,1,1],
 [1,1,0,1,1,0,1,1],
 [1,0,1,1,1,1,0,1],
 [0,1,1,1,1,1,1,0]]
);

yields 4752 possibilities. This is also the number of $3 \times 8$ Latin rectangles whose first row is $(0,1,\ldots,7)$ and second rows is $(7,6,\ldots,0)$.

share|improve this answer
    
4752 is also the number of ways to place 3 non-attacking knights on a $6\times6$ board, according to oeis.org/A172134. Coincidence, presumably. The entry directly relevant to this question is oeis.org/A003471 –  Gerry Myerson Sep 20 '12 at 1:14

For (a), you want to count the permutations $\pi$ of $[1 \ldots 8]$ such that have no fixed point, i.e. $\pi(i) \ne i$ for all $i$. These are also known as derangements. See http://en.wikipedia.org/wiki/Derangement

EDIT: For (b), see http://oeis.org/A003471

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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