|
|
A213910
|
|
Irregular triangle read by rows: T(n,k) is the number of involutions of length n that have exactly k inversions; n>=0, 0<=k<=binomial(n,2).
|
|
2
|
|
|
1, 1, 1, 1, 1, 2, 0, 1, 1, 3, 1, 2, 1, 1, 1, 1, 4, 3, 3, 4, 2, 4, 1, 3, 0, 1, 1, 5, 6, 5, 9, 5, 10, 5, 9, 4, 7, 3, 3, 2, 1, 1, 1, 6, 10, 9, 16, 13, 19, 17, 19, 19, 17, 19, 13, 17, 7, 13, 3, 8, 1, 4, 0, 1, 1, 7, 15, 16, 26, 29, 34, 43, 39, 54, 41, 61, 40, 62, 36, 58, 28, 47, 21, 34, 15, 21, 10, 11, 6, 4, 3, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = T(n-1,k) + Sum_{j=1..n-1} T(n-2,k-2*(n-j)+1) for n>=0, k>0; T(n,k) = 0 for n<0 or k<0; T(n,0) = 1 for n>=0. - Alois P. Heinz, Mar 07 2013
|
|
EXAMPLE
|
T(4,3) = 2 because we have: (3,2,1,4), (1,4,3,2).
Triangle T(n,k) begins:
1;
1;
1, 1;
1, 2, 0, 1;
1, 3, 1, 2, 1, 1, 1;
1, 4, 3, 3, 4, 2, 4, 1, 3, 0, 1;
1, 5, 6, 5, 9, 5, 10, 5, 9, 4, 7, 3, 3, 2, 1, 1;
...
|
|
MAPLE
|
T:= proc(n) option remember; local f, g, j; if n<2 then 1 else
f, g:= [T(n-1)], [T(n-2)]; for j to 2*n-3 by 2 do
f:= zip((x, y)->x+y, f, [0$j, g[]], 0) od; f[] fi
end:
|
|
MATHEMATICA
|
Needs["Combinatorica`"];
Table[Distribution[Map[Inversions, Involutions[n]], Range[0, Binomial[n, 2]]], {n, 0, 9}]//Flatten
(* Second program: *)
zip[f_, x_List, y_List, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]];
T[n_] := T[n] = Module[{f, g, j}, If[n < 2, Return@{1}, f = T[n-1]; g = T[n-2]; For[j = 1, j <= 2*n - 3, j += 2, f = zip[Plus, f, Join[Table[0, {j}], g], 0]]]; f];
|
|
CROSSREFS
|
Cf. A008302 (permutations of [n] with k inversions).
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|