Aesthetically Inclined Rooks

Computer Science Level 5

$50$ rooks want to arrange themselves in a non-attacking position on a $50 \times 50$ chessboard such that the arrangement is symmetric about the diagonal from the lower left corner to the upper right corner. They can do this in $N$ ways. What are the last five digits of $N$ ?

The answer is 59776.

2 solutions

Abdelhamid Saadi
Oct 10, 2015

Let $rooks(n)$ be the number of possibilities for $n$ rooks on $n \times n$ chessboard.

We can observe that the following relation realation holds:

$rooks(0) = 1$

$rooks(1) = 1$

$rooks(n + 2) = rooks(n + 1) + (n + 1)* rooks(n) \quad n \geq 0$

This gives in python:

def rooks(n):
    "Aesthetically Inclined Rooks"
    rooks_=[1,1]
    for k in range(2, n + 1):
        rooks_.append(rooks_[k - 1]+(k - 1)*rooks_[k - 2])
    return rooks_[n]

print(rooks(50)%100000)

Agnishom Chattopadhyay
Aug 23, 2015

This problem requires more Combinatorics than Computer Science.

First, we notice that since there are as many non-attacking rooks as their are files, there must be an rook in each file. Let's call the rank of the rook in the i'th file $rook(i)$ .

The symmetry constraint means that for every rook which is some steps above the diagonal, there exists a rook which is exactly the same steps away horizontally from the the same point on the diagonal.

$rook( i + (rook(i) - i) ) = i \implies rook(rook(i)) = i \quad \forall i$

Now, let us have a look at the array of the ranks of the rooks. Two things can happen to each of the rooks:

They remain on the diagonal
Two of them pair up and switch ranks.

For example, in the configuration [1, 2, 3, 4, 8, 7, 6, 5] , the first four rooks are in the diagonal but the fifth and the 8th rook have paired up and so has the sixth and the seventh rook.

We can choose $2r$ rooks from $2n$ rooks in ${2n \choose 2r }$ ways and then pair them up in $\frac{(2r)!}{2^r r!}$ ways.

Thus, the total number of symmetric arrangements asked is the summation of the possible arrangements when none of them switch ranks, 2 of them switch ranks, 4 of them switch ranks, 6 ... and so on.

$f(2n) = \sum_{i=0}^{n} {{2n \choose 2i} {\frac{(2i)!}{2^i i!}}}$

Moderator note:

Since you've started on a combinatorial approach, how can we use combinatorial ideas to find the summation?

Calvin Lin Staff - 5 years, 9 months ago

I initially thought that mindlessly counting the solutions to a minizinc model will solve this problem. It didn't obviously work because there was no way I could run through all the solutions. But when I ran the model, with smaller numbers, I realised that there is a lot of structure in the solutions which can be analytically taken care of.

I am not aware of a method that allows me to calculate such a large number by hand. Can you teach me how?

Agnishom Chattopadhyay - 5 years, 9 months ago

Hint: A recurrence relation exists, and so that would greatly simplify the calculations. It is "linear" in $F_n$ , but the coefficients involve $n$ .

Calvin Lin Staff - 5 years, 9 months ago

@Calvin Lin – Let $F_n$ be the number of ways of arranging $n$ non-attacking rooks symmetrically on an $n\times n$ chessboard. The recurrence relation is $F_n \; = \; F_{n-1} + (n-1)F_{n-2}$ with $F_0 = F_1 = 1$ .

There are $F_{n-1}$ ways of arranging the $n$ rooks symmetrically if the rook in the first column is on the diagonal of symmetry.

There are $n-1$ places to put the rook in the first column if it is not on the diagonal of symmetry. If the first column rook goes in row $j$ , then the $j$ th column rook must go in row $1$ , and there are $F_{n-2}$ ways of arranging the other $n-2$ rooks symmetrically.

Performing calculations modulo $100000$ in Excel (or elsewhere) makes it a simple matter to evaluate the last $5$ digits of $F_{50}$ .

An alternative way of thinking about this problem is to see that $F_n$ is $1$ plus the number of permutations in $S_n$ whose cycle type contains only transpositions ( $2$ -cycles). That leads to the formula ( $j$ being the number of transpositions in the cycle type): $F_n \; =\; \sum_{j=0}^{\lfloor \frac12n \rfloor} {n \choose 2j} \dfrac{(2j)!}{2^j j!}$

Mark Hennings - 5 years, 5 months ago

@Mark Hennings – That's great! Different approaches of thinking about the problem can yield different answers.

It could be interesting to show how the closed form of $F_n$ could be used to demonstrate the recurrence relation (haven't tried that yet).

Calvin Lin Staff - 5 years, 5 months ago

Aesthetically Inclined Rooks

The answer is 59776.

2 solutions

Moderator note:

0 pending reports