Raúl Mario Torres Silva - cp's OEIS frontend

User: Raúl Mario Torres Silva

Raúl Mario Torres Silva has authored 2 sequences.

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

Raúl Mario Torres Silva, Jan 30 2019

nonn

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.

			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

Wikipedia, Factorial number system

Cf. A000170, A099152, A306428

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

A306428 Decimal representation of permutations of lengths 1, 2, 3, ...

Original entry on oeis.org

1, 21, 312, 132, 231, 321, 4123, 1423, 2413, 4213, 1243, 2143, 3412, 4312, 1342, 3142, 4132, 1432, 2341, 3241, 4231, 2431, 3421, 4321, 51234, 15234, 25134, 52134, 12534, 21534, 35124, 53124, 13524, 31524, 51324, 15324, 23514, 32514, 52314, 25314, 35214, 53214, 12354, 21354, 31254

Offset: 0

Raúl Mario Torres Silva, Feb 14 2019

nonn

One way to generate the permutations is by using the factorial base (not to be confused with the Lehmer code).
Here is a detailed example showing how to compute a(2982).
We have i = 2982 = (4, 0, 4, 1, 0, 0, 0) in the factorial base.
So the initial vector "0" is (1, 2, 3, 4, 5, 6, 7), using seven active digits.
The factorial base vector is reversed, giving (0, 0, 0, 1, 4, 0, 4).
The instructions are to read from the factorial base vector, producing rotations to the right by as many steps as the column says, in the following order:
Start on the right; on the vector "0", a rotation of 4 units is made
(0, 0, 0, 1, 4, 0, [4])
(1, 2, 3, 4, 5, 6, 7)
The result is:
(4, 5, 6, 7, 1, 2, 3)
The 3 is retained, one column is advanced.
Next a rotation of 0 units is made (the null rotation)
(0, 0, 0, 1, 4, [0], 4)
(4, 5, 6, 7, 1, 2, 3)
The result is:
(4, 5, 6, 7, 1, 2, 3)
The 2 is retained, one column is advanced.
Now a rotation of 4 units is made
(0, 0, 0, 1, [4], 0, 4)
(4, 5, 6, 7, 1, 2, 3)
The result is:
(5, 6, 7, 1, 4, 2, 3)
The 4 is retained, one column is advanced.
Now a rotation of 1 units is made
(0, 0, 0, [1], 4, 0, 4)
(5, 6, 7, 1, 4, 2, 3)
The result is:
(1, 5, 6, 7, 4, 2, 3)
The 7 is retained, one column is advanced.
Now 3 null rotations are made.
All remaining values are retained: 6, 5, and 1
Thus 2982 represents the permutation: (1, 5, 6, 7, 4, 2, 3)
Or a(2982) = 1567423.

			The sequence may be regarded as a triangle, where each row consists of permutations of N terms; i.e., we have
1/,2,1/,3,1,2;1,3,2;2,3,1;3,2,1/4,1,2,3;1,4,2,3;2,4,1,3;...
Append to each an infinite number of fixed terms and we get a list of rearrangements of the natural numbers, but with only a finite number of terms permuted:
1/2,3,4,5,6,7,8,9,...
2,1/3,4,5,6,7,8,9,...
3,1,2/4,5,6,7,8,9,...
1,3,2/4,5,6,7,8,9,...
2,3,1/4,5,6,7,8,9,...
3,2,1/4,5,6,7,8,9,...
4,1,2,3/5,6,7,8,9,...
1,4,2,3/5,6,7,8,9,...
2,4,1,3/5,6,7,8,9,...
Alternatively, if we take only the first n terms of each such infinite row, then the first n! rows give all permutations of the elements 0,1,2,...,n-1.

cp's OEIS Frontend

User: Raúl Mario Torres Silva

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs