|
|
A306461
|
|
Number T(n,k) of occurrences of k in a (signed) displacement set of a permutation of [n]; triangle T(n,k), n>=1, 1-n<=k<=n-1, read by rows.
|
|
6
|
|
|
1, 1, 1, 1, 2, 3, 4, 3, 2, 6, 10, 13, 15, 13, 10, 6, 24, 42, 56, 67, 76, 67, 56, 42, 24, 120, 216, 294, 358, 411, 455, 411, 358, 294, 216, 120, 720, 1320, 1824, 2250, 2612, 2921, 3186, 2921, 2612, 2250, 1824, 1320, 720, 5040, 9360, 13080, 16296, 19086, 21514, 23633, 25487, 23633, 21514, 19086, 16296, 13080, 9360, 5040
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = T(n,-k).
T(n,k) = - Sum_{j=1..n} (-1)^j * binomial(n-|k|,j) * (n-j)!.
T(n,k) = |k|! * (n-|k|)! [x^(n-|k|)] (1-exp(-x))/(1-x)^(|k|+1).
Sum_{k=1-n..n-1} T(n,k) = A306455(n).
|
|
EXAMPLE
|
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}, respectively. Numbers -2 and 2 occur twice, -1 and 1 occur thrice, and 0 occurs four times. So row n=3 is [2, 3, 4, 3, 2].
Triangle T(n,k) begins:
: 1 ;
: 1, 1, 1 ;
: 2, 3, 4, 3, 2 ;
: 6, 10, 13, 15, 13, 10, 6 ;
: 24, 42, 56, 67, 76, 67, 56, 42, 24 ;
: 120, 216, 294, 358, 411, 455, 411, 358, 294, 216, 120 ;
|
|
MAPLE
|
b:= proc(s, d) option remember; (n-> `if`(n=0, add(x^j, j=d),
add(b(s minus {i}, d union {n-i}), i=s)))(nops(s))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=1-n..n-1))(b({$1..n}, {})):
seq(T(n), n=1..8);
# second Maple program:
T:= (n, k)-> -add((-1)^j*binomial(n-abs(k), j)*(n-j)!, j=1..n):
seq(seq(T(n, k), k=1-n..n-1), n=1..9);
|
|
MATHEMATICA
|
T[n_, k_] := -Sum[(-1)^j Binomial[n-Abs[k], j] (n-j)!, {j, 1, n}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|