Мажорирование множеств (Bg'kjnjkfguny buk'yvmf)

Мажорирование — математический термин из теории множеств.

Определение

Пусть $X=\{x_{1},x_{2},\ldots ,x_{n}\},Y=\{y_{1},y_{2},\ldots ,y_{n}\}$ , где $x_{1}\geqslant x_{2}\geqslant \ldots \geqslant x_{n},y_{1}\geqslant y_{2}\geqslant \ldots \geqslant y_{n}$ .

Говорят, что множество $X$ мажори́рует множество $Y$ (обозначается $X\succ Y$ ), если верно следующее:

для любого

k=1\ldots n-1

,

\sum _{i=1}^{k}x_{i}\geqslant \sum _{i=1}^{k}y_{i}

; и

\sum _{i=1}^{n}x_{i}=\sum _{i=1}^{n}y_{i}

Если последнее равенство заменить менее сильным условием $\sum _{i=1}^{n}x_{i}\geqslant \sum _{i=1}^{n}y_{i}$ , то $X$ нестрого мажорирует $Y$ .

Мажоризацию можно обобщить на случай неупорядоченных наборов чисел. Множество $X$ мажорирует множество $Y$ , если невозрастающая перестановка $X$ мажорирует невозрастающую перестановку $Y$ .

Примеры

$\{8,7,1\}\succ \{6,5,5\}$ , так как $8\geqslant 6,\ 8+7\geqslant 6+5,\ 8+7+1=6+5+5$

$\{3,2\}\succ \{3,2\}$ , так как $3\geqslant 3,\ 3+2=3+2$

Вообще, для любых $x_{1}\geqslant x_{2}\geqslant \ldots \geqslant x_{n}$ выполняется следующее:

$\{x_{1}+x_{2}+\ldots +x_{n},\underbrace {0,0,\ldots ,0} _{n-1}\}\succ \{x_{1},x_{2},\ldots ,x_{n}\}\succ \{\underbrace {{\frac {x_{1}+\ldots +x_{n}}{n}},{\frac {x_{1}+\ldots +x_{n}}{n}},\ldots ;{\frac {x_{1}+\ldots +x_{n}}{n}}} _{n}\}$

Неравенство Мюрхеда

Пусть $F_{1}$ — симметризация одночлена $x_{1}^{\alpha _{1}}\ldots x_{n}^{\alpha _{n}}$ , $F_{2}$ — симметризация одночлена $x_{1}^{\beta _{1}}\ldots x_{n}^{\beta _{n}}$ . Если $\{\alpha _{1};\ldots ;\alpha _{n}\}\succ \{\beta _{1};\ldots ;\beta _{n}\}$ , то при всех неотрицательных $x_{1},\dots ,x_{n}$ выполняется неравенство $F_{1}(\alpha _{1},\ldots \alpha _{n})\geqslant F_{2}(\beta _{1},\ldots \beta _{n})$ .