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

1, 0, 0, 2, 10, 12, 8, 12, 30, 72, 106, 128, 186, 316, 546, 836, 1186, 1756, 2720, 4224, 6366, 9374, 13932, 20958, 31470, 46820, 69194, 102458, 152152, 225548, 333142, 490964, 723690, 1067166, 1571878, 2311500, 3395804, 4987584, 7324024, 10747556

Offset: 1

Author

W. Edwin Clark, Mar 27 2010

Keywords

• nonn

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

Examples

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100
• 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 2010.

Crossrefs

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

Programs

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,3,n): seq(a(n), n=1..14); # 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, 3, n]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 14}] (* Jean-François Alcover, Jun 01 2015, after Alois P. Heinz *)

Formula

Empirical: a(n) = 2*a(n-1) -a(n-2) +a(n-3) -a(n-4) +4*a(n-5) -6*a(n-6) +a(n-7) -2*a(n-8) +a(n-9) -5*a(n-10) +5*a(n-11) +a(n-12) +3*a(n-13) +a(n-14) +3*a(n-15) -a(n-16) -a(n-18) -a(n-19) -a(n-20) for n>20. - Andrew Howroyd, Apr 08 2016

Empirical G.f.: (3-2*x) + 2*(1-x) * (-1 +2*x -x^2 +x^3 +8*x^5 -5*x^6 -2*x^7 -5*x^8 -6*x^10 +3*x^11 +x^12 +3*x^13 +4*x^14 +7*x^15 +5*x^16 +3*x^17 +x^18) / ((1 -x +x^2)^2 * (-1 +x^2 +x^3)^2 * (1 -x^3 -x^4 -3*x^5 -x^6 +x^8 +x^9 +x^10)). - Andrew Howroyd, Apr 08 2016

Extensions

More terms from Alois P. Heinz, Mar 30 2010