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.

I would appreciate some pointers on this problem about finding the number of ways to choose 3 squares from an $n\times n$ grid such that no two are on the same diagonal.

This is http://oeis.org/A172123, where an explicit formula is given, but I am not sure how to derive that formula. Unfortunately the reference by Karl Fabel is in German and I cannot read German.

share|improve this question
    
The correct reference is to A172124; your link is for two bishops. –  Brian M. Scott Jun 5 '12 at 0:04

1 Answer 1

(I'm going to use the chess-based language that the OEIS uses but you've abandoned, because I find it a much more natural way of talking about this kind of problem.)

Say we want to place three bishops on an $n \times n$ board so that two of them are attacking each other. We start by picking a diagonal, and then place two bishops on that diagonal and a third one somewhere on the board not on the diagonal. Note that there are four diagonals of each length, except there are only two of length $n$. So the total number of attacking situations of this type is $$A_n=2 {n \choose 2}(n^2-n) + \sum_{k=0}^{n-1} 4{n - k \choose 2}(n^2-n+k)\, .$$ There are two special cases we need to patch up.

First, we haven't counted configurations where all three bishops are on the same diagonal. A similar argument says that there are $$B_n= 2 {n \choose 3} + \sum_{k=0}^{n-1} 4{n - k \choose 3}$$ such configurations.

Second, we've double-counted the "V-shaped" configuration where one bishop attacks the other two along different diagonals. This is the complicated case. We place the central bishop somewhere on the board, and pick a square on each of its diagonals to place the other two; in order to do this, we need to break it up by parity.

If $n$ is even, we can suppose by symmetry that the central bishop is in the upper-left quadrant of the board and then just multiply everything by 4. Say it has coordinates $(k,l)$ with $k,l \leq n/2$ (here the coordinates of the board squares range from $1$ to $n$). Then it lies on one diagonal which has $n-1-|k-l|$ other squares, and another which has $k+l-2$ other squares. Putting all this together, we can see that there are a total of $$C_n=4\sum_{k=1}^{n/2}\sum_{l=1}^{n/2} (k+l-2)(n-1-|k-l|)$$ configurations that look like this.

If $n$ is odd, a similar argument applies except that we also have to count configurations where the central bishop is on the middle rank or file of the board, which have a different set of symmetries. I won't go into the details at the moment, but hopefully by now you're convinced that this is possible (if tedious).

So then the total number of configurations where they aren't attacking each other is $${n^2 \choose 3} - A_n - B_n + C_n$$ by inclusion-exclusion. Hopefully I haven't screwed up and this should evaluate to the formula in the OEIS; certainly it has the right basic properties (it's parity-dependent, and if you squint at it long enough you should be able to convince yourself that the two parity cases are both sextic polynomials in $n$).

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.