A130152 -id:A130152 - cp's OEIS frontend

A306209 Number A(n,k) of permutations of [n] within distance k of a fixed permutation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 6, 5, 1, 1, 1, 2, 6, 14, 8, 1, 1, 1, 2, 6, 24, 31, 13, 1, 1, 1, 2, 6, 24, 78, 73, 21, 1, 1, 1, 2, 6, 24, 120, 230, 172, 34, 1, 1, 1, 2, 6, 24, 120, 504, 675, 400, 55, 1, 1, 1, 2, 6, 24, 120, 720, 1902, 2069, 932, 89, 1, 1, 1, 2, 6, 24, 120, 720, 3720, 6902, 6404, 2177, 144, 1

Offset: 0

Alois P. Heinz, Jan 29 2019

A(n,k) counts permutations p of [n] such that |p(j)-j| <= k for all j in [n].

			A(4,1) = 5: 1234, 1243, 1324, 2134, 2143.
A(5,2) = 31: 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254, 13425, 13524, 14235, 14253, 14325, 14523, 21345, 21354, 21435, 21453, 21534, 21543, 23145, 23154, 24135, 24153, 31245, 31254, 31425, 31524, 32145, 32154, 34125.
Square array A(n,k) begins:
  1,  1,   1,    1,    1,     1,     1,     1,     1, ...
  1,  1,   1,    1,    1,     1,     1,     1,     1, ...
  1,  2,   2,    2,    2,     2,     2,     2,     2, ...
  1,  3,   6,    6,    6,     6,     6,     6,     6, ...
  1,  5,  14,   24,   24,    24,    24,    24,    24, ...
  1,  8,  31,   78,  120,   120,   120,   120,   120, ...
  1, 13,  73,  230,  504,   720,   720,   720,   720, ...
  1, 21, 172,  675, 1902,  3720,  5040,  5040,  5040, ...
  1, 34, 400, 2069, 6902, 17304, 30960, 40320, 40320, ...

Alois P. Heinz, Antidiagonals n = 0..36, flattened
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
Torleiv Kløve, Generating functions for the number of permutations with limited displacement, Electron. J. Combin., 16 (2009), #R104.

Columns k=0..10 give: A000012, A000045(n+1), A002524, A002526, A072856, A154654, A154655, A154656, A154657, A154658, A154659.
Rows n=1-2 give: A000012, A040000.
Main diagonal gives A000142.
A(2n,n) gives A048163(n+1).
A(2n+1,n) gives A092552(n+1).
A(n,floor(n/2)) gives A306267.
A(n+2,n) gives A001564.
Cf. A130152.

A[0, _] = 1;
A[n_ /; n > 0, k_] := A[n, k] = Permanent[Table[If[Abs[i - j] <= k, 1, 0], {i, 1, n}, {j, 1, n}]];
Table[A[n - k, k], {n, 0, 12}, {k, n, 0, -1 }] // Flatten (* Jean-François Alcover, Oct 18 2021, after Alois P. Heinz in A130152 *)

A(n,k) = Sum_{j=0..k} A130152(n,j) for n > 0, A(0,k) = 1.

A299789 Number T(n,k) of permutations p of [n] such that min_{j=1..n} |p(j)-j| = k; triangle T(n,k), n >= 0, 0 <= k <= floor(n/2), read by rows.

Original entry on oeis.org

0, 1, 1, 1, 4, 2, 15, 8, 1, 76, 40, 4, 455, 236, 28, 1, 3186, 1648, 198, 8, 25487, 13125, 1596, 111, 1, 229384, 117794, 14534, 1152, 16, 2293839, 1175224, 146372, 12929, 435, 1, 25232230, 12903874, 1621282, 152430, 6952, 32, 302786759, 154615096, 19563257, 1922364, 112416, 1707, 1

Offset: 0

Alois P. Heinz, Jan 21 2019

			T(4,0) = 15: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2314, 2431, 3124, 3214, 3241, 4132, 4213, 4231.
