A174706 -id:A174706 - cp's OEIS frontend

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

1, 1, 2, 6, 24, 72, 180, 428, 1042, 2512, 5912, 13592, 30872, 69560, 155568, 345282, 761312, 1669612, 3645236, 7927404, 17180092, 37119040, 79986902, 171964534, 368959906, 790214816, 1689779842, 3608413750, 7696189046, 16397254612, 34902593796, 74230774324

Offset: 0

W. Edwin Clark, Mar 27 2010

nonn

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

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

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

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,3,n); # Alois P. Heinz, Mar 27 2010

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, 3, 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 *)

Empirical: a(n) = 3*a(n-1) - 4*a(n-3) + 3*a(n-4) - 4*a(n-5) - 9*a(n-6) + 2*a(n-7) + 5*a(n-8) + 9*a(n-9) + 17*a(n-10) + 16*a(n-11) + 14*a(n-12) + 8*a(n-13) - 2*a(n-14) - 5*a(n-15) - 5*a(n-16) - 6*a(n-17) - 4*a(n-18) - a(n-19) for n > 20. - Andrew Howroyd, Apr 08 2016

Empirical G.f.: (-3+x) + (2*(2-6*x+x^2+8*x^3-3*x^4+12*x^5 +9*x^6-17*x^7 -2*x^8-19*x^10 -26*x^11 -29*x^12-13*x^13+9*x^14+7*x^15 +4*x^16+6*x^17 +3*x^18)) / ((1+x)*(-1+x+x^2 +x^4+x^5)^2*(1-2*x+x^2-2*x^3-x^4-x^5 +x^7 +x^8)). - Andrew Howroyd, Apr 08 2016

a(19)-a(28) from R. H. Hardin, May 06 2010

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

Original entry on oeis.org

1, 0, 0, 2, 10, 12, 8, 12, 30, 72, 106, 128, 186, 316, 546, 836, 1186, 1756, 2720, 4224, 6366, 9374, 13932, 20958, 31470, 46820, 69194, 102458, 152152, 225548, 333142, 490964, 723690, 1067166, 1571878, 2311500, 3395804, 4987584, 7324024, 10747556

Offset: 1

W. Edwin Clark, Mar 27 2010

nonn

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

			For n = 4 the a(4) = 2 permutations are (2,4,1,3), (3,1,4,2).

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.

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

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,3,n): seq(a(n), n=1..14); # Alois P. Heinz, Mar 27 2010

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, 3, n]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 14}] (* Jean-François Alcover, Jun 01 2015, after Alois P. Heinz *)

Empirical: a(n) = 2*a(n-1) -a(n-2) +a(n-3) -a(n-4) +4*a(n-5) -6*a(n-6) +a(n-7) -2*a(n-8) +a(n-9) -5*a(n-10) +5*a(n-11) +a(n-12) +3*a(n-13) +a(n-14) +3*a(n-15) -a(n-16) -a(n-18) -a(n-19) -a(n-20) for n>20. - Andrew Howroyd, Apr 08 2016

Empirical G.f.: (3-2*x) + 2*(1-x) * (-1 +2*x -x^2 +x^3 +8*x^5 -5*x^6 -2*x^7 -5*x^8 -6*x^10 +3*x^11 +x^12 +3*x^13 +4*x^14 +7*x^15 +5*x^16 +3*x^17 +x^18) / ((1 -x +x^2)^2 * (-1 +x^2 +x^3)^2 * (1 -x^3 -x^4 -3*x^5 -x^6 +x^8 +x^9 +x^10)). - Andrew Howroyd, Apr 08 2016

More terms from Alois P. Heinz, Mar 30 2010

A174708 The number of permutations p of {1,...,n} satisfying |p(i)-p(i+1)| is in {4,5} for i from 1 to n-1.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 2, 18, 12, 0, 0, 0, 0, 0, 0, 30, 136, 112, 0, 0, 0, 0, 0, 0, 400, 1348, 1352, 408, 180, 120, 180, 408, 1352, 7356, 19008, 23028, 16788, 12630, 11744, 16742, 31320, 70256, 181106, 367560, 503800, 533504, 546468, 623546, 881384, 1468398, 2697374, 5164896, 8976002, 12977384

Offset: 1

W. Edwin Clark, Mar 27 2010

nonn

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

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.

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

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(4, 5, n): seq(a(n), n=1..19);  # Alois P. Heinz, Mar 27 2010

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

a(29)-a(42) from Robert Gerbicz, Nov 22 2010
a(43)-a(44) from Alois P. Heinz, Nov 27 2010
a(45)-a(55) from Andrew Howroyd, Apr 05 2016

A216837 Number of permutations p of {1,...,n} such that at most one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i from 1 to n-1.

Original entry on oeis.org

1, 1, 2, 6, 20, 72, 268, 1020, 3936, 15332, 60112, 236780, 935848, 3708236, 14721912, 58533264, 232991656, 928261480, 3700935760, 14763921580, 58924038816, 235258847064, 939576469152, 3753419774180, 14997257109992, 59933657096280, 239547378220840

Offset: 0

Alois P. Heinz, Oct 03 2013

nonn

			a(4) = 20 = 4! - 4, because 4 permutations of {1,...,4} do not satisfy the condition: 2314, 2341, 3214, 3241.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A174700, A174701, A174702, A174703, A174704, A174705, A174706, A174707, A174708, A185030, A356692.

b:= proc(u, o) option remember; `if`(u+o=0, 1,
      add(b(sort([o-j, u+j-1])[]), j=1..min(2, o))+
      add(b(sort([u-j, o+j-1])[]), j=1..min(2, u)))
    end:
