A296050 -id:A296050 - cp's OEIS frontend

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

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

A323671 Number T(n,k) of permutations p of [n] with no fixed points such that |{ j : |p(j)-j| = 1 }| = k; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 2, 0, 1, 2, 3, 2, 1, 4, 12, 14, 8, 6, 0, 29, 68, 82, 54, 25, 6, 1, 206, 496, 546, 376, 170, 48, 12, 0, 1708, 3960, 4349, 2922, 1353, 430, 98, 12, 1, 15702, 35816, 38632, 26048, 12084, 4052, 982, 160, 20, 0, 159737, 358786, 383523, 257552, 120919, 41508, 10647, 1998, 270, 20, 1

Offset: 0

Alois P. Heinz, Jan 23 2019

			T(4,0) = 1: 3412.
T(4,1) = 2: 3421, 4312.
T(4,2) = 3: 2413, 3142, 4321.
T(4,3) = 2: 2341, 4123.
T(4,4) = 1: 2143.
Triangle T(n,k) begins:
      1;
      0,     0;
      0,     0,     1;
      0,     0,     2,     0;
      1,     2,     3,     2,     1;
      4,    12,    14,     8,     6,    0;
     29,    68,    82,    54,    25,    6,   1;
    206,   496,   546,   376,   170,   48,  12,   0;
   1708,  3960,  4349,  2922,  1353,  430,  98,  12,  1;
  15702, 35816, 38632, 26048, 12084, 4052, 982, 160, 20, 0;
  ...

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

Column k=0 gives A001883.
Row sums give A000166.
Main diagonal and lower diagonal give A059841, A110660.
Cf. A296050, A320582.

b:= proc(s) option remember; expand((n-> `if`(n=0, 1, add(
      (t-> `if`(t=0, 0, `if`(t=1, x, 1)*b(s minus {j}))
       )(abs(n-j)), j=s)))(nops(s)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b({$1..n})):
seq(T(n), n=0..12);

b[s_] := b[s] = Expand[Function[n, If[n==0, 1, Sum[Function[t, If[t==0, 0, If[t==1, x, 1]*b[s~Complement~{j}]]][Abs[n-j]], {j, s}]]][Length[s]]];
T[n_] := PadRight[CoefficientList[b[Range[n]], x], n+1];
T /@ Range[0, 12] // Flatten (* Jean-François Alcover, Feb 09 2021, after Alois P. Heinz *)

Sum_{k=1..n} T(n,k) = A296050(n).

cp's OEIS Frontend

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