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,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

Table of n, a(n) for n=1..83.

Wikipedia, Factorial number system

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)}].

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

Cf. A000170, A099152, A306428

Sequence in context: A212243 A336463 A358457 * A353441 A004616 A322386

Adjacent sequences: A306232 A306233 A306234 * A306236 A306237 A306238

Keyword

nonn

Author

Raúl Mario Torres Silva, Jan 30 2019

Status

approved