A003274 -id:A003274 - cp's OEIS frontend

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.

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

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

Original entry on oeis.org

1, 1, 2, 2, 8, 12, 32, 40, 88, 118, 244, 338, 642, 912, 1650, 2402, 4182, 6200, 10492, 15786, 26166, 39814, 64994, 99738, 161020, 248670, 398248, 617912, 983890, 1531796, 2428988, 3790980, 5993746, 9371174, 14785512, 23146268, 36465816, 57137316, 89924384

Offset: 0

Alois P. Heinz, Apr 01 2018

			a(3) = 2: 123, 321.
a(4) = 8: 1234, 1432, 2143, 2341, 3214, 3412, 4123, 4321.
a(5) = 12: 12345, 12543, 14325, 14523, 32145, 32541, 34125, 34521, 52143, 52341, 54123, 54321.

Alois P. Heinz, Table of n, a(n) for n = 0..5100
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. A003274, A174700, A293506, A293560, A302119, A307269, A328648.

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

A069241 Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| <= 2.

Original entry on oeis.org

1, 1, 1, 3, 6, 10, 17, 28, 44, 68, 104, 157, 235, 350, 519, 767, 1131, 1665, 2448, 3596, 5279, 7746, 11362, 16662, 24430, 35815, 52501, 76956, 112797, 165325, 242309, 355135, 520490, 762830, 1117997, 1638520, 2401384, 3519416, 5157972, 7559393, 11078847

Offset: 0

Don Knuth, Apr 13 2002

Equivalently, the number of bandwidth-at-most-2 arrangements of a straight line of n vertices.

			For example, the six Hamiltonian paths when n=4 are 1234, 1243, 1324, 1342, 2134, 3124.

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-2,1).

Cf. A003274, A000930, A092526, A263719, A302119.

a:= n-> (Matrix([[1,1,1,0,1]]). Matrix(5, (i,j)-> if i=j-1 then 1 elif j=1 then [3,-3,2,-2,1][i] else 0 fi)^n)[1,3]: seq(a(n), n=0..50); # Alois P. Heinz, Sep 09 2008

a[0] = a[1] = a[2] = 1; a[3] = 3; a[4] = 6; a[n_] := a[n] = 3a[n-1] - 3a[n-2] + 2a[n-3] - 2a[n-4] + a[n-5]; Table[a[n], {n, 0, 38}] (* Jean-François Alcover, Feb 13 2015 *)
CoefficientList[Series[(3+x+x^2)/(1-x-x^3)-(2-x)/(1-x)^2,{x,0,60}],x] (* or *) LinearRecurrence[{3,-3,2,-2,1},{1,1,1,3,6},60] (* Harvey P. Dale, Apr 07 2019 *)

a(n) = A003274(n)/2, n > 1.
a(n) = 3*s(n) + s(n-1) + s(n-2) - 2 - n, where s(n) = A000930(n).
G.f.: (3+x+x^2)/(1-x-x^3) - (2-x)/(1-x)^2.
Lim_{n->infinity} a(n+1)/a(n) = A092526 = 1/A263719. - Alois P. Heinz, Apr 15 2018

A333833 Number of permutations p of [n] such that |p(i) - p(i-1)| <= 2 and |p(i) - p(i-2)| <= 3.

Original entry on oeis.org

1, 1, 2, 6, 12, 14, 18, 28, 42, 56, 74, 102, 144, 200, 274, 376, 520, 720, 994, 1370, 1890, 2610, 3604, 4974, 6864, 9474, 13078, 18052, 24916, 34390, 47468, 65520, 90436, 124826, 172294, 237814, 328250, 453076, 625370, 863184, 1191434, 1644510, 2269880, 3133064

Offset: 0

Alois P. Heinz, Apr 07 2020

			a(5) = 14: 12345, 12354, 12435, 12453, 13245, 21345, 31245, 35421, 45321, 53421, 54213, 54231, 54312, 54321.
a(6) = 18: 123456, 123465, 123546, 123564, 124356, 132456, 213456, 213465, 312456, 465321, 564312, 564321, 645321, 653421, 654213, 654231, 654312, 654321.

Alois P. Heinz, Table of n, a(n) for n = 0..7141
Alois P. Heinz, Animation of a(10) = 74 permutations
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1).

Cf. A003274, A086106, A174700, A263690, A263696, A302510, A307269, A328648, A338614.

Join[{1, 1, 2, 6, 12}, LinearRecurrence[{1, 0, 0, 1}, {14, 18, 28, 42}, 40]] (* Jean-François Alcover, Oct 26 2021 *)

G.f.: -(2*x^8+4*x^7+2*x^6+x^5+5*x^4+4*x^3+x^2+1)/(x^4+x-1).
a(n) = 2*A302510(n-2) for n >= 6.
Limit_{n-> infinity} a(n+1)/a(n) = A086106.

A363181 Number of permutations p of [n] such that for each i in [n] we have: (i>1) and |p(i)-p(i-1)| = 1 or (i

Original entry on oeis.org

1, 0, 2, 2, 8, 14, 54, 128, 498, 1426, 5736, 18814, 78886, 287296, 1258018, 4986402, 22789000, 96966318, 461790998, 2088374592, 10343408786, 49343711666, 253644381032, 1268995609502, 6756470362374, 35285321738624, 194220286045506, 1054759508543554

Offset: 0

Alois P. Heinz, May 19 2023

nonn

Number of permutations p of [n] such that each element in p has at least one neighbor whose value is smaller or larger by one.

Number of permutations of [n] having n occurrences of the 1-box pattern.

			a(0) = 1: (), the empty permutation.
a(1) = 0.
a(2) = 2: 12, 21.
a(3) = 2: 123, 321.
a(4) = 8: 1234, 1243, 2134, 2143, 3412, 3421, 4312, 4321.
a(5) = 14: 12345, 12354, 12543, 21345, 21543, 32145, 32154, 34512, 34521, 45123, 45321, 54123, 54312, 54321.
a(6) = 54: 123456, 123465, 123654, 124356, 124365, 125634, 125643, 126534, 126543, 213456, 213465, 214356, 214365, 215634, 215643, 216534, 216543, 321456, 321654, 341256, 341265, 342156, 342165, 345612, 345621, 346512, 346521, 431256, 431265, 432156, 432165, 435612, 435621, 436512, 436521, 456123, 456321, 561234, 561243, 562134, 562143, 563412, 563421, 564312, 564321, 651234, 651243, 652134, 652143, 653412, 653421, 654123, 654312, 654321.

Alois P. Heinz, Table of n, a(n) for n = 0..803
FindStat, St000064: The number of one-box pattern of a permutation.
S. Kitaev, J. Remmel, The 1-box pattern on pattern avoiding permutations, arXiv:1305.6970 [math.CO], 2013.

Main diagonal of A346462.

Cf. A002464, A003274, A011655, A095816, A127697, A179957, A229730, A271212, A211694, A333833, A363236.

a:= proc(n) option remember; `if`(n<4, [1, 0, 2$2][n+1],
      3/2*a(n-1)+(n-3/2)*a(n-2)-(n-5/2)*a(n-3)+(n-4)*a(n-4))
    end:
seq(a(n), n=0..30);

a(n) = A346462(n,n).
a(n)/2 mod 2 = A011655(n-1) for n>=1.
a(n) ~ sqrt(Pi) * n^((n+1)/2) / (2 * exp(n/2 - sqrt(n)/2 + 7/16)) * (1 - 119/(192*sqrt(n))). - Vaclav Kotesovec, May 26 2023

A137725 Number of sequences of length n with elements {-2,-1,+1,+2}, such that the sum of elements of the whole sequence but of no proper subsequence equals 0 modulo n. For n>=4, the number of Hamiltonian (directed) circuits on the circulant graph C_n(1,2).

Original entry on oeis.org

4, 4, 16, 18, 24, 32, 46, 58, 82, 112, 158, 220, 316, 450, 650, 938, 1364, 1982, 2892, 4220, 6170, 9022, 13206, 19332, 28314, 41472, 60760, 89022, 130446, 191150, 280120, 410506, 601600, 881656, 1292102, 1893634, 2775226, 4067256, 5960822, 8735972, 12803156, 18763898, 27499794, 40302866, 59066684

Offset: 1

Max Alekseyev, Feb 08 2008

nonn

Number of 1-D walks with jumps to next-nearest neighbors with n steps, starting at 0 and ending at -2n, -n, 0, n, or 2n, such that every point is visited at most once and every pair of points at the distance n contains at least one unvisited point (not counting the ending visit). Cf. A092765.

For n>1, the number of circular permutations (counted up to rotations) of {0, 1,...,n-1} such that the distance between every two adjacent elements is -2,-1,1,or 2 modulo n. Cf. A003274.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Mordecai J. Golin and Yiu Cho Leung, Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees, Hamiltonian Cycles and other Parameters, Technical report HKUST-TCSC-2004-02. See also
Eric Weisstein's World of Mathematics, Circulant Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,0,-1,1).

Cf. A124353, A137726.

CoefficientList[Series[-2*x^2-2*x-6-1/(x+1)+2/(x-1)^2+1/(x-1)+(4*x-6)/(x^3+x-1), {x, 0, 50}], x] (* G. C. Greubel, Apr 28 2017 *)

my(x='x+O('x^50)); Vec(-2*x^2-2*x-6-1/(x+1)+2/(x-1)^2+1/(x-1)+(4*x-6)/(x^3+x-1)) \\ G. C. Greubel, Apr 28 2017

