A306235 Indices in A306428 of permutations t with a finite number of nonfixed points and such that t_i - t_j <> j - i for any distinct i and j (see Comments for precise definition).

0, 2, 4, 7, 8, 14, 15, 24, 28, 32, 33, 39, 48, 56, 60, 63, 64, 72, 80, 87, 96, 104, 111, 121, 122, 127, 134, 135, 138, 140, 142, 147, 150, 156, 159, 160, 168, 176, 184, 185, 192, 202, 207, 242, 246, 247, 258, 277, 296, 312, 314, 316, 318, 322, 326, 327, 333, 366, 367, 385, 414, 415, 416, 420, 423, 426, 428, 432, 438, 443, 447, 504, 505, 506, 536, 537, 540, 567, 569, 602, 604, 628, 660

Offset: 1

Author

Raúl Mario Torres Silva, Jan 30 2019

Keywords

• nonn

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.

Examples

			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
		

Links

• Wikipedia, Factorial number system

Crossrefs

Cf. A000170, A099152, A306428

Formula

A099152(k) = Sum_{i > 0} [k! - 1 - a(i) >= 0] (with [] = Iverson bracket).

A000170(k) = Sum_{i > 0} [k! - 1 - a(i) belongs to {a(n)}].