login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A174704 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. 14
1, 1, 0, 0, 2, 14, 60, 152, 256, 464, 1124, 3114, 8324, 20166, 44958, 97666, 217792, 501356, 1163776, 2668126, 6006712, 13363390, 29660118, 66006498, 147147006, 327471130, 725850010, 1602363242, 3527859498, 7756716420, 17040151108, 37393219368, 81932669910, 179223992670, 391448289188, 853909743368 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

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

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..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 27 2010.

EXAMPLE

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).

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(2, 4, n): seq(a(n), n=1..12); # 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[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 *)

CROSSREFS

Cf. A003274, A174700, A174701, A174702, A174703, A174705, A174706, A174707, A174708, A185030, A216837.

Sequence in context: A232601 A285153 A232370 * A058738 A095376 A153332

Adjacent sequences:  A174701 A174702 A174703 * A174705 A174706 A174707

KEYWORD

nonn

AUTHOR

W. Edwin Clark, Mar 27 2010

EXTENSIONS

Edited by Alois P. Heinz, Nov 27 2010

a(22) from Alois P. Heinz, Oct 12 2013

a(23) from Alois P. Heinz, Jan 14 2016

a(24)-a(35) from Andrew Howroyd, Apr 05 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 10 02:02 EDT 2020. Contains 336365 sequences. (Running on oeis4.)