|
| |
|
|
A174700
|
|
The number of permutations p of {1,...,n} such that |p(i)-p(i+1)| is in {1,2,3} for all i from 1 to n-1.
|
|
8
|
|
|
|
1, 2, 6, 24, 72, 180, 428, 1042, 2512, 5912, 13592, 30872, 69560, 155568, 345282, 761312, 1669612, 3645236, 7927404, 17180092, 37119040, 79986902, 171964534, 368959906, 790214816, 1689779842, 3608413750, 7696189046
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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 {1,2,3}.
|
|
|
LINKS
|
Table of n, a(n) for n=1..28.
|
|
|
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(1, 3, n); # Alois P. Heinz, Mar 27 2010
|
|
|
CROSSREFS
|
Cf. A003274, A174701, A174702, A174703, A174704, A174705, A174706, A174707, A174708.
Sequence in context: A027562 A096259 A087645 * A216158 A178847 A173844
Adjacent sequences: A174697 A174698 A174699 * A174701 A174702 A174703
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
W. Edwin Clark, Mar 27 2010
|
|
|
EXTENSIONS
|
a(19)-a(28) from R. H. Hardin, May 06 2010
|
|
|
STATUS
|
approved
|
| |
|
|
