|
%I #39 Jan 02 2023 12:30:47
%S 1,1,0,0,2,14,60,152,256,464,1124,3114,8324,20166,44958,97666,217792,
%T 501356,1163776,2668126,6006712,13363390,29660118,66006498,147147006,
%U 327471130,725850010,1602363242,3527859498,7756716420,17040151108,37393219368,81932669910,179223992670,391448289188,853909743368
%N 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.
%C 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}.
%H Andrew Howroyd, <a href="/A174704/b174704.txt">Table of n, a(n) for n = 0..500</a>
%H W. Edwin Clark, <a href="http://list.seqfan.eu/oldermail/seqfan/2010-March/004193.html">permutations p in S_n such that m <= |p(i)-p(i+1)| <= M for i from 1 to n-1</a>, SeqFan Discussion, Mar 27 2010.
%e 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).
%p 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
%t 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_ *)
%Y Cf. A003274, A174700, A174701, A174702, A174703, A174705, A174706, A174707, A174708, A185030, A216837.
%K nonn
%O 0,5
%A _W. Edwin Clark_, Mar 27 2010
%E Edited by _Alois P. Heinz_, Nov 27 2010
%E a(22) from _Alois P. Heinz_, Oct 12 2013
%E a(23) from _Alois P. Heinz_, Jan 14 2016
%E a(24)-a(35) from _Andrew Howroyd_, Apr 05 2016
|
