|
%I #45 May 03 2021 07:16:49
%S 1,1,1,4,4,3,15,19,15,10,76,99,86,67,42,455,603,544,455,358,216,3186,
%T 4248,3934,3486,2921,2250,1320,25487,34115,32079,29296,25487,21514,
%U 16296,9360,229384,307875,292509,272064,245806,214551,179058,133800,75600
%N Number T(n,k) of permutations p of [n] having at least one index i with |p(i)-i| = k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.
%C T(n,k) is defined for n,k>=0. The triangle contains only the terms with k<n. T(n,k) = 0 for k>=n.
%H Alois P. Heinz, <a href="/A306506/b306506.txt">Rows n = 1..35, flattened</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>
%F T(n,k) = n! - A306512(n,k).
%F T(2n,n) = T(2n,0) = A002467(2n) = (2n)! - A306535(n).
%e The 6 permutations p of [3]: 123, 132, 213, 231, 312, 321 have absolute displacement sets {|p(i)-i|, i=1..3}: {0}, {0,1}, {0,1}, {1,2}, {1,2}, {0,2}, respectively. Number 0 occurs four times, 1 occurs four times, and 2 occurs thrice. So row n=3 is [4, 4, 3].
%e Triangle T(n,k) begins:
%e 1;
%e 1, 1;
%e 4, 4, 3;
%e 15, 19, 15, 10;
%e 76, 99, 86, 67, 42;
%e 455, 603, 544, 455, 358, 216;
%e 3186, 4248, 3934, 3486, 2921, 2250, 1320;
%e 25487, 34115, 32079, 29296, 25487, 21514, 16296, 9360;
%e ...
%p b:= proc(s, d) option remember; (n-> `if`(n=0, add(x^j, j=d),
%p add(b(s minus {i}, d union {abs(n-i)}), i=s)))(nops(s))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=0..n-1))(b({$1..n}, {})):
%p seq(T(n), n=1..9);
%p # second Maple program:
%p T:= proc(n, k) option remember; n!-LinearAlgebra[Permanent](
%p Matrix(n, (i, j)-> `if`(abs(i-j)=k, 0, 1)))
%p end:
%p seq(seq(T(n, k), k=0..n-1), n=1..9);
%t T[n_, k_] := n!-Permanent[Table[If[Abs[i-j]==k, 0, 1], {i, 1, n}, {j, 1, n} ]];
%t Table[T[n, k], {n, 1, 9}, {k, 0, n-1}] // Flatten (* _Jean-François Alcover_, May 01 2019, from 2nd Maple program *)
%Y Columns k=0-3 give: A002467, A306511, A306524, A324366.
%Y T(n+2,n+1) gives A007680 (for n>=0).
%Y T(2n,n) gives A306675.
%Y Cf. A000142, A010050, A306461, A306512, A306535.
%K nonn,tabl
%O 1,4
%A _Alois P. Heinz_, Feb 20 2019
|
