|
| |
|
|
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(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
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
