A306461 Number T(n,k) of occurrences of k in a (signed) displacement set of a permutation of [n]; triangle T(n,k), n>=1, 1-n<=k<=n-1, read by rows.

1, 1, 1, 1, 2, 3, 4, 3, 2, 6, 10, 13, 15, 13, 10, 6, 24, 42, 56, 67, 76, 67, 56, 42, 24, 120, 216, 294, 358, 411, 455, 411, 358, 294, 216, 120, 720, 1320, 1824, 2250, 2612, 2921, 3186, 2921, 2612, 2250, 1824, 1320, 720, 5040, 9360, 13080, 16296, 19086, 21514, 23633, 25487, 23633, 21514, 19086, 16296, 13080, 9360, 5040

Offset

1,5

Links

Alois P. Heinz, Rows n = 1..142, flattened

Wikipedia, Permutation

Formula

T(n,k) = T(n,-k).

T(n,k) = - Sum_{j=1..n} (-1)^j * binomial(n-|k|,j) * (n-j)!.

T(n,k) = |k|! * (n-|k|)! [x^(n-|k|)] (1-exp(-x))/(1-x)^(|k|+1).

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

T(n,k) = |k|! * A306234(n,k).

Example

The 6 permutations p of [3]: 123, 132, 213, 231, 312, 321 have (signed) displacement sets {p(i)-i, i=1..3}: {0}, {-1,0,1}, {-1,0,1}, {-2,1}, {-1,2}, {-2,0,2}, respectively. Numbers -2 and 2 occur twice, -1 and 1 occur thrice, and 0 occurs four times. So row n=3 is [2, 3, 4, 3, 2].
Triangle T(n,k) begins:
  :                             1                           ;
  :                        1,   1,   1                      ;
  :                   2,   3,   4,   3,   2                 ;
  :              6,  10,  13,  15,  13,  10,   6            ;
  :        24,  42,  56,  67,  76,  67,  56,  42,  24       ;
  :  120, 216, 294, 358, 411, 455, 411, 358, 294, 216, 120  ;

Maple

b:= proc(s, d) option remember; (n-> `if`(n=0, add(x^j, j=d),
      add(b(s minus {i}, d union {n-i}), i=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1-n..n-1))(b({$1..n}, {})):
seq(T(n), n=1..8);
# second Maple program:
T:= (n, k)-> -add((-1)^j*binomial(n-abs(k), j)*(n-j)!, j=1..n):
seq(seq(T(n, k), k=1-n..n-1), n=1..9);

Mathematica

T[n_, k_] := -Sum[(-1)^j Binomial[n-Abs[k], j] (n-j)!, {j, 1, n}];
Table[Table[T[n, k], {k, 1-n, n-1}], {n, 1, 9}] // Flatten (* Jean-François Alcover, Feb 20 2021, after Alois P. Heinz *)

Crossrefs

Columns k=0-1 give: A002467, A180191.

Row sums give A306455.

T(n+1,n) gives A000142.

T(n+2,n) gives A007680.

Cf. A000142, A061018 (left half of this triangle), A306234, A306506, A324225.

Sequence in context: A251102 A111880 A348599 * A101497 A274007 A065870

Adjacent sequences: A306458 A306459 A306460 * A306462 A306463 A306464

Keyword

nonn,tabf

Author

Alois P. Heinz, Feb 17 2019

Status

approved