login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A174702 The number of permutations p of {1,...,n} such that |p(i)-p(i+1)| is in {1,2,3,4,5} for all i from 1 to n-1. 13
1, 2, 6, 24, 120, 720, 3600, 15600, 61872, 236388, 901748, 3509106, 13716168, 53327912, 205176192, 780194112, 2937412512, 10991746368, 40961976672, 152144989056, 563313879080, 2078732476328, 7644789439842, 28024241472936, 102432262746504 (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,4,5}.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..100

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.

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, 5, n): seq(a(n), n=1..10); # 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[1, 5, n]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 10}] (* slow beyond n = 10 *) (* Jean-Fran├žois Alcover, Jun 01 2015, after Alois P. Heinz *)

CROSSREFS

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

Sequence in context: A189857 A189860 A274795 * A173846 A154654 A189862

Adjacent sequences:  A174699 A174700 A174701 * A174703 A174704 A174705

KEYWORD

nonn

AUTHOR

W. Edwin Clark, Mar 27 2010

EXTENSIONS

a(15)-a(20) from R. H. Hardin, May 06 2010

a(21)-a(25) 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 10 07:51 EST 2016. Contains 278994 sequences.