The estimate of the number of permutationally-ordered sets

M. I. Kharitonov

Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 3 (2015), pp. 24-28

Résumé

It is proved that the number of $n$-element permutationally-ordered sets with the maximal antichain of length not exceeding $k$ is not greater than $\min\biggl\{{k^{2n}\over (k!)^2}, {(n-k+1)^{2n}\over ((n-k)!)^2}\biggr\}$. It is also proved that the number of permutations $\xi_k(n)$ of the numbers $\{1,\dots,n\}$ with the maximal decreasing subsequence of length not exceeding $k$ satisfies the inequality ${k^{2n}\over ((k-1)!)^2}.$ A review of papers focused on bijections and relations between pairs of linear orders, pairs of Young diagrams, two-dimensional arrays of positive integers, and matrices with integer elements is presented.