Transinequality

A permutációs egyenlőtlenség vagy az egymonoton sorozatok egyenlőtlensége , vagy " transz -egyenlőtlenség " azt állítja, hogy két számhalmaz pontszorzata a lehető legnagyobb, ha a halmazok egymonotonok (vagyis mindkettő egyszerre nem csökkenő vagy egyidejűleg nem növekvő), és a lehető legkisebb, ha a halmazok ellentétes monotonitásúak (akkor az egyik nem csökkenő, a másik nem növekvő).

Más szóval, ha és , akkor a számok tetszőleges permutációjára a következő egyenlőtlenség érvényes: $x_1\leqslant x_2 \leqslant \dots\leqslant x_n$ $y_1\leqslant y_2 \leqslant \dots\leqslant y_n$ $\sigma$ $\{1,2,\pontok,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

Különösen, ha , akkor a rendeléstől függetlenül . $y_{i}=x_{i}$ $x_{1}x_{\sigma (1)}+\pontok +x_{n}x_{\sigma (n)}\leq {x_{1}}^{2}+\pontok {x_{n }}^{2}$ $x_{1},\pontok,x_{n}$

A permutációs egyenlőtlenség következménye az összegekre vonatkozó Csebisev-egyenlőtlenség .

Bizonyítás

Jelöljük . A bizonyításhoz célszerű némileg újrafogalmazni az állítást: $V(\sigma )=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)))$

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

Itt van az összes lehetséges permutáció halmaza , és ez az azonos permutáció . $S_{n}$ $\sigma _{0}:\x\mapsto x$

A bizonyítás fő gondolata az, hogy ha egyesekre , akkor az és értékeinek felcserélésével nem csökkentjük az összeg értékét . $\sigma (i)>\sigma (j)$ $i<j$ $\sigma (i)$ $\sigma (j)$ $V(\sigma)$

Tekintsük a megadott összeget valamilyen permutációra és egy ilyen párra . Tekintsük ennek a párnak az inverzióiból képzett permutációt . ${\displaystyle \sigma \not =\sigma _{0))$ $i,j$ $\sigma$

\sigma ':x\mapsto \left\{{\begin{mátrix}\sigma (j),&x=i,\\\sigma (i),&x=j,\\\sigma (x), &x\not \in \{{i,j}\}.\end{mátrix}}\jobbra.

Definíció szerint,

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

A választás és a sorrendi feltevés alapján az egyenlőtlenség igaz , tehát . $i,j$ $x,y$ $(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})\geq 0$ $V(\sigma ')\geq V(\sigma )$

Ezért csökkenthetjük az inverziók számát az érték csökkentése nélkül (például az inverziók rögzítése buborék rendezési sorrendben ). Ennek eredményeként egy ilyen folyamat átalakuláshoz vezet , tehát . $V(\sigma)$ $\sigma$ $\sigma _{0}$ $V(\sigma )\leq V(\sigma _{0})$

Általánosítások

Több permutációhoz

Legyen megadott rendezett sorozatok . Jelöljük . Az azonos permutációt továbbra is jelöli . $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)}\pontok x_{\sigma _{s}(1)}^{(s)}+\pontok +x_{\sigma _{1}(n)}^{(1) }x_{\sigma _{2}(n)}^{(2)}\pontok x_{\sigma _{s}(n)}^{(s)))$ $\sigma _{0}$

Akkor bármelyik készlethez . $V(\sigma _{1},\dots ,\sigma _{s})\leq V(\sigma _{0},\dots ,\sigma _{0})$ $(\sigma _{1},\dots ,\sigma _{s})$

Bizonyíték

Ezt a szokásos permutációs egyenlőtlenséghez hasonlóan bizonyítjuk (ennek speciális esete -re ). $s=2$

Az általánosság elvesztése nélkül feltételezzük, hogy , mert különben egyszerűen megszorozhatjuk az összes permutációt anélkül, hogy megváltoztatnánk az összeg értékét. $\sigma _{1}=\sigma _{0}$ ${\displaystyle \sigma _{1}^{-1))$

Ha legalább az egyik permutáció különbözik a -tól , akkor számára (jellel jelöljük ) létezik olyan, hogy . ${\displaystyle \sigma _{1},\dots ,\sigma _{s))$ $\sigma _{0}$ ${\displaystyle \sigma _{k))$ $i<j$ $\sigma _{k}(i)>\sigma _{k}(j)$

Ekkor, ha a halmaz összes permutációjában , amelyre \sigma (i) > \sigma (j) a és értékek felcserélődnek , akkor az érték nem csökken, de az inverziók össz száma csökken . $\sigma$ $(\sigma _{1},\dots ,\sigma _{s})$ $\sigma (i)$ $\sigma (j)$ $V$ $(\sigma _{1},\dots ,\sigma _{s})$

Ilyen műveleteket a szükséges (véges) számú alkalommal végrehajtva úgy jutunk el a halmazhoz, hogy nem csökkentjük az értékét . $(\sigma _{0},\dots ,\sigma _{0})$ $V$

Konvex függvényekhez

Az inverziók lépésről lépésre történő korrekciójának gondolata az esetek szélesebb osztályára alkalmazható, mint a pontszorzat.

Legyen egy konvex függvény , és legyen nem csökkenő sorrendben rendezve. Akkor $f$ $x$ $y$

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

Bizonyíték

A konvex függvény definíciója szerint, ha , akkor , azaz . Mindkettőt behelyettesítve és hozzáadva az értéket kapjuk . Más szóval, minél nagyobb az argumentum, annál nagyobb a függvény felfelé hajlása, és annál értékesebb, ha nagyobb értéket adunk hozzá az összeg maximalizálása érdekében. $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})$

