A248092 Triangle read by rows: T(n,k) is the largest inversion number of the n-permutations having k cycles.

0, 1, 0, 2, 3, 0, 5, 6, 5, 0, 8, 9, 10, 7, 0, 13, 14, 15, 14, 9, 0, 18, 19, 20, 21, 18, 11, 0, 25, 26, 27, 28, 27, 22, 13, 0, 32, 33, 34, 35, 36, 33, 26, 15, 0, 41, 42, 43, 44, 45, 44, 39, 30, 17, 0, 50, 51, 52, 53, 54, 55, 52, 45, 34, 19, 0

Offset

1,4

References

M. Bona, Combinatorics of Permutations. 2nd ed., Chapman and Hall/CRC Press, 2012, Boca Raton, FL. pp. 136, 141.

Links

Table of n, a(n) for n=1..66.

P. H. Edelman, On inversions and cycles in permutations, European J. Combinatorics, 8, 1987, 269-279.

Formula

T(n,k) = binomial(n,k) - ceiling(n/2) + k if k <= ceiling(n/2); T(n,k) = binomial(n,2) - binomial(2k - n, 2) if k > ceiling(n/2).

Example

T(4,3)=5; indeed, the 4-permutations with 3 cycles are 1243, 1324, 1432, 2134, 4231, and 3214, having 1, 1, 3, 1, 5, and 3 inversions, respectively.
Triangle starts:
  0;
  1, 0;
  2, 3,  0;
  5, 6,  5, 0;
  8, 9, 10, 7, 0;

Maple

T := proc (n, k) if n < k then 0 elif k <= ceil((1/2)*n) then binomial(n, 2)-ceil((1/2)*n)+k else binomial(n, 2)-binomial(2*k-n, 2) end if end proc: for n to 13 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form

Crossrefs

Sequence in context: A219695 A364575 A267186 * A145105 A140700 A055615

Adjacent sequences: A248089 A248090 A248091 * A248093 A248094 A248095

Keyword

nonn,tabl

Author

Emeric Deutsch, Oct 29 2014

Status

approved