A307269 Number of permutations p of [n] such that |p(i) - p(i-1)| is in {2,5} for all i from 2 to n.

1, 1, 0, 0, 0, 0, 2, 14, 12, 8, 28, 58, 44, 120, 254, 226, 344, 932, 1262, 1380, 2958, 5006, 5632, 9496, 18204, 23756, 32758, 59992, 90494, 118740, 196318, 320814, 437270, 653770, 1077580, 1570054, 2233920, 3551168, 5426452, 7714408, 11709864

Offset

0,7

Comments

For n>1, a(n)/2 is the number of Hamiltonian paths on the graph with vertex set {1,...,n} where i is adjacent to j iff |i-j| is in {2,5}.

Links

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

Example

a(6) = 2: 246135, 531642.
a(7) = 14: 1357246, 1642753, 2461357, 2753164, 3164275, 3572461, 4275316, 4613572, 5316427, 5724613, 6135724, 6427531, 7246135, 7531642.
a(8) = 12: 13572468, 13864275, 16427538, 16835724, 42753168, 42753861, 57246138, 57246831, 83164275, 83572461, 86135724, 86427531.
a(9) = 8: 168357249, 168357942, 249753168, 249753861, 861357249, 861357942, 942753168, 942753861.

Maple

b:= proc(s, l) option remember; `if`(s={}, 1, add(
      `if`(abs(l-j) in {2, 5}, b(s minus {j}, j), 0), j=s))
    end:
a:= proc(n) option remember; if n=0 then 1 else
      add(b({$1..n} minus {j}, j), j=1..n) fi
    end:
seq(a(n), n=0..20);

Mathematica

b[s_, l_] := b[s, l] = If[s == {}, 1, Sum[If[MemberQ[{2, 5}, Abs[l - j]], b[s ~Complement~ {j}, j], 0], {j, s}]];
a[n_] := a[n] = If[n==0, 1, Sum[b[Range[n] ~Complement~ {j}, j], {j, n}]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 27}] (* Jean-François Alcover, Oct 23 2021, after Alois P. Heinz *)

Crossrefs

Cf. A174703, A302118, A328648.

Sequence in context: A271382 A158787 A174706 * A072163 A084674 A009774

Adjacent sequences: A307266 A307267 A307268 * A307270 A307271 A307272

Keyword

nonn

Author

Alois P. Heinz, Apr 01 2019

Status

approved