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

Author

Alois P. Heinz, Feb 18 2019

Keywords

• nonn
• look
• tabf

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

Examples

			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  ;
		

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

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.

Programs

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
				

Mathematica

T[n_, k_] := With[{t = Abs[k]}, If[tJean-François Alcover, Mar 25 2021, after 3rd Maple program *)

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