|
%I #30 Aug 24 2021 06:11:12
%S 0,1,3,14,73,454,3253,26480,241505,2440538,27075301,327197452,
%T 4278799105,60205974230,907025841317,14567520651224,248474458923073,
%U 4485765986251570,85454391074596165,1713134893536617348,36052727133118151201,794697884305583064302
%N Total number of covered falling diagonals in all n X n permutation matrices.
%C A covered diagonal in a permutation matrix contains at least one 1.
%C Alternatively: Total number of covered raising diagonals in all n X n permutation matrices.
%C Also one half of the total number of all covered diagonals in all n X n permutation matrices.
%C Sum over all permutations p of [n] of the cardinality of the (signed) displacement set {p(i)-i, i=1..n}.
%C Alternatively: Sum over all permutations p of [n] of the cardinality of the set {p(i)+i, i=1..n}.
%H Alois P. Heinz, <a href="/A306455/b306455.txt">Table of n, a(n) for n = 0..450</a>
%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 E.g.f.: (exp(-x)*(x+1)+x-1)/(x-1)^2.
%F a(n) = ((2*n^2-5*n+1)*a(n-1) - (n-1)*(n^2-4*n+2)*a(n-2) - (n-2)*(n-1)^2*a(n-3)) / (n-2) for n > 2, a(n) = n*(n+1)/2 for n < 3.
%F a(n) = Sum_{k=1..n} k * A125182(n,k).
%F a(n) = A259834(n+2) - n!.
%F a(n) = Sum_{k=1-n..n-1} A306461(n,k).
%F a(n) = Sum_{k=1-n..n-1} |k|! * A306234(n,k).
%F a(n) mod 2 = 1 - (n mod 2) = A059841(n) for n >= 2.
%e 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}, representing the indices of covered falling diagonals 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, the sum of the set cardinalities gives a(3) = 1 + 3 + 3 + 2 + 2 + 3 = 14.
%p a:= proc(n) option remember; `if`(n<3, n*(n+1)/2,
%p ((2*n^2-5*n+1)*a(n-1)-(n-1)*(n^2-4*n+2)*a(n-2)
%p -(n-2)*(n-1)^2*a(n-3))/(n-2))
%p end:
%p seq(a(n), n=0..23);
%t a[n_] := a[n] = If[n<3, n(n+1)/2, ((2n^2-5n+1) a[n-1] -
%t (n-1)(n^2-4n+2) a[n-2] - (n-2)(n-1)^2 a[n-3])/(n-2)];
%t a /@ Range[0, 23] (* _Jean-François Alcover_, Aug 24 2021, after _Alois P. Heinz_ *)
%Y Cf. A000142, A059841, A125182, A259834, A306234, A306461.
%K nonn
%O 0,3
%A _Alois P. Heinz_, Feb 16 2019
| 