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

1, 0, 0, 0, 0, 2, 14, 12, 0, 0, 0, 0, 30, 104, 112, 48, 40, 48, 112, 400, 964, 1276, 1202, 1280, 1714, 3004, 6120, 11472, 16730, 20884, 26308, 36676, 57570, 96642, 158864, 237592, 330064, 453476, 647862, 975210, 1515766, 2345634, 3505078, 5064148, 7241688

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 {3,4}.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..500
• 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, A174703, A174704, A174705, A174707, A174708, A185030, A216837.

Extensions

a(28)-a(38) from Robert Gerbicz, Nov 27 2010

a(39)-a(45) from Andrew Howroyd, Apr 05 2016