No. of ways of selecting 3 squares when they do not lie in same row, column, or diagonal

751 Views Asked by At

Total number of ways of selecting 3 small squares on a normal chess board so that they don’t belong to the same row, column or diagonal line, is equal to:

No. of ways of selecting 3 squares when they do not lie in same row or same column $=(64×49×36)×\frac{1}{3!}=18816$

Total ways of selecting the squares when they lie in the same diagonal line $=2({8 \choose 3} + {7 \choose 3} +{6 \choose 3}+{5 \choose 3} + {4 \choose 3}+ {3 \choose 3})=392$

But this only counts the cases when all three are in the same diagonal. How to count the cases when two of the three lie in the same diagonal?

1

There are 1 best solutions below

0
On

I will count the number of ways of selecting three named positions $X,Y,Z$ such that no two are in the same row or column under various conditions. The counts differ slightly according to the parity of $n$ and so I will assume that $n$ is even.

$A$. No other conditions.

$B$. $X$ and $Y$ are on the same diagonal.

$C$. $X,Y$ and $Z$ are on the same diagonal.

$D$. $XY$ and $XZ$ are on perpendicular diagonals.

Inclusion/exclusion

$B-C-2D$ counts the number of ways that $X$ and $Y$ are on the same diagonal and that $Z$ is not on the same diagonal as either.

$C+3D$ counts the number of ways that each of $X,Y,Z$ is on a diagonal with at least one other.

Then the total number of possibilities with no two of $X,Y,Z$ on the same diagonal is $$A-3(B-C-2D)-(C+3D)=A-3B+2C+3D.$$ Each configuration occurs $3!$ times because of the naming of the positions and so the answer requested in the post is given by $$\frac{1}{6}(A-3B+2C+3D).$$ A

$$A=n^2(n-1)^2(n-2)^2.$$ For $n=8$ this is $112896$.

B

The diagonals with one orientation are of lengths $1,2,...,n-1,n,n-1, ...,2,1$. Therefore the number of ways of choosing two positions on one of these diagonals is$${2 \choose 2} + {3 \choose 2} +...+{n-1 \choose 2}+{n \choose 2} + {n-1 \choose 2}+... {3 \choose 2}+{2\choose 2}=\frac{1}{6}n(n-1)(2n-1).$$ This must be multiplied by the number of orientations, $2$, the number of ways of naming $X/Y$, also $2$, and the number of ways of choosing the position of $Z$, $(n-2)^2$. $$B=\frac{2}{3}n(n-1)(n-2)^2(2n-1) .$$ For $n=8$ this is $20160$.

C

The number of ways of choosing three positions on one of the sets of parallel diagonals is$${3 \choose 3} +...+{n-1 \choose 3}+{n \choose 3} + {n-1 \choose 3}+... {3 \choose 3}=\frac{1}{12}n(n-1)^2(n-2).$$ This must be multiplied by the number of orientations, $2$, and the number of ways of naming $X,Y,Z$, $6$. $$C=n(n-1)^2(n-2).$$ For $n=8$ this is $2352$.

D

The condition for no two of $X,Y,Z$ to be on the same row or column is simply that the legs of the L-shape must be unequal. There are then $8$ different orientations of the L-shape and $2$ ways of choosing $Y$ and $Z$.

I have not found a neat formula for the number of L-shapes with a particular orientation but it should be a reasonable challenge to find one. The shapes are however easy to count and for $n=8$ the number is $100$ (split into $49$ for one colour of squares and $51$ for the other). $$D=1600.$$

Grand total

$$\frac{1}{6}(112896-3\times 20160+2\times 2352+3\times 1600)=10320.$$

Addendum

The formula for $D$ appears to be $\frac{1}{6}n(n-2)(5n^2-16n+8)$.