a:= n-> `if`(n=0, 1, add(b(sort([j-1, n-j])[]), j=1..n)):
seq(a(n), n=0..35);

b[u_, o_] := b[u, o] = If[u+o == 0, 1, Sum[b[Sequence @@ Sort[{o-j, u+j-1}]], {j, 1, Min[2, o]}] + Sum[b[Sequence @@ Sort[{u-j, o+j-1}]], {j, 1, Min[2, u]}]]; a[n_] :=  If[n == 0, 1, Sum[b[Sequence @@ Sort[{j-1, n-j}]], {j, 1, n}]]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)

a(n) ~ c * 4^n, where c = 0.052940679853652794231561081876002147090052503777... - Vaclav Kotesovec, Feb 23 2014

a(n) = Sum_{k=0..n-1} A356692(n-1,k) for n >= 1. - Alois P. Heinz, Aug 28 2022

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.

Original entry on oeis.org

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

Offset: 1

W. Edwin Clark, Mar 27 2010

nonn

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

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.

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

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

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

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

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

a(23)-a(26) from Andrew Howroyd, Apr 05 2016

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.

Original entry on oeis.org

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

Offset: 1

W. Edwin Clark, Mar 27 2010

nonn

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

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.

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

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

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

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

a(21)-a(25) from Andrew Howroyd, Apr 05 2016

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.

Original entry on oeis.org

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

Offset: 0

W. Edwin Clark, Mar 27 2010

nonn

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

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

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.

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

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

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

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

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

Original entry on oeis.org

1, 0, 0, 2, 14, 90, 462, 1668, 4496, 11332, 31718, 100258, 336142, 1123212, 3614554, 11128872, 33226646, 98298782, 292626532, 879380718, 2654884024, 8000680668, 23965094526, 71287278676, 210922844362, 622218231406, 1833225926678, 5397521667296, 15876398740556, 46626957024628

Offset: 1

W. Edwin Clark, Mar 27 2010

nonn

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,5}.

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.

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

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, 5, n): seq(a(n), n=1..12); # Alois P. Heinz, Mar 27 2010

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, 5, n]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 12}] (* Jean-François Alcover, Jun 01 2015, after Alois P. Heinz *)

Edited by Alois P. Heinz, Nov 27 2010

a(20)-a(30) from Andrew Howroyd, Apr 05 2016

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

Original entry on oeis.org

1, 0, 0, 0, 0, 2, 28, 144, 292, 272, 160, 272, 844, 3888, 15830, 49080, 113468, 208224, 352112, 662810, 1497286, 3853054, 10238142, 25892602, 60223752, 130042700, 271136524, 572265830, 1258121046, 2878870324, 6714840216, 15583281118, 35434903508, 78777769972, 172664047056

Offset: 1

W. Edwin Clark, Mar 27 2010

nonn

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,5}.

			For n = 6 the a(6) = 2 permutations are (3,6,2,5,1,4), (4,1,5,2,6,3).

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.

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

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(3, 5, n); seq(a(n), n=1..14); # Alois P. Heinz, Mar 27 2010

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[3, 5, n]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 14}] (* Jean-François Alcover, Jun 01 2015, after Alois P. Heinz *)

Edited by Alois P. Heinz, Nov 27 2010

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

A185030 Number of permutations p of {1,...,n} such that exactly one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i from 2 to n-1.

Original entry on oeis.org

1, 1, 2, 2, 2, 4, 6, 10, 20, 36, 66, 132, 250, 478, 956, 1854, 3612, 7224, 14178, 27898, 55796, 110246, 218166, 436332, 865618, 1718902, 3437804, 6837398, 13607250, 27214500, 54216128, 108053078, 216106156, 431001044, 859831354, 1719662708, 3432314834

Offset: 0

Alois P. Heinz, Oct 03 2013

nonn

			a(3) = 2: 213, 231.
a(4) = 2: 2413, 3142.
a(5) = 4: 24135, 31524, 35142, 42531.
a(6) = 6: 251364, 315246, 361524, 416253, 462531, 526413.
a(7) = 10: 2513746, 2614753, 3162475, 3715246, 4172635, 4716253, 5173642, 5726413, 6274135, 6375142.
a(8) = 20: 25137468, 26138475, 27148635, 31624857, 31725864, 37152468, 37158642, 38162475, 41826357, 48172635, 51827364, 58173642, 61837524, 62841357, 62847531, 68274135, 68375142, 72851364, 73861524, 74862531.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

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

b:= proc(u, o) option remember; `if`(u+o<2, 1,
      `if`(o>1, b(sort([o-2, u+1])[]), 0)+
      `if`(u>1, b(sort([u-2, o+1])[]), 0))
    end:
a:= n-> `if`(n=0, 1, add(b(sort([j-1, n-j])[]), j=1..n)):
seq(a(n), n=0..40);

b[u_, o_] := b[u, o] = If[u+o<2, 1, If[o>1, b[Sequence @@ Sort[{o-2, u+1}]], 0] + If[u>1, b[Sequence @@ Sort[{u-2, o+1}]], 0]]; a[n_] := If[n == 0, 1, Sum[ b[Sequence @@ Sort[{j-1, n-j}]], {j, 1, n}]]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)

a(n) ~ c * 2^n, where c = 0.049258776257798093135680343... - Vaclav Kotesovec, Feb 23 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A174708 The number of permutations p of {1,...,n} satisfying |p(i)-p(i+1)| is in {4,5} for i from 1 to n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A216837 Number of permutations p of {1,...,n} such that at most one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i from 1 to n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs