Математика
Оценка количества перестановочно-упорядоченных множеств
М. И. Харитонов Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
В работе доказывается, что количество
$n$-элементных перестановочно-упорядоченных множеств с максимальной антицепью длины
$k$ не более $\min\biggl\{{k^{2n}\over (k!)^2}, {(n-k+1)^{2n}\over ((n-k)!)^2}\biggr\}$. Также доказывается, что для количества перестановок
$\xi_k(n)$ чисел от 1 до
$n$ с максимальной убывающей подпоследовательностью длины не больше
$k$ справедливо неравенство
${k^{2n}\over ((k-1)!)^2}.$ Проводится обзор работ, посвященных биекциям и связям между парами линейных порядков, парами диаграмм Юнга, целочисленными двумерными массивами и целочисленными матрицами.
Ключевые слова:
комбинаторика слов,
$k$-разбиваемость, теорема Дилуорса, полилинейные слова, полилинейные тождества, диаграммы Юнга.
УДК:
512.562+
519.1 Поступила в редакцию: 09.12.2013