A324225 Total number T(n,k) of 1's in falling diagonals with index k in all n X n permutation matrices; triangle T(n,k), n>=1, 1-n<=k<=n-1, read by rows.

1, 1, 2, 1, 2, 4, 6, 4, 2, 6, 12, 18, 24, 18, 12, 6, 24, 48, 72, 96, 120, 96, 72, 48, 24, 120, 240, 360, 480, 600, 720, 600, 480, 360, 240, 120, 720, 1440, 2160, 2880, 3600, 4320, 5040, 4320, 3600, 2880, 2160, 1440, 720, 5040, 10080, 15120, 20160, 25200, 30240, 35280, 40320, 35280, 30240, 25200, 20160, 15120, 10080, 5040

Offset

1,3

Comments

T(n,k) is the number of occurrences of k in all (signed) displacement lists [p(i)-i, i=1..n] of permutations p of [n].

Links

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

Nadir Samos Sáenz de Buruaga, Rafał Bistroń, Marcin Rudziński, Rodrigo Miguel Chinita Pereira, Karol Życzkowski, and Pedro Ribeiro, Fidelity decay and error accumulation in quantum volume circuits, arXiv:2404.11444 [quant-ph], 2024. See p. 18.

Wikipedia, Permutation

Wikipedia, Permutation matrix

Formula

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

T(n,k) = (n-t)*(n-1)! if t < n with t = |k|, T(n,k) = 0 otherwise.

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

E.g.f. of column k: x^t/t * hypergeom([2, t], [t+1], x) with t = |k|+1.

|T(n,k)-T(n,k-1)| = (n-1)! for k = 1-n..n.

Sum_{k=0..n-1} T(n,k) = A001710(n+1).

Example

The 6 permutations p of [3]: 123, 132, 213, 231, 312, 321 have (signed) displacement lists [p(i)-i, i=1..3]: [0,0,0], [0,1,-1], [1,-1,0], [1,1,-2], [2,-1,-1], [2,0,-2], representing the indices of falling diagonals of 1's in the permutation matrices
  [1    ]  [1    ]  [  1  ]  [  1  ]  [    1]  [    1]
  [  1  ]  [    1]  [1    ]  [    1]  [1    ]  [  1  ]
  [    1]  [  1  ]  [    1]  [1    ]  [  1  ]  [1    ] , respectively. Indices -2 and 2 occur twice, -1 and 1 occur four times, and 0 occurs six times. So row n=3 is [2, 4, 6, 4, 2].
Triangle T(n,k) begins:
  :                             1                           ;
  :                        1,   2,   1                      ;
  :                   2,   4,   6,   4,   2                 ;
  :              6,  12,  18,  24,  18,  12,   6            ;
  :        24,  48,  72,  96, 120,  96,  72,  48,  24       ;
  :  120, 240, 360, 480, 600, 720, 600, 480, 360, 240, 120  ;

Maple

b:= proc(s, c) option remember; (n-> `if`(n=0, c,
      add(b(s minus {i}, c+x^(n-i)), i=s)))(nops(s))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1-n..n-1))(b({$1..n}, 0)):
seq(T(n), n=1..8);
# second Maple program:
egf:= k-> (t-> x^t/t*hypergeom([2, t], [t+1], x))(abs(k)+1):
T:= (n, k)-> n! * coeff(series(egf(k), x, n+1), x, n):
seq(seq(T(n, k), k=1-n..n-1), n=1..8);
# third Maple program:
T:= (n, k)-> (t-> `if`(t<n, (n-t)*(n-1)!, 0))(abs(k)):
seq(seq(T(n, k), k=1-n..n-1), n=1..8);

Mathematica

T[n_, k_] := With[{t = Abs[k]}, If[t<n, (n-t)(n-1)!, 0]];
Table[Table[T[n, k], {k, 1-n, n-1}], {n, 1, 8}] // Flatten (* Jean-François Alcover, Mar 25 2021, after 3rd Maple program *)

Crossrefs

Columns k=0-6 give (offsets may differ): A000142, A001563, A062119, A052571, A052520, A282822, A052521.

Row sums give A001563.

T(n+1,n) gives A000142.

T(n+1,n-1) gives A052849.

T(n+1,n-2) gives A052560 for n>1.

Cf. A152883 (right half of this triangle without center column), A162608 (left half of this triangle), A306461, A324224.

Cf. A001710.

Sequence in context: A179787 A358918 A368058 * A214739 A296159 A283334

Adjacent sequences: A324222 A324223 A324224 * A324226 A324227 A324228

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Feb 18 2019

Status

approved