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

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

Offset: 0

Author

Geoffrey Critzer, Mar 04 2013

Keywords

• nonn
• tabf

Examples

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

Links

• Alois P. Heinz, Rows n = 0..40, flattened

Crossrefs

Cf. A008302 (permutations of [n] with k inversions).

Cf. A000085 (row sums), A211606, A214086 (diagonal).

Programs

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:
seq(T(n), n=0..10);  # Alois P. Heinz, Mar 05 2013

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];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 04 2023, after Alois P. Heinz *)

Formula

Sum_{k>=0} T(n,k)*k = A211606(n).

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