login
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.
7
1, 1, 1, 4, 4, 3, 15, 19, 15, 10, 76, 99, 86, 67, 42, 455, 603, 544, 455, 358, 216, 3186, 4248, 3934, 3486, 2921, 2250, 1320, 25487, 34115, 32079, 29296, 25487, 21514, 16296, 9360, 229384, 307875, 292509, 272064, 245806, 214551, 179058, 133800, 75600
OFFSET
1,4
COMMENTS
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.
LINKS
Wikipedia, Permutation
FORMULA
T(n,k) = n! - A306512(n,k).
T(2n,n) = T(2n,0) = A002467(2n) = (2n)! - A306535(n).
EXAMPLE
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].
Triangle T(n,k) begins:
1;
1, 1;
4, 4, 3;
15, 19, 15, 10;
76, 99, 86, 67, 42;
455, 603, 544, 455, 358, 216;
3186, 4248, 3934, 3486, 2921, 2250, 1320;
25487, 34115, 32079, 29296, 25487, 21514, 16296, 9360;
...
MAPLE
b:= proc(s, d) option remember; (n-> `if`(n=0, add(x^j, j=d),
add(b(s minus {i}, d union {abs(n-i)}), i=s)))(nops(s))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n-1))(b({$1..n}, {})):
seq(T(n), n=1..9);
# second Maple program:
T:= proc(n, k) option remember; n!-LinearAlgebra[Permanent](
Matrix(n, (i, j)-> `if`(abs(i-j)=k, 0, 1)))
end:
seq(seq(T(n, k), k=0..n-1), n=1..9);
MATHEMATICA
T[n_, k_] := n!-Permanent[Table[If[Abs[i-j]==k, 0, 1], {i, 1, n}, {j, 1, n} ]];
Table[T[n, k], {n, 1, 9}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, May 01 2019, from 2nd Maple program *)
CROSSREFS
Columns k=0-3 give: A002467, A306511, A306524, A324366.
T(n+2,n+1) gives A007680 (for n>=0).
T(2n,n) gives A306675.
Sequence in context: A345294 A233581 A193628 * A241056 A212618 A066602
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Feb 20 2019
STATUS
approved