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.

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

Links

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

Formula

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

Example

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

Maple

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

Mathematica

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

Crossrefs

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.

Sequence in context: A185130 A261870 A325516 * A121662 A130042 A285362

Adjacent sequences: A299786 A299787 A299788 * A299790 A299791 A299792

Keyword

nonn,tabf

Author

Alois P. Heinz, Jan 21 2019

Status

approved