T(4,1) = 8: 2143, 2341, 2413, 3142, 3421, 4123, 4312, 4321.
T(4,2) = 1: 3412.
T(5,2) = 4: 34512, 34521, 45123, 54123.
T(6,3) = 1: 456123.
T(7,3) = 8: 4567123, 4567132, 4567213, 4567231, 5671234, 5761234, 6571234, 7561234.
T(8,4) = 1: 56781234.
T(9,4) = 16: 567891234, 567891243, 567891324, 567891342, 567892134, 567892143, 567892314, 567892341, 678912345, 679812345, 687912345, 697812345, 768912345, 769812345, 867912345, 967812345.
Triangle T(n,k) begins:
          0;
          1;
          1,         1;
          4,         2;
         15,         8,        1;
         76,        40,        4;
        455,       236,       28,       1;
       3186,      1648,      198,       8;
      25487,     13125,     1596,     111,      1;
     229384,    117794,    14534,    1152,     16;
    2293839,   1175224,   146372,   12929,    435,    1;
   25232230,  12903874,  1621282,  152430,   6952,   32;
  302786759, 154615096, 19563257, 1922364, 112416, 1707, 1;
  ...

Alois P. Heinz, Rows n = 0..21, flattened

Columns k=0-1 give: A002467, A296050.
Row sums give A000142 (for n>0).
T(2n,n) gives A057427.
T(2n+1,n) gives A000079.
T(2n+2,n) gives A306545.
Cf. A000166, A001883, A075851, A075852, A129118, A130152, A306543.

