

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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..N1),
 if f(t) + f(u) = N!1, then t_i = u_{N1i} for i = 0..N1,
 in other words, t and u, restricted to (0..N1), 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..N1) such that the numbers t_i + i are distinct for i = 0..N1; this corresponds to a configuration of N queens on a N X N board in which two queens do not attack each other if they are in the same NorthWestSouthEast 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..N1) such that the numbers t_i + i are distinct for i = 0..N1 and the numbers t_j  j are distinct for j = 0..N1; this corresponds to a configuration of N nonattacking queens on a 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 northeastsouthwest 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: A287208 A212243 A336463 * A004616 A322386 A309583
Adjacent sequences: A306232 A306233 A306234 * A306236 A306237 A306238


KEYWORD

nonn


AUTHOR

Raúl Mario Torres Silva, Jan 30 2019


STATUS

approved



