Estimation of the number of permutationally-ordered sets / M. I. Kharitonov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2015. № 3. P. 24-28 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 125-129].

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\big\{{k^{2n}\over (k!)^2}, {(n-k+1)^{2n}\over ((n-k)!)^2}\big\}. 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.

Key words: combinatorics on words, k-divisibility, Dilworth theorem, multilinear words, multilinear identities, Young diagrams.

№ 3/2015