A302118 -id:A302118 - cp's OEIS frontend

A003274 Number of key permutations of length n: permutations {a_i} with |a_i - a_{i-1}| = 1 or 2.

1, 1, 2, 6, 12, 20, 34, 56, 88, 136, 208, 314, 470, 700, 1038, 1534, 2262, 3330, 4896, 7192, 10558, 15492, 22724, 33324, 48860, 71630, 105002, 153912, 225594, 330650, 484618, 710270, 1040980, 1525660, 2235994, 3277040, 4802768, 7038832, 10315944, 15118786

Offset: 0

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 251 terms from R. H. Hardin)
S. Avgustinovich and S. Kitaev, On uniquely k-determined permutations, Discr. Math., 308 (2008), 1500-1507.
Hugh Denoncourt, Ordinal pattern probabilities for symmetric random walks, arXiv:1907.07172 [math.CO], 2019.
E. S. Page, Systematic generation of ordered sequences using recurrence relations, Computer J., 14 (1971), 150-153.
E. S. Page, Systematic generation of ordered sequences using recurrence relations, The Computer Journal 14 (1971), 150-153. (Annotated scanned copy)
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-2,1).

Cf. A069241, A092526, A174700, A263719, A302118.

A003274:=-(1-z+3*z**2-2*z**3+z**5)/(z**3+z-1)/(z-1)**2; # [Conjectured by Simon Plouffe in his 1992 dissertation.]

CoefficientList[Series[-(x^6 - x^5 + x^3 + 2 x^2 - 2 x + 1)/((x^3 + x - 1) (x - 1)^2), {x, 0, 39}], x] (* Michael De Vlieger, Oct 01 2019 *)

For n > 1, a(n) = 2*A069241(n).
G.f.: -(x^6 - x^5 + x^3 + 2*x^2 - 2*x + 1)/((x^3 + x - 1)*(x-1)^2).
Limit_{n->oo} a(n+1)/a(n) = A092526 = 1/A263719. - Alois P. Heinz, Apr 15 2018

Better description and g.f. from Erich Friedman

a(0)=1 prepended and g.f. adapted by Alois P. Heinz, Apr 01 2018

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.

Original entry on oeis.org

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

A302119 Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| in {1,3}.

Original entry on oeis.org

1, 1, 1, 1, 4, 6, 16, 20, 44, 59, 122, 169, 321, 456, 825, 1201, 2091, 3100, 5246, 7893, 13083, 19907, 32497, 49869, 80510, 124335, 199124, 308956, 491945, 765898, 1214494, 1895490, 2996873, 4685587, 7392756, 11573134, 18232908, 28568658, 44962192, 70494629

Offset: 0

Alois P. Heinz, Apr 01 2018

			a(1) = 1: 1.
a(2) = 1: 12.
a(3) = 1: 123.
a(4) = 4: 1234, 1432, 2143, 3214.
a(5) = 6: 12345, 12543, 14325, 14523, 32145, 34125.
a(6) = 16: 123456, 123654, 125436, 125634, 143256, 143652, 145236, 145632, 214365, 214563, 321456, 341256, 365214, 412365, 521436, 541236.

Alois P. Heinz, Table of n, a(n) for n = 0..5102
Eric Weisstein's World of Mathematics, Hamiltonian path
Wikipedia, Hamiltonian path
Index entries for linear recurrences with constant coefficients, signature (1,3,-2,-1,-1,-3,1,1,3,1,1,0,-2,0,-1)

Cf. A069241, A293506, A293560, A302118.

G.f.: (x^16 -x^15 +x^13 +x^12 +2*x^11 -x^10 -5*x^9 -6*x^8 -2*x^7 +5*x^6 +3*x^5 +3*x^4 -x^3 -3*x^2+1) / ((x-1) *(x+1) *(x^5+x^3+x-1) *(x^4+x^2-1)^2).
a(n) = ceiling(A302118(n)/2).
limit_{n->infinity} a(n)/a(n+1) = A293560 = 1/A293506 = 0.63688291680184484849...

