login
A248092
Triangle read by rows: T(n,k) is the largest inversion number of the n-permutations having k cycles.
0
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
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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Oct 29 2014
STATUS
approved