cp's OEIS Frontend

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

%I A306506 #45 May 03 2021 07:16:49
%S A306506 1,1,1,4,4,3,15,19,15,10,76,99,86,67,42,455,603,544,455,358,216,3186,
%T A306506 4248,3934,3486,2921,2250,1320,25487,34115,32079,29296,25487,21514,
%U A306506 16296,9360,229384,307875,292509,272064,245806,214551,179058,133800,75600
%N A306506 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 A306506 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 A306506 Alois P. Heinz, <a href="/A306506/b306506.txt">Rows n = 1..35, flattened</a>
%H A306506 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation">Permutation</a>
%F A306506 T(n,k) = n! - A306512(n,k).
%F A306506 T(2n,n) = T(2n,0) = A002467(2n) = (2n)! - A306535(n).
%e A306506 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 A306506 Triangle T(n,k) begins:
%e A306506       1;
%e A306506       1,     1;
%e A306506       4,     4,     3;
%e A306506      15,    19,    15,    10;
%e A306506      76,    99,    86,    67,    42;
%e A306506     455,   603,   544,   455,   358,   216;
%e A306506    3186,  4248,  3934,  3486,  2921,  2250,  1320;
%e A306506   25487, 34115, 32079, 29296, 25487, 21514, 16296, 9360;
%e A306506   ...
%p A306506 b:= proc(s, d) option remember; (n-> `if`(n=0, add(x^j, j=d),
%p A306506       add(b(s minus {i}, d union {abs(n-i)}), i=s)))(nops(s))
%p A306506     end:
%p A306506 T:= n-> (p-> seq(coeff(p, x, i), i=0..n-1))(b({$1..n}, {})):
%p A306506 seq(T(n), n=1..9);
%p A306506 # second Maple program:
%p A306506 T:= proc(n, k) option remember; n!-LinearAlgebra[Permanent](
%p A306506       Matrix(n, (i, j)-> `if`(abs(i-j)=k, 0, 1)))
%p A306506     end:
%p A306506 seq(seq(T(n, k), k=0..n-1), n=1..9);
%t A306506 T[n_, k_] := n!-Permanent[Table[If[Abs[i-j]==k, 0, 1], {i, 1, n}, {j, 1, n} ]];
%t A306506 Table[T[n, k], {n, 1, 9}, {k, 0, n-1}] // Flatten (* _Jean-François Alcover_, May 01 2019, from 2nd Maple program *)
%Y A306506 Columns k=0-3 give: A002467, A306511, A306524, A324366.
%Y A306506 T(n+2,n+1) gives A007680 (for n>=0).
%Y A306506 T(2n,n) gives A306675.
%Y A306506 Cf. A000142, A010050, A306461, A306512, A306535.
%K A306506 nonn,tabl
%O A306506 1,4
%A A306506 _Alois P. Heinz_, Feb 20 2019