Let $B$ be the permutation of $A=\{1,2,3,\dots,n\}$ such that $|x_i-x_j|\ne|i-j|$ of every $i,j\in A$ where $x_k$ is $k-th$ element of $B$. How many different $B$ exist?

On first sight it doesn't look too hard. Firstly, I tried to solve it like the following problem:
In how many ways numbers $1,2,3,\dots,n$ can be arranged in a row such that $k$ cannot be on $k-th$ place for all $k\in\{1,2,3,\dots,n\}$? This second problem can be solved using inclusion/exclusion. Firstly, number of all permutation is $n!$. Now subtract the number of permutations where $1$ is on the first place, then where $2$ is on the second place etc. The number of these permutations is $\binom n 1 (n-1)!$. Then add permutations where we have $2$ incorrect numbers. This number will be $\binom n 2 (n-2)!$ etc. Final sum will be $$f(n)=n!-\binom n 1 (n-1)!+\binom n 2 (n-2)!-\dots=n! \sum_{k=0}^{n} \frac{(-1)^{k}}{k!}$$ I tried to solve the main problem using this method. My idea is to compute all permutations (it is $n!$), then for every incorrect pair of $i,j$ to subract these permutations, then to do it for $2$ pairs, then for $3$ pairs etc. I successfully did it for $1$ pair. I splited it in $n-1$ cases:

Case $1$: $|i-j|=1$
Numbers of ways to choose $(i,j)$: $n-1$ (it does not matter if $i>j$ or $j>i$ ebcause there is absolute value)
Number of ways to choose $(x_i,x_j)$: $2(n-1)$
Case $2$: $|i-j|=2$
Numbers of ways to choose $(i,j)$: $n-2$
Number of ways to choose $(x_i,x_j)$: $2(n-2)$
Case $3$: $|i-j|=3$
Numbers of ways to choose $(i,j)$: $n-3$
Number of ways to choose $(x_i,x_j)$: $2(n-3)$
Case $n-1$: $|i-j|=n-1$
Numbers of ways to choose $(i,j)$: $1$
Number of ways to choose $(x_i,x_j)$: $2$
From this I computed number of permutations where at least one pair of numbers is incorrect (including overcounted permutations):

$\displaystyle S=\left((n-1)\cdot2(n-1)\right)\cdot\left((n-2)\cdot2(n-2)\right)\left((n-3)\cdot2(n-3)\right)\cdot{\dots}\cdot\left(1\cdot2)\right)\\ \displaystyle S=\sum_{k=1}^{n-1}2k^2\\ \displaystyle S=\frac{n(n-1)(2n-1)}{3}$

Then I tried to do the same for $2$ pairs and then to $3$ pairs to find some regularity. It is very hard to find formula for $2$ pairs. Formula I've found is really complicated and I do not see any way to simplify it. For $3$ pairs I couldn't find any formula. I believe this problem isn't hard as it seems, so I think there must be an easy way to find solution. Is my way completely wrong or I'm close to solution, but I'm still missing something?

  • $\begingroup$ $f(1)=1,f(2)=0,f(3)=0,f(4)=2$, namely $(3,1,4,2)$ and $(2,4,1,3)$ $\endgroup$ – Empy2 Apr 15 '15 at 16:39
  • $\begingroup$ @Michael I computed $f(x)$ for all $x\le30$, but it cannot help me to solve it. $\endgroup$ – user164524 Apr 15 '15 at 16:41
  • $\begingroup$ Did you put it into the Online Encyclopedia of Integer Sequences? (OEIS) $\endgroup$ – Empy2 Apr 15 '15 at 16:41
  • $\begingroup$ @Michael Of course, but I didn't find anything. $\endgroup$ – user164524 Apr 15 '15 at 16:42
  • $\begingroup$ Is there any pattern when $n$ is prime? The ten solutions for $n=5$ all come from $i\to2i+m\pmod5$ and $i\to3i+m\pmod5$. There will be at least 28 solutions for $n=7$ with similar formulas. $\endgroup$ – Empy2 Apr 15 '15 at 17:34

It's easy to see that $f(n)$ is the number of configurations of $n$ mutually non-attacking queens on an $n\times n$ chessboard. Given a permutation $\pi$ satisfying your conditions, place queens at the squares $(i,\pi(i))$. They are non-attacking horizontally and vertically since $\pi$ is a permutation; the condition $|\pi(i)-\pi(j)|\ne |i-j|$ says precisely that the queens don't attack each other diagonally.

The $n$-queens problem has been very well studied - see Wikipedia for an overview; many references appear in the OEIS entry. It's a safe bet that no general formula is known; in fact, the correct values appear to have only been computed up to $n=26$.


Your Answer

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