Transolikhet

Permutationsojämlikheten , eller ojämlikheten om enmonotona sekvenser , eller " trans -ojämlikhet ", anger att prickprodukten av två uppsättningar tal är den maximala möjliga om uppsättningarna är enkelmonotona (det vill säga båda är samtidigt icke-minskande eller samtidigt icke-ökande), och den minsta möjliga om uppsättningarna är av motsatt monotoni (då är den ena icke-minskande och den andra icke-ökande).

Med andra ord, om och , då för en godtycklig permutation av siffror gäller följande olikhet: $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

I synnerhet om , då oavsett beställning . ${\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 av permutationsojämlikheten är Chebyshev-ojämlikheten för summorna .

Bevis

Låt oss beteckna . Som bevis är det lämpligt att omformulera uttalandet något: $V(\sigma )=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)))$

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

Här är uppsättningen av alla möjliga permutationer , och är den identiska permutationen . $S_{n}$ $\sigma _{0}:\x\mapsto x$

Huvudtanken med beviset är att om för vissa , så kommer vi inte att minska värdet på summan genom att byta ut värdena på och . $\sigma (i)>\sigma (j)$ $i<j$ $\sigma (i)$ $\sigma (j)$ $V (\ Sigma)$

Tänk på den angivna summan för någon permutation och ett sådant par . Betrakta permutationen som bildas från inversionerna av detta 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\inte \i \{{i,j}\}.\end{matris}}\right.

Per definition,

{\ DisplayStyle 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_} -x_ {i}) (y _ \ sigma (i)}-y _ {\ sigma ( j )})}

Genom val och ordningsantagandet är ojämlikheten sann , så att . $I j$ $x,y$ ${\ displayStyle (x_ {j} -x_ {i}) (y _ {\ sigma (i)}-y _ {\ sigma (j)}) \ geq 0}$ $V(\sigma ')\geq V(\sigma )$

Därför kan vi minska antalet inversioner utan att minska värdet (till exempel fixa inversionerna i bubbelsorteringsordning ). Som ett resultat kommer en sådan process att leda till transformation i , så . $V (\ Sigma)$ $\sigma$ $\sigma _{0}$ $V(\sigma )\leq V(\sigma _{0})$

Generaliseringar

För flera permutationer

Låt de ordnade sekvenserna ges . Låt oss beteckna . Den identiska permutationen kommer fortfarande att betecknas som . $s$ ${\ displayStyle 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)} \ prickar x _ {\ sigma _ {s} (1)}^{(s) +\ prickar +x _ {\ sigma {1} (n)}^{(1) }x_{\sigma _{2}(n)}^{(2)}\dots x_{\sigma _{s}(n)}^{(s)))$ $\sigma _{0}$

Sedan för vilken uppsättning som helst . ${\ DisplayStyle V (\ Sigma _ {1}, \ Dots, \ Sigma _ {S}) \ LeQ V (\ Sigma _ {0}, \ Dots, \ Sigma _ {0})}}}}}}} }}$ $(\sigma _{1},\dots ,\sigma _{s})$

Bevis

Det bevisas på samma sätt som den vanliga permutationsojämlikheten (ett specialfall av detta för ). $s=2$

Utan förlust av generalitet kommer vi att anta att , för annars kan vi helt enkelt multiplicera alla permutationer med utan att ändra värdet på summan. $\sigma _{1}=\sigma _{0}$ ${\displaystyle \sigma _{1}^{-1))$

Om åtminstone en av permutationerna skiljer sig från , så finns det för den (vi betecknar den med ) sådana att . ${\displaystyle \sigma _{1},\dots ,\sigma _{s))$ $\sigma _{0}$ ${\displaystyle \sigma _{k))$ $i<j$ $\sigma _{k}(i)>\sigma _{k}(j)$

Sedan, om i alla permutationer från den uppsättning för vilken \sigma (i) > \sigma (j) värdena och är utbytta , så kommer värdet inte att minska, men det totala antalet inversioner bland kommer att bli mindre. $\sigma$ $(\sigma _{1},\dots ,\sigma _{s})$ $\sigma (i)$ $\sigma (j)$ $V$ $(\sigma _{1},\dots ,\sigma _{s})$

Genom att utföra sådana åtgärder det nödvändiga (ändliga) antalet gånger kommer vi fram till uppsättningen utan att minska värdet på . $(\sigma _{0},\dots ,\sigma _{0})$ $V$

För konvexa funktioner

Idén med bevis för steg-för-steg-korrigering av inversioner är tillämplig på en bredare klass av fall än bara punktprodukten.

Låt - en konvex funktion , och strömlinjeformad av bristande efterlevnad. Sedan $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 av en konvex funktion, om , då , det vill säga . Att stödja och lägga till båda får vi . Med andra ord, ju större argument, desto större böjning uppåt av funktionen, och desto mer värdefullt är det att lägga till ett större värde där för att maximera summan. $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 på den vanliga permutationsojämlikheten väljer vi så att . $i<j$ $\sigma (i)>\sigma (j)$

Sedan, som beskrivits ovan . Detta möjliggör induktion liknande det vanliga fallet. $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)})}$

Genom att multiplicera alla värden med , kan vi härleda en liknande olikhet, men med ett tecken i motsatt riktning, för konkava funktioner . $f$ $-ett$

Konsekvenser

