

A174701


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


11



1, 2, 6, 24, 120, 480, 1632, 5124, 15860, 50186, 158808, 496472, 1526736, 4627392, 13908192, 41570256, 123658616, 366072856, 1078360714, 3162222448, 9236396440, 26885780412
(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 ij is in {1,2,3,4}.


LINKS

Table of n, a(n) for n=1..22.
W. Edwin Clark, permutations p in S_n such that m <= p(i)p(i+1) <= M for i from 1 to n1, SeqFan Discussion, Mar 2010.


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[t1])); 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[t1])); if m<=d and d<=M then p(t+1) fi od; h:= l[t]; for j from t to n1 do l[j]:= l[j+1] od; l[n]:= h fi end; p(1); cnt end: a:=n>f(1, 4, n); # Alois P. Heinz, Mar 27 2010


CROSSREFS

Cf. A003274, A174700, A174702, A174703, A174704, A174705, A174706, A174707, A174708, A185030, A216837.
Sequence in context: A189567 A189859 A189569 * A178848 A173845 A072856
Adjacent sequences: A174698 A174699 A174700 * A174702 A174703 A174704


KEYWORD

more,nonn


AUTHOR

W. Edwin Clark, Mar 27 2010


EXTENSIONS

a(16)a(22) from R. H. Hardin, May 06 2010


STATUS

approved



