Transinequality

Permutaatioepäyhtälö eli epäyhtälö yksimonotonisista sekvensseistä tai " trans -epäyhtälö " ilmoittaa, että kahden lukujoukon pistetulo on suurin mahdollinen, jos joukot ovat yksimonotonisia (eli molemmat ovat samanaikaisesti ei-laskevia tai samanaikaisesti ei-nouseva), ja pienin mahdollinen, jos joukot ovat vastakkaisia monotonisia (jolloin toinen on ei-laskeva ja toinen ei-kasvava).

Toisin sanoen, jos ja , niin mielivaltaiselle numeroiden permutaatiolle pätee seuraava epäyhtälö: $x_1\leqslant x_2 \leqslant \dots\leqslant x_n$ $y_1\leqslant y_2 \leqslant \dots\leqslant y_n$ $\sigma$ $\{1,2,\pisteet,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

Erityisesti jos , niin tilauksesta riippumatta . ${\displaystyle y_{i}=x_{i))$ $x_{1}x_{\sigma (1)}+\pisteet +x_{n}x_{\sigma (n)}\leq {x_{1}}^{2}+\pisteet {x_{n }}^{2}$ $x_{1},\pisteet ,x_{n}$

Permutaatioepäyhtälön seuraus on Tšebyševin epäyhtälö summille .

Todiste

Merkitään . Todistuksen vuoksi on kätevää muotoilla väite hieman uudelleen: $V(\sigma )=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)))$

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

Tässä on joukko kaikkia mahdollisia permutaatioita , ja se on identtinen permutaatio . $S_{n}$ $\sigma _{0}:\x\mapsto x$

Todistuksen pääidea on, että jos joillekin , niin vaihtamalla ja arvoja emme vähennä summan arvoa . $\sigma (i)>\sigma (j)$ $i<j$ $\sigma (i)$ ${\näyttötyyli \sigma (j)}$ $V(\sigma)$

Harkitse ilmoitettua summaa jollekin permutaatiolle ja sellaiselle parille . Tarkastellaan tämän parin inversioista muodostettua permutaatiota . ${\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\not \in \{{i,j}\}.\end{matrix}}\right.

Määritelmän mukaan

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)})

Valinnan ja järjestysoletuksen mukaan epäyhtälö on totta , joten . $i, j$ $x,y$ $(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})\geq 0$ $V(\sigma ')\geq V(\sigma )$

Siksi voimme vähentää inversioiden määrää ilman, että arvo pienenee (esimerkiksi korjaamalla inversiot kuplajärjestykseen ). Tämän seurauksena tällainen prosessi johtaa muuttumiseen , joten . $V(\sigma)$ $\sigma$ $\sigma _{0}$ $V(\sigma )\leq V(\sigma _{0})$

Yleistykset

Useita permutaatioita varten

Olkoon annetut järjestetyt sekvenssit . Merkitään . Sama permutaatio merkitään edelleen nimellä . $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)}\pisteet x_{\sigma _{s}(1)}^{(s)}+\pisteet +x_{\sigma _{1}(n)}^{(1) }x_{\sigma _{2}(n)}^{(2)}\pisteet x_{\sigma _{s}(n)}^{(s)))$ $\sigma _{0}$

Sitten mihin tahansa sarjaan . $V(\sigma _{1},\dots ,\sigma _{s})\leq V(\sigma _{0},\dots ,\sigma _{0})$ $(\sigma _{1},\dots ,\sigma _{s})$

Todiste

Se todistetaan samalla tavalla kuin tavallinen permutaatio-epäyhtälö (tämän erikoistapaus kohteelle ). $s = 2$

Yleisyyttä menettämättä oletetaan, että , koska muuten voimme yksinkertaisesti kertoa kaikki permutaatiot muuttamatta summan arvoa. $\sigma _{1}=\sigma _{0}$ ${\displaystyle \sigma _{1}^{-1))$

Jos ainakin yksi permutaatioista on erilainen kuin , niin sille (merkitsimme sitä ) on olemassa sellainen, että . ${\displaystyle \sigma _{1},\dots ,\sigma _{s))$ $\sigma _{0}$ ${\displaystyle \sigma _{k))$ $i<j$ $\sigma _{k}(i)>\sigma _{k}(j)$

Sitten, jos kaikissa permutaatioissa joukosta , jonka \sigma (i) > \sigma (j) arvot ja vaihdetaan keskenään , arvo ei pienene, mutta inversioiden kokonaismäärä joukossa pienenee. $\sigma$ $(\sigma _{1},\dots ,\sigma _{s})$ $\sigma (i)$ ${\näyttötyyli \sigma (j)}$ $V$ $(\sigma _{1},\dots ,\sigma _{s})$

Suorittamalla tällaisia toimintoja tarvittavan (äärellisen) määrän kertoja, saavutamme joukon vähentämättä arvoa . $(\sigma _{0},\dots ,\sigma _{0})$ $V$

Kuperille funktioille

Ajatus todistetusta käänteiskorjauksesta askel askeleelta on sovellettavissa laajempaan tapausluokkaan kuin vain pistetuloon.

Antaa olla kupera funktio , ja järjestettävä ei-laskevassa järjestyksessä. Sitten $f$ $x$ $y$

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

Todiste

Konveksin funktion määritelmän mukaan jos , niin , eli . Korvaamalla ja lisäämällä molemmat arvot saamme . Toisin sanoen, mitä suurempi argumentti, sitä suurempi on funktion ylöspäin suuntautuva mutka, ja sitä arvokkaampaa on lisätä siihen suurempi arvo summan maksimoimiseksi. $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))$ ${\näyttötyyli 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})$

Kuten tavanomaisen permutaatioepäyhtälön todistuksessa, valitsemme sellaisen, että . $i<j$ $\sigma (i)>\sigma (j)$

Sitten, kuten edellä on kuvattu, . Näin voimme suorittaa induktion, joka on samanlainen kuin tavallisessa tapauksessa. $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)})$

Kun kaikki arvot kerrotaan arvolla , saadaan samanlainen epäyhtälö, mutta päinvastaisella merkillä koveralle funktiolle . $f$ $-yksi$

Seuraukset

for (kupera funktio): tavallinen permutaatioepäyhtälö joukoille ja $f(x)=e^{x}$ $e^{x_{1)),\dots ,e^{x_{n))$ $e^{y_{1}},\dots ,e^{y_{n}}$

at (kupera funktio): $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})}$

Kun molempia osia on vähennetty arvolla , saadaan taas tavallinen permutaatioepäyhtälö. ${\displaystyle \sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2)))))$

varten (kovera funktio): ${\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})}$

Kun eksponentti on otettu molemmista osista: ; $\prod _{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod _{i=1}^{n}{(x_{ i}+y_{i})}$

varten (kovera funktio): $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))))$

Epäonnistuneita yleistysyrityksiä

Vuonna 1946 julkaistiin yritys (Scripta Mathematica 1946, 12(2), 164-169) yleistää epätasa-arvo seuraavasti:

Sillä ja kaksi reaalilukua ja , $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)}

jos inversioiden määrä permutaatiossa on pienempi kuin permutaatiossa . $\pi$ $\sigma$

Myöhemmin kuitenkin kävi ilmi, että tämä yleistys pätee vain . Koska tälle yleistykselle on vastaesimerkkejä, kuten: $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.}

Seuraukset

Permutaatioepäyhtälö on mielenkiintoinen siinä mielessä, että sen avulla voidaan intuitiivisesti yhdistää yhteisellä pohjalla ulkoisesti täysin erilaisia numeerisia epäyhtälöitä, joita käytetään matematiikan eri alueilla.

Tämä osio käsittelee pituisten lukujen joukkoja ja olettaa, että merkintä tarkoittaa , eli indeksisilmukoita. $n$ $x_{i}$ $i>n$ ${\displaystyle x_{in))$

Cauchyn ja Bunyakovskin epätasa-arvo

Permutaatioepäyhtälön mukaan mille tahansa , . $k$ $\sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}}\leq \sum \limits _{i=0}^{n-1}{ a_{i}^{2}}$

Tästä johdetaan Cauchyn-Bunyakovsky-epätasa-arvon erikoistapaus:

\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 \ rajat _{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}}

Samoin jakamalla summa kaikkien mahdollisten -ulotteisten indeksisiirtojen kesken ja käyttämällä yleistystä useille permutaatioille, saadaan yleisempi epäyhtälö kokonaislukuille : ${\näyttötyyli n^{k-1))$ $(k-1)$ $k$

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

Yleinen Cauchyn ja Bunyakovskin epätasa-arvo

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

Jos ja arvot normalisoidaan siten, että , niin tuloksena saadaan Cauchyn ja Bunyakovskyn epäyhtälö. Tätä varten riittää jakaa kaikki luvulla ja kaikki . Koska Cauchyn ja Bunyakovskyn epätasa-arvo sallii tällaiset jaot muuttamatta totuutta, tämä todistaa väitteen. $a_{i}$ $b_{i}$ $a_{1}^{2}+\pisteet +a_{n}^{2}=b_{1}^{2}+\pisteet +b_{n}^{2}=1$ $a_{i}$ ${\displaystyle {\sqrt {a_{1}^{2}+\pisteet +a_{n}^{2))))$ $b_{i}$ ${\displaystyle {\sqrt {b_{1}^{2}+\pisteet +b_{n}^{2))))$

Keskimääräiset epätasa-arvot

Neliöllinen ja aritmeettinen

Keskimääräisen neliöllisen ja aritmeettisen keskiarvon välinen epätasa-arvo johdetaan alkeellisesti edellä todistetusta Cauchyn ja Bunyakovskyn epäyhtälöstä.

Aritmetiikka ja geometria

Aritmeettisen ja geometrisen keskiarvon välinen epäyhtälö kertoo sen

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

Kertomalla molemmat osat ja ottaen huomioon muuttujien th potenssit, näemme, että tämä on sama kuin $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}\pisteet x_{n-2}x_{n-1}\leq x_{1}^{n}+\pisteet x_{n}^{n}

Viimeinen epäyhtälö saadaan helposti yleistämällä permutaatioepäyhtälö useiksi permutaatioiksi for $\sigma _{k}(i)=i+(k-1)$

Geometrinen ja harmoninen

Tuomme epätasa-arvon samaan muotoon kuin edellinen:

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

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

Ottaen huomioon muuttujien th potenssit, saamme $n$

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

Viimeinen epäyhtälö on helppo saada soveltamalla permutaatioepäyhtälöä suoraan useille permutaatioille.

Linkit

L. V. Radzivilovski. Permutaatioepätasa-arvon ja Mongolian epätasa-arvon yleistäminen // Mathematical Education . - 2006. - Nro 10 .
V. I. Murashko, S. M. Gorsky, Ya. I. Sandrygailo. KφKψ-kuperat funktiot ja klassisten epäyhtälöiden yleistykset // PFMT. - 2018. - Numero. 37 , nro 4 . — S. 98–102 .
Yue Kwok Choy, Uudelleenjärjestelyepätasa-arvo