A307269 Number of permutations p of [n] such that |p(i) - p(i-1)| is in {2,5} for all i from 2 to n.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 2, 14, 12, 8, 28, 58, 44, 120, 254, 226, 344, 932, 1262, 1380, 2958, 5006, 5632, 9496, 18204, 23756, 32758, 59992, 90494, 118740, 196318, 320814, 437270, 653770, 1077580, 1570054, 2233920, 3551168, 5426452, 7714408, 11709864

Offset: 0

Alois P. Heinz, Apr 01 2019

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

			a(6) = 2: 246135, 531642.
a(7) = 14: 1357246, 1642753, 2461357, 2753164, 3164275, 3572461, 4275316, 4613572, 5316427, 5724613, 6135724, 6427531, 7246135, 7531642.
a(8) = 12: 13572468, 13864275, 16427538, 16835724, 42753168, 42753861, 57246138, 57246831, 83164275, 83572461, 86135724, 86427531.
a(9) = 8: 168357249, 168357942, 249753168, 249753861, 861357249, 861357942, 942753168, 942753861.

Cf. A174703, A302118, A328648.

b:= proc(s, l) option remember; `if`(s={}, 1, add(
      `if`(abs(l-j) in {2, 5}, b(s minus {j}, j), 0), j=s))
    end:
a:= proc(n) option remember; if n=0 then 1 else
      add(b({$1..n} minus {j}, j), j=1..n) fi
    end:
seq(a(n), n=0..20);

b[s_, l_] := b[s, l] = If[s == {}, 1, Sum[If[MemberQ[{2, 5}, Abs[l - j]], b[s ~Complement~ {j}, j], 0], {j, s}]];
a[n_] := a[n] = If[n==0, 1, Sum[b[Range[n] ~Complement~ {j}, j], {j, n}]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 27}] (* Jean-François Alcover, Oct 23 2021, after Alois P. Heinz *)

A328648 Number of permutations p of [n] such that |p(i) - p(i-1)| is in {2,7} for all i from 2 to n.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 0, 0, 2, 18, 12, 0, 12, 62, 76, 32, 44, 162, 600, 714, 386, 550, 2514, 5320, 4140, 3336, 8626, 24722, 33428, 27110, 34812, 96210, 200322, 220360, 213368, 376178, 894780, 1400578, 1473944, 1810538, 3653304, 7170370, 9467970

Offset: 0

Alois P. Heinz, Oct 23 2019

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

			a(8) = 2: 24681357, 75318642.
a(9) = 18: 135792468, 186429753, 246813579, 297531864, 318642975, 357924681, 429753186, 468135792, 531864297, 579246813, 642975318, 681357924, 753186429, 792468135, 813579246, 864297531, 924681357, 975318642.
a(10) = 12: 135792468(10), 13(10)8642975, 186429753(10), 18(10)3579246, 579246813(10), 5792468(10)31, 642975318(10), 6429753(10)81, (10)318642975, (10)357924681, (10)813579246, (10)864297531.

Cf. A174703, A174708, A302118, A307269.

b:= proc(s, l) option remember; `if`(s={}, 1, add(`if`(l=0
      or abs(l-j) in {2, 7}, b(s minus {j}, j), 0), j=s))
    end:
a:= n-> b({$1..n}, 0):
seq(a(n), n=0..20);

b[s_, l_] := b[s, l] = If[s == {}, 1, Sum[If[l == 0 || MemberQ[{2, 7}, Abs[l - j]], b[s ~Complement~ {j}, j], 0], {j, s}]];
a[n_] := b[Range[n], 0];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 23 2021, after Alois P. Heinz *)

cp's OEIS Frontend

A003274 Number of key permutations of length n: permutations {a_i} with |a_i - a_{i-1}| = 1 or 2.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A302119 Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| in {1,3}.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A307269 Number of permutations p of [n] such that |p(i) - p(i-1)| is in {2,5} for all i from 2 to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

A328648 Number of permutations p of [n] such that |p(i) - p(i-1)| is in {2,7} for all i from 2 to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica