A174700 -id:A174700 - cp's OEIS frontend

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.

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

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

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.

A249665 The number of permutations p of {1,...,n} such that p(1)=1, p(n)=n, and |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, 1, 2, 6, 14, 28, 56, 118, 254, 541, 1140, 2401, 5074, 10738, 22711, 48001, 101447, 214446, 453355, 958395, 2025963, 4282685, 9053286, 19138115, 40456779, 85522862, 180789396, 382176531, 807895636, 1707837203, 3610252689, 7631830480

Offset: 1

Andrew Woods, Mar 06 2015

These partitions are qualified as 3-bounded and anchored. The number of 2-bounded anchored partitions of [1..n] is A000930(n). - Michel Marcus, Aug 13 2018

			For n = 5, the a(5) = 6 solutions are 123456, 132456, 134256, 135246, 142356, and 143256.

G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..250 from Andrew Woods).
Maria M. Gillespie, Kenneth G. Monks, and Kenneth M. Monks, Enumerating Anchored Permutations with Bounded Gaps, arXiv:1808.03573 [math.CO], 2018. Also Discrete Math.,343 (2020), #111957. (Proves the formulas and conjectures.)
Index entries for linear recurrences with constant coefficients, signature (2,-1,2,1,1,0,-1,-1).

Cf. A000930, A174700, A337654.

R:=PowerSeriesRing(Integers(), 41);
Coefficients(R!( x*(1-x-x^3)/(1-2*x+x^2-2*x^3-x^4-x^5+x^7+x^8) )); // G. C. Greubel, Sep 23 2024

(1-x-x^3)/(1 -2x +x^2 -2x^3 -x^4-x^5+x^7+x^8) + O[x]^33 // CoefficientList[#, x]& (* Jean-François Alcover, Sep 23 2018, after Colin Barker *)

Vec(x*(1 - x - x^3) / (1 - 2*x + x^2 - 2*x^3 - x^4 - x^5 + x^7 + x^8) + O(x^40)) \\ Colin Barker, Aug 13 2018

def A249665_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(1-x-x^3)/(1-2*x+x^2-2*x^3-x^4-x^5+x^7+x^8) ).list()
a=A249665_list(41); a[1:] # G. C. Greubel, Sep 23 2024

Let a(1)=1, g(1)=h(1)=0. For all n<1, let a(n)=g(n)=h(n)=0. Then:
a(n) = a(n-1) + g(n-1) + h(n-1),
g(n) = a(n-2) + a(n-3) + a(n-4) - a(n-6) + g(n-2) + g(n-4) + h(n-2),
h(n) = 2*a(n-3) + 2*a(n-4) + a(n-5) - a(n-7) + g(n-3) + g(n-5) + h(n-3).
Alternatively, let a(1)=1, a(n)=0 for n<1. Let b(1)=1, b(2)=0, b(3)=1, b(4)=3, b(5)=4, b(6)=5, b(7)=7, b(8)=10, and b(n)=b(n-1)+b(n-3) for n>8. Then:
a(n) = a(n-1)*b(1) + a(n-2)*b(2) + a(n-3)*b(3) + ... + a(1)*b(n-1).
From Colin Barker, Mar 07 2015 and Aug 13 2018: (Start)
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) + a(n-4) + a(n-5) - a(n-7) - a(n-8).
G.f.: x*(1 - x - x^3) / (1 - 2*x + x^2 - 2*x^3 - x^4 - x^5 + x^7 + x^8).
(End)

A187817 Number of permutations p of {1,...,n} such that exactly two elements of {p(1),...,p(i-1)} are between p(i) and p(i+1) for all i from 3 to n-1.

Original entry on oeis.org

1, 1, 2, 6, 4, 4, 4, 4, 8, 12, 20, 32, 52, 104, 188, 344, 616, 1116, 2232, 4236, 8084, 15212, 28760, 57520, 111512, 216804, 417560, 806440, 1612880, 3162132, 6209192, 12113136, 23670168, 47340336, 93411704, 184494460, 362693224, 713767712, 1427535424

Offset: 0

Alois P. Heinz, Oct 03 2013

nonn

			a(4) = 4: 2314, 2341, 3214, 3241.
a(5) = 4: 23514, 32514, 34152, 43152.
a(6) = 4: 341625, 346152, 431625, 436152.
a(7) = 4: 3471625, 4371625, 4517263, 5417263.
a(8) = 8: 34716258, 43716258, 45182736, 45817263, 54182736, 54817263, 56283741, 65283741.
a(9) = 12: 348172596, 438172596, 451827369, 459182736, 541827369, 549182736, 561928374, 569283741, 651928374, 659283741, 672938514, 762938514.

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

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

b:= proc(u, o) option remember; `if`(u+o<3, (u+o)!,
      `if`(o>2, b(sort([o-3, u+2])[]), 0)+
      `if`(u>2, b(sort([u-3, o+2])[]), 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 < 3, (u + o)!,
     If[o > 2, b @@ Sort[{o - 3, u + 2}], 0] +
     If[u > 2, b @@ Sort[{u - 3, o + 2}], 0]];
a[n_] := If[n == 0, 1, Sum[b @@ Sort[{j - 1, n - j}], {j, 1, n}]];
a /@ Range[0, 40] (* Jean-François Alcover, Mar 15 2021, after Alois P. Heinz *)

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

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A187817 Number of permutations p of {1,...,n} such that exactly two elements of {p(1),...,p(i-1)} are between p(i) and p(i+1) for all i from 3 to n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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