A szokásos permutációs egyenlőtlenség bizonyításához hasonlóan azt választjuk , hogy . $i<j$ $\sigma (i)>\sigma (j)$

Ezután a fent leírtak szerint . Ez lehetővé teszi, hogy a szokásos esethez hasonló indukciót hajtsunk végre. $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)})$

Az összes értéket megszorozva konkáv függvényekre hasonló egyenlőtlenséget kaphatunk, de ellenkező irányú előjellel . $f$ $-egy$

Következmények

for (konvex függvény): a szokásos permutációs egyenlőtlenség halmazokra és $f(x)=e^{x}$ $e^{x_{1)),\dots ,e^{x_{n))$ $e^{y_{1}},\dots ,e^{y_{n}}$

at (konvex függvény): $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})}$

Miután mindkét részt csökkentjük -vel , ismét megkapjuk a szokásos permutációs egyenlőtlenséget. ${\displaystyle \sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2)))))$

for (konkáv függvény): ${\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})}$

Miután mindkét részből vettük a kitevőt : ; $\prod _{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod _{i=1}^{n}{(x_{ i}+y_{i})}$

for (konkáv függvény): $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))))$

Sikertelen általánosítási kísérletek

1946-ban kísérletet tettek közzé (Scripta Mathematica 1946, 12(2), 164-169), hogy az egyenlőtlenséget a következőképpen általánosítsák:

For és két valós számhalmaz és , $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)}

ha a permutációban az inverziók száma kisebb, mint a permutációban . $\pi$ $\sigma$

Később azonban kiderült, hogy ez az általánosítás csak a -ra igaz . Mivel erre az általánosításra vannak ellenpéldák, mint például: $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.}

Következmények

A permutációs egyenlőtlenség érdekes abból a szempontból, hogy lehetővé teszi a matematika különböző területein használt, külsőleg teljesen eltérő numerikus egyenlőtlenségek intuitív, közös alapon történő kombinálását.

Ez a szakasz a hosszúságú számok halmazaival foglalkozik, és feltételezi, hogy a jelölések jelölik , azaz indexhurkok . $n$ $x_{i}$ $i>n$ ${\displaystyle x_{in))$

A Cauchy-Bunyakovsky egyenlőtlenség

A permutációs egyenlőtlenség szerint bármely , . $k$ $\sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}}\leq \sum \limits _{i=0}^{n-1}{ a_{i}^{2}}$

Ebből adódik a Cauchy-Bunyakovsky egyenlőtlenség egy speciális esete:

\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 \ 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\sum \limits _{i=1}^{n}{a_{i}^{2}}

Hasonlóképpen, ha az összeget felosztjuk az összes lehetséges -dimenziós indexeltolásra, és több permutáción keresztül általánosítunk, egy általánosabb egyenlőtlenséget kapunk az egész számokra : ${\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}}

Az általános Cauchy-Bunyakovsky egyenlőtlenség

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

Ha a és értékeit úgy normalizáljuk , hogy , akkor ennek eredményeként megkapjuk a Cauchy-Bunyakovsky egyenlőtlenséget. Ehhez elég mindent elosztani -vel , és mindent -vel . Mivel a Cauchy-Bunyakovsky egyenlőtlenség az igazság megváltoztatása nélkül megengedi az ilyen felosztásokat, ez bizonyítja az állítást. $a_{i}$ $kettős}$ $a_{1}^{2}+\pontok +a_{n}^{2}=b_{1}^{2}+\pontok +b_{n}^{2}=1$ $a_{i}$ ${\displaystyle {\sqrt {a_{1}^{2}+\dots +a_{n}^{2))))$ $kettős}$ ${\displaystyle {\sqrt {b_{1}^{2}+\pontok +b_{n}^{2))))$

Átlagos egyenlőtlenségek

Másodfokú és aritmetika

A másodfokú és a számtani átlag közötti egyenlőtlenség alapvetően a Cauchy-Bunyakovsky egyenlőtlenség fentebb bizonyított konkrét esetéből adódik.

Aritmetika és geometriai

A számtani és a geometriai átlag egyenlőtlensége azt állítja

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

Mindkét részt megszorozva a változók hatványait figyelembe véve azt látjuk, hogy ez megegyezik $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}\pontok x_{n-2}x_{n-1}\leq x_{1}^{n}+\pontok x_{n}^{n}

Az utolsó egyenlőtlenség könnyen megkapható a permutációs egyenlőtlenség több permutációra történő általánosításából $\sigma _{k}(i)=i+(k-1)$

Geometriai és harmonikus

Az egyenlőtlenséget ugyanabba a formába hozzuk, mint az előző:

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

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

Figyelembe véve a változók th hatványát, azt kapjuk $n$

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

Az utolsó egyenlőtlenség könnyen megszerezhető a permutációs egyenlőtlenség közvetlen alkalmazásával több permutációra.

Linkek

L. V. Radzivilovskiy. A permutációs egyenlőtlenség és a mongol egyenlőtlenség általánosítása // Mathematical Education . - 2006. - 10. sz .
V. I. Murashko, S. M. Gorsky, Ya. I. Sandrygailo. KφKψ-konvex függvények és klasszikus egyenlőtlenségek általánosításai // PFMT. - 2018. - Kiadás. 37 , 4. sz . – S. 98–102 .
Yue Kwok Choy, Átrendezési egyenlőtlenség