A152883 -id:A152883 - cp's OEIS frontend

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

Alois P. Heinz, Feb 18 2019

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

			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  ;

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

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.

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

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

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

A213168 a(n) = n!/2 - (n-1)! - n + 2.

Original entry on oeis.org

0, 0, 4, 33, 236, 1795, 15114, 141113, 1451512, 16329591, 199583990, 2634508789, 37362124788, 566658892787, 9153720575986, 156920924159985, 2845499424767984, 54420176498687983, 1094805903679487982, 23112569077678079981, 510909421717094399980

Offset: 2

Olivier Gérard, Nov 02 2012

Row sums of A142706 for k=1..n-1.

Vincenzo Librandi, Table of n, a(n) for n = 2..200

Cf. A001286.
Cf. A142706, A051683, A152883.
Cf. A200748 (considered as a triangular array).

[Factorial(n)/2-Factorial(n-1)-n+2: n in [2..25]]; // Vincenzo Librandi, Sep 09 2016

f:=gfun:-rectoproc({2*(n-3)*a(n) - (2*n^2-6*n+4)*a(n-1)- 2*(n-3)*(n-2)^2, a(2)=0,a(3)=0},a(n),remember): map(f, [$2..22]); # Georg Fischer, Aug 25 2021

Table[n!/2 - (n - 1)! - n + 2, {n, 2, 20}]

A213168(n):=n!/2-(n-1)!-n+2$
makelist(A213168(n),n,2,30); /* Martin Ettl, Nov 03 2012 */

a(n) = A001286(n-1) - n + 2. - Anton Zakharov, Sep 08 2016
D-finite with recurrence: 2*(n-3)*a(n) - (2*n^2-6*n+4)*a(n-1)- 2*(n-3)*(n-2)^2 = 0. - Georg Fischer, Aug 25 2021
E.g.f.: 1/(2-2*x)+log(1-x)+(2-x)*exp(x). - Alois P. Heinz, Aug 25 2021

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula