Transulighed

Permutationsuligheden , eller uligheden om enkelt-monotone sekvenser , eller " trans -ulighed ", angiver, at prikproduktet af to sæt tal er det maksimalt mulige, hvis mængderne er enkelt-monotone (det vil sige, at begge samtidigt ikke er faldende eller samtidig ikke-stigende), og den mindst mulige, hvis mængderne er af modsat monotoni (så er det ene ikke-faldende, og det andet er ikke-tiltagende).

Med andre ord, hvis og , så for en vilkårlig permutation af tal , gælder følgende ulighed: $x_1\leqslant x_2 \leqslant \dots\leqslant x_n$ $y_1\leqslant y_2 \leqslant \dots\leqslant y_n$ $\sigma$ $\{1,2,\dots,n\}$

x_1 y_n + x_2 y_{n-1} + \cdots + x_n y_1 \leqslant x_1 y_{\sigma(1)} + x_2 y_{\sigma(2)} + \cdots + x_n y_{\sigma(n)} \leqslant x_1 y_1 + x_2 y_2 + \cdots + x_n y_n

Især hvis , så uanset bestilling . ${\displaystyle y_{i}=x_{i))$ $x_{1}x_{\sigma (1)}+\dots +x_{n}x_{\sigma (n)}\leq {x_{1}}^{2}+\dots {x_{n }}^{2}$ $x_{1},\dots ,x_{n}$

En konsekvens af permutationsuligheden er Chebyshev-uligheden for summerne .

Bevis

Lad os betegne . Til beviset er det praktisk at omformulere påstanden noget: $V(\sigma )=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)))$

\arg \max \limits _{\sigma \in S_{n}}{V(\sigma )}=\sigma _{0}

Her er sættet af alle mulige permutationer , og er den identiske permutation . $S_{n}$ $\sigma _{0}:\x\mapsto x$

Hovedideen med beviset er, at hvis for nogle , så ved at bytte værdierne af og , vil vi ikke mindske værdien af summen . $\sigma (i)>\sigma (j)$ $i<j$ $\sigma (i)$ $\sigma (j)$ $V(\sigma)$

Overvej den angivne sum for en eller anden permutation og sådan et par . Overvej permutationen dannet fra inversionerne af dette par. ${\displaystyle \sigma \not =\sigma _{0))$ $i,j$ $\sigma$

\sigma ':x\mapsto \left\{{\begin{matrix}\sigma (j),&x=i,\\\sigma (i),&x=j,\\\sigma (x), &x\ikke \i \{{i,j}\}.\end{matrix}}\right.

Per definition,

