Мажорирование множеств

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

Определение

Пусть $X=\{x_1,x_2,\dots ,x_n\},Y=\{y_1,y_2,\dots ,y_n\}$, где $x_1⩾x_2⩾\dots ⩾x_n,y_1⩾y_2⩾\dots ⩾y_n$.

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

для любого $k=1\dots n-1$ , $\sum _{i=1}^k{x}_i⩾\sum _{i=1}^k{y}_i$; и $\sum _{i=1}^n{x}_i=\sum _{i=1}^n{y}_i$

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

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

Примеры

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

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

Вообще, для любых $x_1⩾x_2⩾\dots ⩾x_n$ выполняется следующее:

$\{x_1+x_2+\dots +x_n,\underset{n-1}{\underbrace{0,0,\dots ,0}}\}\succ \{x_1,x_2,\dots ,x_n\}\succ \{\underset{n}{\underbrace{\frac{x_1+\dots +x_n}{n},\frac{x_1+\dots +x_n}{n},\dots ;\frac{x_1+\dots +x_n}{n}}}\}$

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

Шаблон:Main Пусть $F_1$ — симметризация одночлена $x_1^{{\alpha }_1}\dots x_n^{{\alpha }_n}$, $F_2$ — симметризация одночлена $x_1^{{\beta }_1}\dots x_n^{{\beta }_n}$. Если $\{{\alpha }_1;\dots ;{\alpha }_n\}\succ \{{\beta }_1;\dots ;{\beta }_n\}$, то при всех неотрицательных $x_1,\dots ,x_n$ выполняется неравенство $F_1({\alpha }_1,\dots {\alpha }_n)⩾F_2({\beta }_1,\dots {\beta }_n)$.