|
|
A320582
|
|
Number T(n,k) of permutations p of [n] such that |{ j : |p(j)-j| = 1 }| = k; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.
|
|
5
|
|
|
1, 1, 0, 1, 0, 1, 2, 0, 4, 0, 5, 6, 10, 2, 1, 21, 36, 42, 12, 9, 0, 117, 226, 219, 104, 47, 6, 1, 792, 1568, 1472, 800, 328, 64, 16, 0, 6205, 12360, 11596, 6652, 2658, 688, 148, 12, 1, 55005, 109760, 103600, 60840, 24770, 7120, 1560, 200, 25, 0, 543597, 1085560, 1030649, 614420, 255830, 77732, 17750, 2876, 365, 20, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,7
|
|
LINKS
|
|
|
FORMULA
|
Sum_{k=1..n} k * T(n,k) = A052582(n-1) for n > 0.
Sum_{k=0..n} (k+1) * T(n,k) = A082033(n-1) for n > 0.
|
|
EXAMPLE
|
T(4,0) = 5: 1234, 1432, 3214, 3412, 4231.
T(4,1) = 6: 2431, 3241, 3421, 4132, 4213, 4312.
T(4,2) = 10: 1243, 1324, 1342, 1423, 2134, 2314, 2413, 3124, 3142, 4321.
T(4,3) = 2: 2341, 4123.
T(4,4) = 1: 2143.
Triangle T(n,k) begins:
1;
1, 0;
1, 0, 1;
2, 0, 4, 0;
5, 6, 10, 2, 1;
21, 36, 42, 12, 9, 0;
117, 226, 219, 104, 47, 6, 1;
792, 1568, 1472, 800, 328, 64, 16, 0;
6205, 12360, 11596, 6652, 2658, 688, 148, 12, 1;
55005, 109760, 103600, 60840, 24770, 7120, 1560, 200, 25, 0;
...
|
|
MAPLE
|
b:= proc(s) option remember; expand((n-> `if`(n=0, 1, add(
`if`(abs(n-j)=1, x, 1)*b(s minus {j}), j=s)))(nops(s)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b({$1..n})):
seq(T(n), n=0..12);
|
|
MATHEMATICA
|
b[s_] := b[s] = Expand[With[{n = Length[s]}, If[n==0, 1, Sum[
If[Abs[n-j]==1, x, 1]*b[s~Complement~{j}], {j, s}]]]];
T[n_] := PadRight[CoefficientList[b[Range[n]], x], n+1];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|