V(\sigma ')=V(\sigma )-x_{i}y_{\sigma (i)}-x_{j}y_{\sigma (j)}+x_{i}y_{\sigma (j)}+x_{j}y_{\sigma (i)}=V(\sigma )+(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma ( j)})

Ved valg og ordensantagelsen er uligheden sand , således at . $i,j$ $x,y$ $(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})\geq 0$ $V(\sigma ')\geq V(\sigma )$

Derfor kan vi reducere antallet af inversioner uden at formindske værdien (for eksempel at rette inversionerne i boblesorteringsrækkefølge ). Som et resultat vil en sådan proces føre til transformation til , så . $V(\sigma)$ $\sigma$ $\sigma _{0}$ $V(\sigma )\leq V(\sigma _{0})$

Generaliseringer

For flere permutationer

Lad givne ordnede sekvenser . Lad os betegne . Den identiske permutation vil stadig blive betegnet som . $s$ $x_{1}^{(i)}\leq x_{2}^{(i)}\leq \dots \leq x_{n}^{(i)},\ i=1,\dots, s$ ${\displaystyle V(\sigma _{1},\dots ,\sigma _{s})=x_{\sigma _{1}(1)}^{(1)}x_{\sigma _{2}( 1)}^{(2)}\dots x_{\sigma _{s}(1)}^{(s)}+\dots +x_{\sigma _{1}(n)}^{(1) }x_{\sigma _{2}(n)}^{(2)}\dots x_{\sigma _{s}(n)}^{(s)))$ $\sigma _{0}$

Så for ethvert sæt . $V(\sigma _{1},\dots ,\sigma _{s})\leq V(\sigma _{0},\dots ,\sigma _{0})$ $(\sigma _{1},\dots,\sigma _{s})$

Bevis

Det bevises på samme måde som den sædvanlige permutationsulighed (et særligt tilfælde af dette for ). $s=2$

Uden tab af generalitet vil vi antage, at , for ellers kan vi simpelthen gange alle permutationer med uden at ændre værdien af summen. $\sigma _{1}=\sigma _{0}$ ${\displaystyle \sigma _{1}^{-1))$

Hvis mindst en af permutationerne er forskellig fra , så eksisterer der for den (vi betegner det med ) sådan at . ${\displaystyle \sigma _{1},\dots ,\sigma _{s))$ $\sigma _{0}$ ${\displaystyle \sigma _{k))$ $i<j$ $\sigma _{k}(i)>\sigma _{k}(j)$

Hvis der så i alle permutationer fra mængden, som \sigma (i) > \sigma (j) værdierne og udveksles for, vil værdien ikke falde, men det samlede antal inversioner blandt vil blive mindre. $\sigma$ $(\sigma _{1},\dots,\sigma _{s})$ $\sigma (i)$ $\sigma (j)$ $V$ $(\sigma _{1},\dots,\sigma _{s})$

Ved at udføre sådanne handlinger det nødvendige (endelige) antal gange, kommer vi til sættet uden at formindske værdien af . $(\sigma _{0},\dots,\sigma _{0})$ $V$

For konvekse funktioner

Ideen om bevis ved trin-for-trin korrektion af inversioner er anvendelig til en bredere klasse af tilfælde end blot prikproduktet.

Lade være en konveks funktion , og være ordnet i ikke-faldende rækkefølge. Derefter $f$ $x$ $y$

f(x_{1}+y_{\sigma (1)})+\dots +f(x_{n}+y_{\sigma (n)})\leq f(x_{1}+y_{ 1})+\dots f(x_{n}+y_{n})

Bevis

Per definition af en konveks funktion, hvis , så , det er . Ved at erstatte og tilføje både værdien får vi . Med andre ord, jo større argumentet er, desto større bøjning opad har funktionen, og jo mere værdifuldt er det at tilføje en større værdi der for at maksimere summen. $x_{1}<x_{2},\ c>0$ $f(x_{1}+c)-f(x_{1})\leq f(x_{2}+c)-f(x_{2})$ $f(x_{1}+c)+f(x_{2})\leq f(x_{1})+f(x_{2}+c)$ ${\displaystyle c=c_{2}-c_{1))$ ${\displaystyle x_{1},x_{2))$ $c_{1}$ $f(x_{1}+c_{2})+f(x_{2}+c_{1})\leq f(x_{1}+c_{1})+f(x_{2}+ c_{2})$

Som i beviset for den sædvanlige permutationsulighed vælger vi sådan, at . $i<j$ $\sigma (i)>\sigma (j)$

Så, som beskrevet ovenfor . Dette giver os mulighed for at udføre en induktion svarende til det sædvanlige tilfælde. $f(x_{i}+y_{\sigma (i)})+f(x_{j}+y_{\sigma (j)})\leq f(x_{i}+y_{\sigma ( j)})+f(x_{j}+y_{\sigma (i)})$

Ved at gange alle værdier med , kan vi udlede en lignende ulighed, men med et fortegn i den modsatte retning, for konkave funktioner . $f$ $-en$

Konsekvenser

for (konveks funktion): den sædvanlige permutationsulighed for mængder og $f(x)=e^{x}$ $e^{x_{1)),\dots ,e^{x_{n))$ $e^{y_{1}},\dots,e^{y_{n}}$

at (konveks funktion): $f(x)=x^{2}$ $\sum \limits _{i}^{n}{(x_{i}^{2}+2x_{i}y_{\sigma (i)}+y_{\sigma (i)}^{2 })}\leq \sum \limits _{i}^{n}{(x_{i}^{2}+2x_{i}y_{i}+y_{i}^{2})}$

Efter at have reduceret begge dele med , opnår vi igen den sædvanlige permutationsulighed. ${\displaystyle \sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2)))))$

for (konkav funktion): ${\displaystyle f(x)=\log {x))$ $\sum \limits _{i=1}^{n}{\ln(x_{i}+y_{\sigma (i)})}\geq \sum \limits _{i=1}^{ n}{\ln(x_{i}+y_{i})}$

