A279214 Number of permutations sigma such that |sigma(i+1)-sigma(i)| >= 3 for 1 <= i <= n - 1 and |sigma(i+2)-sigma(i)| >= 3 for 1 <= i <= n - 2.

1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 40, 792, 15374, 281434, 5089060, 93082532, 1743601076, 33694028152

Offset

0,10

Comments

2 | a(n) for n > 1.

Links

Table of n, a(n) for n=0..17.

Example

a(9) = 2: 369258147, 741852963.

Prog

(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 A279214(n)
  (0..n).map{|i| solve(3, i).size}
end
p A279214(12)

Crossrefs

Cf. A002464 (|sigma(i+1)-sigma(i)| >= 2), A127697 (|sigma(i+1)-sigma(i)| >= 3).

Sequence in context: A127186 A139747 A230133 * A264716 A264713 A012637

Adjacent sequences: A279211 A279212 A279213 * A279215 A279216 A279217

Keyword

nonn,more

Author

Seiichi Manyama, Dec 17 2016

Extensions

a(0)-a(2), a(15)-a(17) from Alois P. Heinz, Dec 01 2018

Status

approved