cp's OEIS Frontend

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.

%I A318790 #25 Dec 14 2021 12:48:53
%S A318790 1,7,20,37,64,109
%N 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.
%e A318790 In case n=2:
%e A318790 permutation
%e A318790 --------------------------------
%e A318790 [1, 3, 5, 2, 4] and its reverse.
%e A318790 [1, 4, 2, 5, 3] and its reverse.
%e A318790 [2, 4, 1, 3, 5] and its reverse.
%e A318790 [2, 4, 1, 5, 3] and its reverse.
%e A318790 [2, 5, 3, 1, 4] and its reverse.
%e A318790 [3, 1, 4, 2, 5] and its reverse.
%e A318790 [3, 1, 5, 2, 4] and its reverse.
%e A318790 So a(2) = 14/2 = 7.
%o A318790 (Ruby)
%o A318790 def check(d, a, i)
%o A318790   return true if i == 0
%o A318790   j = 1
%o A318790   d_max = [i, d - 1].min
%o A318790   while (a[i] - a[i - j]).abs >= d && j < d_max
%o A318790     j += 1
%o A318790   end
%o A318790   (a[i] - a[i - j]).abs >= d
%o A318790 end
%o A318790 def solve(d, len, a = [])
%o A318790   b = []
%o A318790   if a.size == len
%o A318790     b << a
%o A318790   else
%o A318790     (1..len).each{|m|
%o A318790       s = a.size
%o A318790       if s == 0 || (s > 0 && !a.include?(m))
%o A318790         if check(d, a + [m], s)
%o A318790           b += solve(d, len, a + [m])
%o A318790         end
%o A318790       end
%o A318790     }
%o A318790   end
%o A318790   b
%o A318790 end
%o A318790 def A318790(n)
%o A318790   (1..n).map{|i| solve(i, i * i + 1).size / 2}
%o A318790 end
%o A318790 p A318790(4)
%Y A318790 Cf. A002464, A279214, A322281, A322308.
%K A318790 nonn,hard,more
%O A318790 1,2
%A A318790 _Seiichi Manyama_, Dec 15 2018