Efter at have taget eksponenten fra begge dele: ; $\prod _{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod _{i=1}^{n}{(x_{ i}+y_{i})}$

for (konkav funktion): $f(x)={\frac {1}{x}}$ ${\displaystyle \sum \limits _{i=1}^{n}{\frac {1}{x_{i}+y_{\sigma (i)))}\geq \sum \limits _{i=1 }^{n}{\frac {1}{x_{i}+y_{i))))$

Mislykkede forsøg på generalisering

I 1946 blev et forsøg offentliggjort (Scripta Mathematica 1946, 12(2), 164-169) på at generalisere uligheden som følger:

For og to sæt reelle tal og , $n\ge 3$ $x_1\leqslant\cdots\leqslant x_n$ $y_1\leqslant\cdots\leqslant y_n$

x_1 y_{\sigma (1)} + \cdots + x_n y_{\sigma (n)} \leqslant x_1 y_{\pi(1)} + \cdots + x_n y_{\pi(n)}

hvis antallet af inversioner i permutationen er mindre end i permutationen . $\pi$ $\sigma$

Senere viste det sig dog, at denne generalisering kun gælder for . Da der er modeksempler på denne generalisering, såsom: $n=3$ $n=4$

{\textstyle 0\cdot 0+1\cdot 1+2\cdot 10+3\cdot 2=27<31=0\cdot 2+1\cdot 1+2\cdot 0+3\cdot 10.}

Konsekvenser

Permutationsuligheden er interessant, idet den giver dig mulighed for intuitivt at kombinere på et fælles grundlag udadtil fuldstændig uens numeriske uligheder, der bruges inden for forskellige områder af matematikken.

Dette afsnit omhandler sæt af længdetal og antager, at notationen for betegner , det vil sige indeksløkker. $n$ $x_{i}$ $i>n$ ${\displaystyle x_{in))$

Cauchy-Bunyakovsky uligheden

Ifølge permutation ulighed, for enhver , . $k$ $\sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}}\leq \sum \limits _{i=0}^{n-1}{ a_{i}^{2}}$

Heraf udledes et særligt tilfælde af Cauchy-Bunyakovsky-uligheden:

\left({\sum \limits _{i=0}^{n-1}{a_{i))}\right)^{2}=\sum \limits _{i=0}^{ n-1}\sum \limits _{j=0}^{n-1}{a_{i}a_{j}}=\sum \limits _{i=0}^{n-1}\sum \ grænser _{j=0}^{n-1}{a_{i}a_{i+j}}\leq \sum \limits _{j=0}^{n-1}{\sum \limits _{ i=1}^{n}{a_{i}^{2}}}=n\sum \limits _{i=1}^{n}{a_{i}^{2}}

På samme måde udledes en mere generel ulighed for heltal ved at dele summen over alle mulige dimensionelle indeksforskydninger og bruge en generalisering over flere permutationer : ${\displaystyle n^{k-1))$ $(k-1)$ $k$

\left({\sum \limits _{i=0}^{n-1}{a_{i))}\right)^{k}\leq n^{k-1}\sum \limits _{i=0}^{n-1}{a_{i}^{k}}

Den generelle Cauchy-Bunyakovsky ulighed

2(a_{1}b_{1}+\dots +a_{n}b_{n})=a_{1}b_{1}+\dots +a_{n}b_{n}+b_{ 1}a_{1}+\dots +b_{n}a_{n}\leq a_{1}^{2}+\dots +a_{n}^{2}+b_{1}^{2}+ \dots +b_{n}^{2}

Hvis værdierne af og er normaliseret på en sådan måde , at Cauchy-Bunyakovsky-uligheden som en konsekvens opnås. For at gøre dette er det nok at dividere alt med , og alt med . Da Cauchy-Bunyakovsky-uligheden tillader sådanne opdelinger uden at ændre sandheden, beviser dette påstanden. $a_{i}$ $b_{i}$ $a_{1}^{2}+\dots +a_{n}^{2}=b_{1}^{2}+\dots +b_{n}^{2}=1$ $a_{i}$ ${\displaystyle {\sqrt {a_{1}^{2}+\dots +a_{n}^{2))))$ $b_{i}$ ${\displaystyle {\sqrt {b_{1}^{2}+\dots +b_{n}^{2))))$

Gennemsnitlige uligheder

Kvadratisk og aritmetisk

Uligheden mellem den gennemsnitlige kvadratiske og den aritmetiske middelværdi er elementært afledt af det særlige tilfælde af Cauchy-Bunyakovsky uligheden bevist ovenfor.

Aritmetisk og geometrisk

Uligheden mellem det aritmetiske og geometriske middelværdi angiver det