OFFSET
0,6
COMMENTS
Row n has 1+n(n-1)/2 entries.
Sum of entries in row n is n!.
T(n,0)=1.
T(n,1)=binomial(n+1,3); select 3 points a,b,c from the n+1 points that delimit the n entries of the identity permutation and interchange the segment between a and b with the segment between b and c. For example, if n=7, then for the selection 123a4b567c we obtain 1235674; the leading entries of its blocks are 1,5, and 4; the word 154 has 1 inversion.
Apparently, T(n,2) = binomial(n+2,6) (proof ?).
See the related concept of "profile" in the Atkinson reference (p. 32).
The entries have been obtained by direct counting (via Maple).
REFERENCES
M. D. Atkinson, Restricted permutations, Discrete Math., 195 (1999), 27-38.
LINKS
Alois P. Heinz, Rows n = 0..11, flattened
EXAMPLE
T(5,2)=7 because we have 13254, 21354, 21435, 21453, 21534, 23154, and 31254; the words formed by the leading entries of their blocks are 13254, 21354, 21435, 2143, 2153, 2154, and 3154, respectivey, each having 2 inversions.
Triangle starts:
1;
1;
1,1;
1,4,0,1;
1,10,1,7,4,0,1;
1,20,7,27,28,8,14,8,6,0,1;
1,35,28,78,118,68,96,89,83,44,36,23,12,8,0,1;
1,56,84,192,388,335,459,550,594,503,462,408,317,275,161,118,70,40,16,10,0,1;
1,84,210,433,1093,1255,1769,2511,3045,3259,3455,3609,3429,3420,2896,2540,2084, 1646,1230,918,606,376,232,125,61,20,12,0,1;
1,120,462,934,2761,3970,5913,9478,12712,15790,18896,22204,24175,26702,27126, 27236,26327,24656,22489,19985,17150,14054,11409,8816,6609,4673,3315,2121,1322, 741,412,196,86,24,14,0,1;
1,165,924,1969,6427,11183,17853,31364,46136,63779,84402,108793,131429,157750, 180191,200307,216385,227243,233550,233913,229477,217954,204133,185895,165640, 143562,122661,101308,81859,64203,49081,36356,26020,17900,11918,7585,4501,2555, 1325,660,283,115,28,16,0,1;
MATHEMATICA
inv[{a_}] = 0; inv[{a_, b_}] = If[a < b, 0, 1]; inv[p_List] := (lp = Length[p]; Count[Table[{p[[i]], p[[j]]}, {i, lp}, {j, i + 1, lp}] // Flatten[#, 1] &, {a_, b_} /; a > b]); t[n_, k_] := t[n, k] = (cnt = 0; w = Array[v, n]; Do[ If[Length[Union[w]] == n, If[inv[ First /@ Split[w, #2 - #1 == 1 &]] == k, cnt++]], Evaluate[Sequence @@ Table[{v[i], n}, {i, n}]]]; cnt); Table[t[n, k], {n, 0, 8}, {k, 0, n (n - 1)/2}] // Flatten (* Jean-François Alcover, May 20 2011 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Apr 18 2011
STATUS
approved