|
| |
|
|
A174708
|
|
The number of permutations p of {1,...,n} satisfying |p(i)-p(i+1)| is in {4,5} for i from 1 to n-1.
|
|
14
|
|
|
|
1, 0, 0, 0, 0, 0, 0, 2, 18, 12, 0, 0, 0, 0, 0, 0, 30, 136, 112, 0, 0, 0, 0, 0, 0, 400, 1348, 1352, 408, 180, 120, 180, 408, 1352, 7356, 19008, 23028, 16788, 12630, 11744, 16742, 31320, 70256, 181106, 367560, 503800, 533504, 546468, 623546, 881384, 1468398, 2697374, 5164896, 8976002, 12977384
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
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 {4,5}.
|
|
|
LINKS
|
|
|
|
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(4, 5, n): seq(a(n), n=1..19); # 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[4, 5, n]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 19}] (* Jean-François Alcover, Jun 01 2015, after Alois P. Heinz *)
|
|
|
CROSSREFS
|
Cf. A003274, A174700, A174701, A174702, A174703, A174704, A174705, A174706, A174707, A185030, A216837.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
