login
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
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
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
Sequence in context: A293301 A218453 A324563 * A200893 A294583 A283675
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Apr 18 2011
STATUS
approved