A318790 One-half of the number of permutations sigma of {1,2,...,n^2 + 1} such that |sigma(i+j)-sigma(i)| >= n for 1 <= i <= n^2 + 1 - j, 1 <= j <= n - 1.

1, 7, 20, 37, 64, 109

Offset: 1

Author

Seiichi Manyama, Dec 15 2018

Keywords

• nonn
• hard
• more

Examples

			In case n=2:
permutation
--------------------------------
[1, 3, 5, 2, 4] and its reverse.
[1, 4, 2, 5, 3] and its reverse.
[2, 4, 1, 3, 5] and its reverse.
[2, 4, 1, 5, 3] and its reverse.
[2, 5, 3, 1, 4] and its reverse.
[3, 1, 4, 2, 5] and its reverse.
[3, 1, 5, 2, 4] and its reverse.
So a(2) = 14/2 = 7.
		

Crossrefs

Cf. A002464, A279214, A322281, A322308.

Programs

Ruby

def check(d, a, i)
  return true if i == 0
  j = 1
  d_max = [i, d - 1].min
  while (a[i] - a[i - j]).abs >= d && j < d_max
    j += 1
  end
  (a[i] - a[i - j]).abs >= d
end
def solve(d, len, a = [])
  b = []
  if a.size == len
    b << a
  else
    (1..len).each{|m|
      s = a.size
      if s == 0 || (s > 0 && !a.include?(m))
        if check(d, a + [m], s)
          b += solve(d, len, a + [m])
        end
      end
    }
  end
  b
end
def A318790(n)
  (1..n).map{|i| solve(i, i * i + 1).size / 2}
end
p A318790(4)