login
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.
3
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}.
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
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Oct 23 2019
STATUS
approved