med (konvex funktion): vanlig tillåtande olikhet för mängder och $f(x)=e^{x}$ ${\ Displaystyle e^{x_ {1}, \ dots, e^{x_ {n}}}}}}}$ ${\ displayStyle e^{y_ {1}, \ dots, e^{y_ {n}}}}}$

at (konvex 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 att ha reducerat båda delarna med får vi återigen den vanliga permutationsojämlikheten. ${\displaystyle \sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2)))))$

med (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 att ha tagit utställarna från båda delarna :; $\prod _{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod _{i=1}^{n}{(x_{ i}+y_{i})}$

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

Misslyckade försök att generalisera

1946 publicerades ett försök (Scripta Mathematica 1946, 12(2), 164-169) att generalisera ojämlikheten enligt följande:

För och två uppsättningar av materialnummer och , $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)}

Om antalet inversioner i permutationen är mindre än i permutationen . $\pi$ $\sigma$

Men senare visade det sig att denna generalisering endast gäller för . Eftersom det finns motexempel för denna generalisering, som: $n=3$ $n=4$

{\textstil 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

Permutationsojämlikheten är intressant genom att den låter dig intuitivt kombinera på en gemensam grund utåt helt olika numeriska ojämlikheter som används inom olika områden av matematiken.

Det här avsnittet behandlar uppsättningar av längdnummer och antar att notationen för betecknar , det vill säga indexloopar. $n$ $x_{i}$ $i>n$ ${\displaystyle x_{in))$

Cauchy-Bunyakovsky ojämlikheten

Enligt permutation ojämlikhet, för alla , . $k$ $\sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}}\leq \sum \limits _{i=0}^{n-1}{ a_{i}^{2}}$

Ur detta härleds ett specialfall av Cauchy-Bunyakovsky-ojämlikheten:

\left({\sum \limits _{i=0}^{n-1}{a_{i))}\right)^{2}=\sum \limits _{i=0}^{ n-1}\summa \limits _{j=0}^{n-1}{a_{i}a_{j}}=\summa \limits _{i=0}^{n-1}\summa \ limits _{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\summa \limits _{i=1}^{n}{a_{i}^{2}}

På liknande sätt, genom att dela summan över alla möjliga dimensionella indexskiften och använda en generalisering över flera permutationer, erhålls en mer allmän olikhet för heltal : ${\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 allmänna Cauchy-Bunyakovsky ojämlikheten

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}

Om värdena för och är normaliserade på ett sådant sätt att , som en konsekvens, erhålls Cauchy-Bunyakovsky-ojämlikheten. För att göra detta räcker det att dela allt med , och allt med . Eftersom Cauchy-Bunyakovsky-ojämlikheten tillåter sådana uppdelningar utan att ändra sanningen, bevisar detta påståendet. $a_{i}$ $bi}$ $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))))$ $bi}$ ${\displaystyle {\sqrt {b_{1}^{2}+\dots +b_{n}^{2))))$

Genomsnittliga ojämlikheter

Kvadratisk och aritmetisk

Olikheten mellan medelkvadratens och det aritmetiska medelvärdet härleds elementärt från det speciella fallet med Cauchy-Bunyakovsky-ojämlikheten som bevisats ovan.

Aritmetiska och geometriska

Olikheten mellan det aritmetiska och geometriska medelvärdet säger att

{\sqrt[{n}]{x_{1}\dots x_{n}}}\leq {\frac {x_{1}+\dots +x_{n}}{n}}

Om vi multiplicerar båda delarna med och tar hänsyn till variablernas th potenser ser vi att detta är detsamma som $n$ $n$

{\displaystyle nx_{1}\dots x_{n}\leq x_{1}^{n}+\dots x_{n}^{n))

x_{1}x_{2}\dots x_{n-1}x_{n}+x_{2}x_{3}\dots x_{n}x_{1}+\dots +x_{n} x_{1}\dots x_{n-2}x_{n-1}\leq x_{1}^{n}+\dots x_{n}^{n}

Den sista olikheten erhålls lätt från generaliseringen av permutationsojämlikheten till flera permutationer för ${\ displayStyle \ sigma _ {k} (i) = i+(k-1)}$

Geometrisk och harmonisk

Vi tar ojämlikheten till samma form som den föregående:

{\sqrt[{n}]{x_{1}\dots x_{n))}\geq {\frac {n}({\frac {1}{x_{1))}+\dots { \frac {1}{x_{n}}}}}

{\frac {1}{x_{1}}}+\dots {\frac {1}{x_{n}}}\geq {\frac {n}{\sqrt[{n}]{x_ {1}\dots x_{n}}}}}

Med tanke på variablernas e potenser får vi $n$

n\left({\frac {1}{x_{1))}\right)\dots \left({\frac {1}{x_{n))}\right)\leq \left({ \frac {1}{x_{1}}}\right)^{n}+\dots \left({\frac {1}{x_{n}}}\right)^{n}

Den sista olikheten är lätt att erhålla genom direkt tillämpning av permutationsolikheten för flera permutationer.

Länkar

L. V. Radzivilovskiy. Generalisering av permutationsojämlikheten och den mongoliska ojämlikheten // Matematisk utbildning . - 2006. - Nr 10 .
V. I. Murashko, S. M. Gorsky, Ya. I. Sandrygailo. KφKψ-konvexa funktioner och generaliseringar av klassiska ojämlikheter // PFMT. - 2018. - Utgåva. 37 , nr 4 . — S. 98–102 .
Yue Kwok Choy, Omarrangemang Ojämlikhet