cp's OEIS Frontend

Two semi-rooks do not attack each other if they are in the same column.

a(n) is also number of permutations p of 1,2,...,n satisfying |p(i+5k)-p(i)|<>6k AND |p(j+6k)-p(j)|<>5k for all i>=1, j>=1, k>=1, i+5k<=n, j+6k<=n

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.

One has T(n, k) = 0 exactly when (n, k) = (2, 2) or (3, 3).

One has T(n, n) = 1 except when n = 2 or 3 (that is, when A000170(n) = 0).

For a fixed k, the sequence T(-, k) is nondecreasing.

For a fixed n, the sequence T(n, -) is nonincreasing.

For a fixed nonzero p, the sequence (T(k + p, k))_k is nonincreasing. Indeed, given a configuration with k+1 armies on a k+p+1 chessboard, remove the row and column containing a given queen; this row and column can contain only queens of one army, so this yields a configuration of k armies on a k+p chessboard.

One has T(n, 1) = n^2 and T(n, 2) = A250000(n).

For a fixed k, one has, asymptotically in n, that 1/2.(n/k)^2 <= T(n, k) <= (n/k)^2, which can be proved as follows.

For the upper bound, let R(n, k) be defined as T(n, k) with rooks instead of queens. Then, T(n, k) <= R(n, k) ~ (n/k)^2. Indeed, for 1 <= i <= k, say the i^th army controls a_i rows and b_i columns. The sum of the a_i's, as well as the sum of the b_i's, is at most n. The size of the i^th army is at most a_i b_i. Therefore, one wants to maximize min(a_i b_i, i = 1..k). Ignoring rounding, the maximum is reached when all the a_i's and b_i's are equal.

For the lower bound, consider the n X n chessboard as a k X k grid with cells of size (n/k) X (n/k). Consider a configuration of k non-attacking queens on the k X k chessboard as in A000170(k). Place each of the k armies inside one cell occupied in that configuration. The precise placement is as follows: the army occupies the square whose vertices are the midpoints of the sides of the cell, hence has size 1/2.(n/k)^2. These armies are non-attacking.

A "cycle" means a rook-connected closed path of squares.

The proof of this result is given in the Links section.

a(n+1) is very close to A239231(n); more precisely, the difference is the sequence 1,0,1,1,1,1,1,1,1,1,1,2,1,1,1,2,1,1,1,2,1,2,3,2.

For n large enough, n/60 <= a(n) <= 0.241*n [Glock et al.].

The length of the n-th row is A000170(n) for n >= 4.