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