A324225 - OEIS

%I #44 Apr 25 2024 10:42:52

%S 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,

%T 240,360,480,600,720,600,480,360,240,120,720,1440,2160,2880,3600,4320,

%U 5040,4320,3600,2880,2160,1440,720,5040,10080,15120,20160,25200,30240,35280,40320,35280,30240,25200,20160,15120,10080,5040

%N 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.

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

%H Alois P. Heinz, <a href="/A324225/b324225.txt">Rows n = 1..100, flattened</a>

%H Nadir Samos Sáenz de Buruaga, Rafał Bistroń, Marcin Rudziński, Rodrigo Miguel Chinita Pereira, Karol Życzkowski, and Pedro Ribeiro, <a href="https://arxiv.org/abs/2404.11444">Fidelity decay and error accumulation in quantum volume circuits</a>, arXiv:2404.11444 [quant-ph], 2024. See p. 18.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_matrix">Permutation matrix</a>

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

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

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

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

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

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

%e 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

%e   [1    ]  [1    ]  [  1  ]  [  1  ]  [    1]  [    1]

%e   [  1  ]  [    1]  [1    ]  [    1]  [1    ]  [  1  ]

%e   [    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].

%e Triangle T(n,k) begins:

%e   :                             1                           ;

%e   :                        1,   2,   1                      ;

%e   :                   2,   4,   6,   4,   2                 ;

%e   :              6,  12,  18,  24,  18,  12,   6            ;

%e   :        24,  48,  72,  96, 120,  96,  72,  48,  24       ;

%e   :  120, 240, 360, 480, 600, 720, 600, 480, 360, 240, 120  ;

%p b:= proc(s, c) option remember; (n-> `if`(n=0, c,

%p       add(b(s minus {i}, c+x^(n-i)), i=s)))(nops(s))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1-n..n-1))(b({$1..n}, 0)):

%p seq(T(n), n=1..8);

%p # second Maple program:

%p egf:= k-> (t-> x^t/t*hypergeom([2, t], [t+1], x))(abs(k)+1):

%p T:= (n, k)-> n! * coeff(series(egf(k), x, n+1), x, n):

%p seq(seq(T(n, k), k=1-n..n-1), n=1..8);

%p # third Maple program:

%p T:= (n, k)-> (t-> `if`(t<n, (n-t)*(n-1)!, 0))(abs(k)):

%p seq(seq(T(n, k), k=1-n..n-1), n=1..8);

%t T[n_, k_] := With[{t = Abs[k]}, If[t<n, (n-t)(n-1)!, 0]];

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

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

%Y Row sums give A001563.

%Y T(n+1,n) gives A000142.

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

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

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

%Y Cf. A001710.

%K nonn,look,tabf

%O 1,3

%A _Alois P. Heinz_, Feb 18 2019