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

1, 1, 0, 0, 0, 0, 0, 0, 2, 18, 12, 0, 12, 62, 76, 32, 44, 162, 600, 714, 386, 550, 2514, 5320, 4140, 3336, 8626, 24722, 33428, 27110, 34812, 96210, 200322, 220360, 213368, 376178, 894780, 1400578, 1473944, 1810538, 3653304, 7170370, 9467970

Offset

0,9

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,7}.

Links

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

Example

a(8) = 2: 24681357, 75318642.
a(9) = 18: 135792468, 186429753, 246813579, 297531864, 318642975, 357924681, 429753186, 468135792, 531864297, 579246813, 642975318, 681357924, 753186429, 792468135, 813579246, 864297531, 924681357, 975318642.
a(10) = 12: 135792468(10), 13(10)8642975, 186429753(10), 18(10)3579246, 579246813(10), 5792468(10)31, 642975318(10), 6429753(10)81, (10)318642975, (10)357924681, (10)813579246, (10)864297531.

Maple

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

Mathematica

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

Crossrefs

Cf. A174703, A174708, A302118, A307269.

Sequence in context: A302454 A303236 A174708 * A359197 A366950 A144158

Adjacent sequences: A328645 A328646 A328647 * A328649 A328650 A328651

Keyword

nonn

Author

Alois P. Heinz, Oct 23 2019

Status

approved