login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)=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), 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 04:40 EDT 2019. Contains 328211 sequences. (Running on oeis4.)