For even n>=4, a(n) = 2*(n + 3*A000930(n) - 2*A000930(n-1)); for odd n>=3, a(n) = 2*(n + 1 + 3*A000930(n) - 2*A000930(n-1)).
For n>8, a(n) = 2*a(n-1) - a(n-3) - a(n-5) + a(n-6) or a(n) = a(n-1) + a(n-2) - a(n-5) - 4.
O.g.f.: -2*x^2-2*x-6-1/(x+1)+2/(x-1)^2+1/(x-1)+(4*x-6)/(x^3+x-1). - R. J. Mathar, Feb 10 2008

Typo in formulas corrected by Max Alekseyev, Nov 03 2010

A249631 Number of permutations p of {1,...,n} such that |p(i+1)-p(i)| < k, k=2,...,n; T(n,k), read by rows.

Original entry on oeis.org

2, 2, 6, 2, 12, 24, 2, 20, 72, 120, 2, 34, 180, 480, 720, 2, 56, 428, 1632, 3600, 5040, 2, 88, 1042, 5124, 15600, 30240, 40320, 2, 136, 2512, 15860, 61872, 159840, 282240, 362880, 2, 208, 5912, 50186, 236388, 773040, 1764000, 2903040, 3628800

Offset: 2

Li-yao Xia, Nov 02 2014

			Triangle starts with n=2:
2;
2,  6;
2, 12,  24;
2, 20,  72, 120;
2, 34, 180, 480, 720;

Li-yao Xia, Triangle of T(n,k) for n=2..10, k=2..n

Cf. A000142, main diagonal, A062119, subdiagonal.
Cf. A003274, A174700, A174701, A174702, 2nd to 5th columns, T(n,k), k=3,4,5,6.
Cf. A174703, A174704, A174705, A174706, A174707, A174708, similar definitions.

a n x = filter (\l -> all (< x) (zipWith (\x y -> abs (x - y)) l (tail l))) (permutations [1 .. n])

isokp(perm, k) = {for (i=1, #perm-1, if (abs(perm[i]-perm[i+1]) >= k, return (0));); return (1);}
tabl(nn) = {for (n=2, nn, for (k=2, n, print1(sum(i=1, n!, isokp(numtoperm(n, i), k)), ", ");); print(););} \\ Michel Marcus, Nov 06 2014

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A069241 Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j| <= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A333833 Number of permutations p of [n] such that |p(i) - p(i-1)| <= 2 and |p(i) - p(i-2)| <= 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A363181 Number of permutations p of [n] such that for each i in [n] we have: (i>1) and |p(i)-p(i-1)| = 1 or (i

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A137725 Number of sequences of length n with elements {-2,-1,+1,+2}, such that the sum of elements of the whole sequence but of no proper subsequence equals 0 modulo n. For n>=4, the number of Hamiltonian (directed) circuits on the circulant graph C_n(1,2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A249631 Number of permutations p of {1,...,n} such that |p(i+1)-p(i)| < k, k=2,...,n; T(n,k), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

PARI