OFFSET
1,2
COMMENTS
Let T be the set of permutations of nonnegative integers t such that t_i = i for all but a finite number of terms i.
The A306428 sequence enumerates the elements of T, hence we have a bijection f from T to the nonnegative integers.
The bijection f has the following properties: for any N > 0:
- if f(t) < N!, then t_i = i for any i >= N,
- this is consistent with the fact that there are N! permutations of (0..N-1),
- if f(t) + f(u) = N!-1, then t_i = u_{N-1-i} for i = 0..N-1,
- in other words, t and u, restricted to (0..N-1), are symmetrical permutations.
This sequence corresponds to the values f(t) of the permutations t in T such that t_i - t_j <> j - i for any distinct i and j.
Hence, for any n > 0 and N > 0:
- if a(n) < N!, then a(n) represents a permutation t of (0..N-1) such that the numbers t_i + i are distinct for i = 0..N-1; this corresponds to a configuration of N queens on an N X N board in which two queens do not attack each other if they are on the same northwest-southeast diagonal,
- this explains the expression of A099152 in the Formula section,
- also if a(n) = N! - 1 - a(m) for some m > 0, then a(n) represents a permutation t of (0..N-1) such that the numbers t_i + i are distinct for i = 0..N-1 and the numbers t_j - j are distinct for j = 0..N-1; this corresponds to a configuration of N nonattacking queens on an N X N board,
- this explains the expression of A000170 in the Formula section.
LINKS
FORMULA
EXAMPLE
For N = 6, there are 83 matrices in which the sums of the entries of each northeast-southwest diagonal are 0 or 1.
Also, for N = 6, there are 4 ways to place 6 nonattacking queens on a 6 X 6 board.
Finally, the solutions for N = 6 are 150, 296, 423 and 569 (positions within the ordered permutations, see A306428).
150 = (2,4,6,1,3,5);
O O O X O O
X O O O O O
O O O O X O
O X O O O O
O O O O O X
O O X O O O
296 = (3,6,2,5,1,4);
O O O O X O
O O X O O O
X O O O O O
O O O O O X
O O O X O O
O X O O O O
423 = (4,1,5,2,6,3);
O X O O O O
O O O X O O
O O O O O X
X O O O O O
O O X O O O
O O O O X O
569 = (5,3,1,6,4,2);
O O X O O O
O O O O O X
O X O O O O
O O O O X O
X O O O O O
O O O X O O
CROSSREFS
KEYWORD
nonn
AUTHOR
Raúl Mario Torres Silva, Jan 30 2019
STATUS
approved