A174704 The number of permutations p of {1,...,n} such that |p(i)-p(i+1)| is in {2,3,4} for all i from 1 to n-1.

1, 1, 0, 0, 2, 14, 60, 152, 256, 464, 1124, 3114, 8324, 20166, 44958, 97666, 217792, 501356, 1163776, 2668126, 6006712, 13363390, 29660118, 66006498, 147147006, 327471130, 725850010, 1602363242, 3527859498, 7756716420, 17040151108, 37393219368, 81932669910, 179223992670, 391448289188, 853909743368

Offset

0,5

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

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

W. Edwin Clark, permutations p in S_n such that m <= |p(i)-p(i+1)| <= M for i from 1 to n-1, SeqFan Discussion, Mar 27 2010.

Example

For n = 5 the a(5) = 14 permutations are (1,3,5,2,4), (1,4,2,5,3), (2,4,1,3,5), (2,4,1,5,3), (2,5,3,1,4), (3,1,4,2,5), (3,1,5,2,4), (3,5,1,4,2), (3,5,2,4,1), (4,1,3,5,2), (4,2,5,1,3), (4,2,5,3,1), (5,2,4,1,3), (5,3,1,4,2).

Maple

f:= proc(m, M, n) option remember; local i, l, p, cnt; l:= array([i$i=1..n]); cnt:=0; p:= proc(t) local d, j, h; if t=n then d:= `if`(t=1, m, abs(l[t]-l[t-1])); if m<=d and d<=M then cnt:= cnt+1 fi else for j from t to n do l[t], l[j]:= l[j], l[t]; d:= `if`(t=1, m, abs(l[t]-l[t-1])); if m<=d and d<=M then p(t+1) fi od; h:= l[t]; for j from t to n-1 do l[j]:= l[j+1] od; l[n]:= h fi end; p(1); cnt end: a:= n-> f(2, 4, n): seq(a(n), n=1..12); # Alois P. Heinz, Mar 27 2010

Mathematica

f[m_, M_, n_] := f[m, M, n] = Module[{i, l, p, cnt}, Do[l[i] = i, {i, 1, n}]; cnt = 0; p[t_] := Module[{d, j, h}, If[t == n, d = If[t == 1, m, Abs[l[t] - l[t-1]]]; If [m <= d && d <= M, cnt = cnt+1], For[j = t, j <= n, j++, {l[t], l[j]} = {l[j], l[t]}; d = If[t == 1, m, Abs[l[t] - l[t-1]]]; If [m <= d && d <= M, p[t+1]]]; h = l[t]; For[j = t, j <= n-1, j++, l[j] = l[j+1]]; l[n] = h]]; p[1]; cnt]; a[n_] := f[2, 4, n]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 12}] (* Jean-François Alcover, Jun 01 2015, after Alois P. Heinz *)

Crossrefs

Cf. A003274, A174700, A174701, A174702, A174703, A174705, A174706, A174707, A174708, A185030, A216837.

Sequence in context: A232601 A285153 A232370 * A058738 A095376 A153332

Adjacent sequences: A174701 A174702 A174703 * A174705 A174706 A174707

Keyword

nonn,changed

Author

W. Edwin Clark, Mar 27 2010

Extensions

Edited by Alois P. Heinz, Nov 27 2010

a(22) from Alois P. Heinz, Oct 12 2013

a(23) from Alois P. Heinz, Jan 14 2016

a(24)-a(35) from Andrew Howroyd, Apr 05 2016

Status

approved