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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 n-1. 13
1, 2, 6, 24, 120, 480, 1632, 5124, 15860, 50186, 158808, 496472, 1526736, 4627392, 13908192, 41570256, 123658616, 366072856, 1078360714, 3162222448, 9236396440, 26885780412, 78022705424, 225793573676, 651761629560, 1876905701372 (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}.

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.

FORMULA

Empirical g.f.: (1 -4*x +x^2 +7*x^3 +12*x^4 +48*x^6 -44*x^7 -281*x^8 -201*x^9 +916*x^10 +985*x^11 -610*x^12 -2618*x^13 -5903*x^14 -6152*x^15 -767*x^16 +5378*x^17 +3236*x^18 +724*x^19 +2277*x^20 -6324*x^21 -17140*x^22 -19864*x^23 -22238*x^24 -16849*x^25 +11373*x^26 +23042*x^27 +20080*x^28 +20616*x^29 -4068*x^30 -35020*x^31 -39693*x^32 -25456*x^33 -5223*x^34 +17255*x^35 +21318*x^36 +12303*x^37 +9497*x^38 -2463*x^39 -18738*x^40 -21259*x^41 -10659*x^42 +3557*x^43 +10194*x^44 +6788*x^45 +957*x^46 -1222*x^47 -2693*x^48 -3892*x^49 -2790*x^50 -543*x^51 +1464*x^52 +1615*x^53 +309*x^54 -525*x^55 -523*x^56 -330*x^57 -216*x^58 -79*x^59 +43*x^60 +77*x^61 +51*x^62 -5*x^63 -35*x^64 -20*x^65 -x^66 +3*x^67 +x^68) / ((1 -x -2*x^2 -3*x^3 -4*x^4 -27*x^6 -32*x^7 -25*x^8 +30*x^9 +61*x^10 +78*x^11 +56*x^12 +10*x^13 +10*x^14 -27*x^15 -43*x^16 -20*x^17 +x^18 +4*x^19 +25*x^20 +35*x^21 +x^22 -6*x^23 +x^24 -x^26 +2*x^27 +5*x^28 +3*x^29 +2*x^30 +x^31 -18*x^5)*(x^18 +2*x^17 -4*x^13 -2*x^12 -2*x^11 -2*x^10 +10*x^9 +7*x^8 +x^7 -5*x^6 -9*x^5 +x^4 -x^2 -2*x +1)^2). - Alois P. Heinz, Apr 08 2016

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

CROSSREFS

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

Sequence in context: A189567 A189859 A189569 * A178848 A173845 A258216

Adjacent sequences:  A174698 A174699 A174700 * A174702 A174703 A174704

KEYWORD

nonn

AUTHOR

W. Edwin Clark, Mar 27 2010

EXTENSIONS

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

a(23)-a(26) 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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 28 08:15 EDT 2016. Contains 275915 sequences.