VOOZH about

URL: https://oeis.org/A306235

⇱ A306235 - OEIS

login
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
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.
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
KEYWORD
nonn
AUTHOR
STATUS
approved