

A186372


Triangle read by rows: T(n,k) is the number of permutations p of [n] such that the number of inversions of the word formed by the leading entries of the blocks of p is k. A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67; their leading entries are 5,4,1, and 6 and the word 5416 has 3 inversions.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

Row n has 1+n(n1)/2 entries.
Sum of entries in row n is n!.
T(n,0)=1.
T(n,1)=binom(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)=binom(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), 2738.


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 (* JeanFrançois Alcover, May 20 2011 *)


CROSSREFS

Sequence in context: A293301 A218453 A324563 * A200893 A294583 A283675
Adjacent sequences: A186369 A186370 A186371 * A186373 A186374 A186375


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Apr 18 2011


STATUS

approved