b:= proc(s) option remember; (n-> `if`(n=1, x^(s[1]-1),
      add((p-> add(coeff(p, x, i)*x^min(i, abs(n-j)),
      i=0..degree(p)))(b(s minus {j})), j=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..max(0, degree(p))))(b({$1..n})):
seq(T(n), n=0..14);
# second Maple program:
A:= proc(n, k) option remember; `if`(n=0, 0, LinearAlgebra[
      Permanent](Matrix(n, (i, j)-> `if`(abs(i-j)>=k, 1, 0))))
    end:
T:= (n, k)-> A(n, k)-A(n, k+1):
seq(seq(T(n, k), k=0..n/2), n=0..14);

A[n_, k_] := A[n, k] = If[n==0, 0, Permanent[Table[If[Abs[i-j] >= k, 1, 0], {i, 1, n}, {j, 1, n}]]];
T[n_, k_] := A[n, k] - A[n, k+1];
Table[T[n, k], {n, 0, 14}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, May 01 2019, from 2nd Maple program *)

T(n,k) = A306543(n,k) - A306543(n,k+1) for n > 0.
Sum_{k=1..floor(n/2)} k * T(n,k) = A129118(n).
Sum_{k=1..floor(n/2)} T(n,k) = A000166(n).
Sum_{k=2..floor(n/2)} T(n,k) = A001883(n).
Sum_{k=3..floor(n/2)} T(n,k) = A075851(n).
Sum_{k=4..floor(n/2)} T(n,k) = A075852(n).

A130153 For each permutation p of {1,2,...,n} define maxabsjump(p) = max(|p(i) - i|, 1<=i<=n); a(n) is the sum of maxabsjumps of all p.

Original entry on oeis.org

0, 1, 8, 52, 362, 2779, 23749, 224570, 2334827, 26504418, 326476313, 4338953453, 61908434299, 944065986251, 15325676747363, 263910466293264, 4805394642545408, 92254524334410750, 1862526899218400010, 39449927915059031609, 874745258339527435041, 20265180489604116160763

Offset: 1

Emeric Deutsch, May 27 2007

nonn

a(n) = Sum_{k=0..n-1} k*A130152(n,k). For the case when in the definition |p(i)-i| is replaced by p(i)-i, see A018927.

			a(3) = 8 because the permutations 123,132,213,231,312 and 321 have maxabsjumps 0,1,1,2,2 and 2, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..23

Cf. A130152, A018927.

with(combinat): for n from 1 to 7 do P:=permute(n): for i from 0 to n-1 do ct[i]:=0 od: for j from 1 to n! do if max(seq(abs(P[j][i]-i),i=1..n))=0 then ct[0]:=ct[0]+1 elif max(seq(abs(P[j][i]-i),i=1..n))=1 then ct[1]:=ct[1]+1 elif max(seq(abs(P[j][i]-i),i=1..n))=2 then ct[2]:=ct[2]+1 elif max(seq(abs(P[j][i]-i),i=1..n))=3 then ct[3]:=ct[3]+1 elif max(seq(abs(P[j][i]-i),i=1..n))=4 then ct[4]:=ct[4]+1 elif max(seq(abs(P[j][i]-i),i=1..n))=5 then ct[5]:=ct[5]+1 elif max(seq(abs(P[j][i]-i),i=1..n))=6 then ct[6]:=ct[6]+1 else fi od: a[n]:=sum(k*ct[k],k=0..n-1): od: seq(a[n],n=1..7); # a cumbersome program to obtain the first 7 terms of the sequence
n := 8: st := proc (p) max(seq(abs(p[j]-j), j = 1 .. nops(p))) end proc: with(combinat): P := permute(n): f := sort(add(t^st(P[i]), i = 1 .. factorial(n))): subs(t = 1, diff(f, t)); # program yields a(n) for the specified n - Emeric Deutsch, Aug 13 2009
# second Maple program:
b:= proc(s) option remember; (n-> `if`(n=0, 1, add((p-> add(
      coeff(p, x, i)*x^max(i, abs(n-j)), i=0..degree(p)))(
        b(s minus {j})), j=s)))(nops(s))
    end:
a:= n-> (p-> add(coeff(p, x, i)*i, i=1..n-1))(b({$1..n})):
seq(a(n), n=1..15);  # Alois P. Heinz, Jan 21 2019

b[s_] := b[s] = Function[n, If[n == 0, 1, Sum[Function[p, Sum[Coefficient[p, x, i] x^Max[i, Abs[n-j]], {i, 0, Exponent[p, x]}]][b[s ~Complement~ {j}]], {j, s}]]][Length[s]];
a[n_] := Function[p, Sum[Coefficient[p, x, i] i, {i, 1, n-1}]][b[Range[n]]];
Array[a, 15] (* Jean-François Alcover, Nov 02 2020, after Alois P. Heinz *)

Corrected by Vladeta Jovovic, Jun 07 2007
a(10) from Emeric Deutsch, Aug 13 2009
a(11)-a(14) from Donovan Johnson, Sep 24 2010
a(15) from Alois P. Heinz, Sep 29 2011
a(16)-a(21) from Alois P. Heinz, Jan 21 2019
a(22) from Alois P. Heinz, Jan 28 2019

A323798 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 2.

Original entry on oeis.org

0, 3, 9, 23, 60, 151, 366, 877, 2088, 4937, 11621, 27285, 63944, 149652, 349924, 817712, 1910027, 4460139, 10412815, 24306706, 56733689, 132411638, 309022917, 721175422, 1682988807, 3927486177, 9165229371, 21387927668, 49910484308, 116469784820, 271790117108

Offset: 2

Alois P. Heinz, Jan 28 2019

			a(3) = 3: 231, 312, 321.
a(4) = 9: 1342, 1423, 1432, 2314, 2413, 3124, 3142, 3214, 3412.
a(5) = 23: 12453, 12534, 12543, 13425, 13524, 14235, 14253, 14325, 14523, 21453, 21534, 21543, 23145, 23154, 24135, 24153, 31245, 31254, 31425, 31524, 32145, 32154, 34125.

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

Column k=2 of A130152.

G.f.: x^3*(x^2-3)/((x^2+x-1)*(x^5-2*x^3-2*x+1)).

A323799 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 3.

Original entry on oeis.org

0, 10, 47, 157, 503, 1669, 5472, 17531, 55135, 172134, 535510, 1660795, 5133470, 15826173, 48706210, 149721544, 459820058, 1411142937, 4328181110, 13269541967, 40669595890, 124617708274, 381776661185, 1169438884559, 3581781480980, 10969462410857, 33592685042253

Offset: 3

Alois P. Heinz, Jan 28 2019

			a(4) = 10: 2341, 2431, 3241, 3421, 4123, 4132, 4213, 4231, 4312, 4321.

Alois P. Heinz, Table of n, a(n) for n = 3..1000
Index entries for linear recurrences with constant coefficients, signature (4,-2,-2,6,-17,-16,-30,6,32,48,12,-16,-16,-9,2,-2,-2,2,1).

Column k=3 of A130152.

Cf. A002524, A002526.

G.f.: x^4 *(x^11+x^10-3*x^9+x^8+4*x^7-4*x^6-4*x^5-5*x^4+11*x^3+11*x^2-7*x-10) / ((x-1) *(x^5 -2*x^3 -2*x+1) *(x^13 +3*x^12 +3*x^11 +5*x^10 +9*x^9 +7*x^8 -3*x^7 -19*x^6 -21*x^5 -13*x^4 -3*x^3 -3*x^2-x+1)).

a(n) = A002526(n) - A002524(n).

A323800 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 4.

Original entry on oeis.org

0, 42, 274, 1227, 4833, 18827, 75693, 304900, 1212960, 4753020, 18410363, 70943107, 272701262, 1046410914, 4007815161, 15319362279, 58456445860, 222775782355, 848216866767, 3227396592600, 12273205919568, 46650941505906, 177252609519698, 673266690295879

Offset: 4

Alois P. Heinz, Jan 28 2019

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

Column k=4 of A130152.

Cf. A002526, A072856.

a(n) = A072856(n) - A002526(n).

A323801 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 5.

Original entry on oeis.org

0, 216, 1818, 10402, 50879, 234061, 1076807, 5090497, 24239396, 114890044, 539033760, 2502282836, 11522663348, 52848995167, 241925339959, 1106164932006, 5052307570906, 23047344846397, 104994467312301, 477733956914534, 2171607914492408, 9864023776496558

Offset: 5

Alois P. Heinz, Jan 28 2019

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

Column k=5 of A130152.

Cf. A072856, A154654.

a(n) = A154654(n) - A072856(n).

A323802 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 6.

Original entry on oeis.org

0, 1320, 13656, 96090, 569602, 3111243, 16447329, 87358763, 475067757, 2607565996, 14310288148, 78087401424, 422646322560, 2269565277936, 12114270563852, 64454693890844, 342374934748155, 1817028234672099, 9636622425425550, 51069856507725138, 270408018010461065

Offset: 6

Alois P. Heinz, Jan 28 2019

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

Column k=6 of A130152.

Cf. A154654, A154655.

a(n) = A154655(n) - A154654(n).

A323803 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 7.

Original entry on oeis.org

0, 9360, 115080, 966456, 6791994, 43414690, 264609407, 1583571277, 9541763303, 58695274369, 364677611732, 2271214783228, 14108312731920, 87159560106240, 534932437294080, 3263015911353024, 19810718453429904, 119955619407015668, 725303963303861844

Offset: 7

Alois P. Heinz, Jan 28 2019

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

Column k=7 of A130152.

Cf. A154655, A154656.

a(n) = A154656(n) - A154655(n).

A323804 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 8.

Original entry on oeis.org

0, 75600, 1077840, 10553640, 86272536, 636428922, 4429638754, 29936160747, 200258110593, 1350025656107, 9269884625133, 64294692046060, 447678000251572, 3115603246683600, 21610322604575616, 149157054284148864, 1023951079104952320, 6994818732341176704

Offset: 8

Alois P. Heinz, Jan 28 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 8..800

Column k=8 of A130152.

Cf. A154656, A154657.

a(n) = A154657(n) - A154656(n).

cp's OEIS Frontend

A306209 Number A(n,k) of permutations of [n] within distance k of a fixed permutation; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A299789 Number T(n,k) of permutations p of [n] such that min_{j=1..n} |p(j)-j| = k; triangle T(n,k), n >= 0, 0 <= k <= floor(n/2), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A130153 For each permutation p of {1,2,...,n} define maxabsjump(p) = max(|p(i) - i|, 1<=i<=n); a(n) is the sum of maxabsjumps of all p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A323798 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A323799 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A323800 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 4.

Views

Author

Keywords

Links

Crossrefs

Formula

A323801 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 5.

Views

Author

Keywords

Links

Crossrefs

Formula

A323802 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 6.

Views

Author

Keywords

Links

Crossrefs

Formula

A323803 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 7.

Views

Author

Keywords

Links

Crossrefs

Formula

A323804 Number of permutations p of [n] such that max_{j=1..n} |p(j)-j| = 8.