|
%I #40 Dec 05 2023 08:31:51
%S 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,
%T 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,
%U 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
%N 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).
%H Alois P. Heinz, <a href="/A213910/b213910.txt">Rows n = 0..40, flattened</a>
%F Sum_{k>=0} T(n,k)*k = A211606(n).
%F 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
%e T(4,3) = 2 because we have: (3,2,1,4), (1,4,3,2).
%e Triangle T(n,k) begins:
%e 1;
%e 1;
%e 1, 1;
%e 1, 2, 0, 1;
%e 1, 3, 1, 2, 1, 1, 1;
%e 1, 4, 3, 3, 4, 2, 4, 1, 3, 0, 1;
%e 1, 5, 6, 5, 9, 5, 10, 5, 9, 4, 7, 3, 3, 2, 1, 1;
%e ...
%p T:= proc(n) option remember; local f, g, j; if n<2 then 1 else
%p f, g:= [T(n-1)], [T(n-2)]; for j to 2*n-3 by 2 do
%p f:= zip((x, y)->x+y, f, [0$j, g[]], 0) od; f[] fi
%p end:
%p seq(T(n), n=0..10); # _Alois P. Heinz_, Mar 05 2013
%t Needs["Combinatorica`"];
%t Table[Distribution[Map[Inversions,Involutions[n]],Range[0,Binomial[n,2]]],{n,0,9}]//Flatten
%t (* Second program: *)
%t zip[f_, x_List, y_List, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]];
%t 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];
%t Table[T[n], {n, 0, 10}] // Flatten (* _Jean-François Alcover_, Dec 04 2023, after _Alois P. Heinz_ *)
%Y Cf. A008302 (permutations of [n] with k inversions).
%Y Cf. A000085 (row sums), A211606, A214086 (diagonal).
%K nonn,tabf
%O 0,6
%A _Geoffrey Critzer_, Mar 04 2013
|
