Inegalitatea de permutare , sau inegalitatea despre secvențele monotone sau „ trans -inegalitatea ”, afirmă că produsul punctual a două seturi de numere este maximul posibil dacă seturile sunt monotone (adică ambele sunt simultan nedescrescătoare ). sau simultan necrescător), iar cel mai mic posibil dacă mulţimile sunt de monotonitate opusă (atunci una este nedescrescătoare, iar cealaltă este necrescătoare).
Cu alte cuvinte, dacă și , atunci pentru o permutare arbitrară a numerelor , este valabilă următoarea inegalitate:
În special, dacă , atunci indiferent de comanda .
O consecință a inegalității de permutare este inegalitatea Chebyshev pentru sume .
Să notăm . Pentru demonstrație, este convenabil să reformulam oarecum afirmația:
Aici este setul tuturor permutărilor posibile și este permutarea identică .
Ideea principală a dovezii este că, dacă pentru unii , atunci schimbând valorile lui și , nu vom scădea valoarea sumei .
Luați în considerare suma indicată pentru o permutare și o astfel de pereche . Luați în considerare permutarea formată din inversiunile acestei perechi.
Prin definitie,
Prin alegere și ipoteza de ordonare , inegalitatea este adevărată , astfel încât .
Prin urmare, putem reduce numărul de inversiuni fără a scădea valoarea (de exemplu, fixând inversiunile în ordinea de sortare cu bule ). Drept urmare, un astfel de proces va duce la transformarea în , deci .
Fie secvențe ordonate date . Să notăm . Permutarea identică va fi totuși notată ca .
Apoi pentru orice set .
DovadaSe dovedește în mod similar cu inegalitatea obișnuită de permutare (un caz special al acesteia pentru ).
Fără pierderea generalității, vom presupune că , deoarece altfel putem pur și simplu înmulți toate permutările fără a modifica valoarea sumei.
Dacă cel puțin una dintre permutări este diferită de , atunci pentru aceasta (o notăm cu ) există astfel încât .
Apoi, dacă în toate permutările din mulțimea pentru care \sigma (i) > \sigma (j) valorile și sunt interschimbate , atunci valoarea nu va scădea, dar numărul total de inversiuni între ele va deveni mai mic.
Efectuând astfel de acțiuni de numărul necesar (finit) de ori, ajungem la mulțime fără a scădea valoarea lui .
Ideea de demonstrație prin corectarea pas cu pas a inversiilor este aplicabilă unei clase mai largi de cazuri decât doar produsul punctual.
Fie o funcție convexă și ordonată în ordine nedescrescătoare. Apoi
DovadaPrin definiția unei funcții convexe, dacă , atunci , adică . Înlocuind și adăugând la ambele valori , obținem . Cu alte cuvinte, cu cât argumentul este mai mare, cu atât este mai mare înclinarea în sus a funcției și cu atât este mai valoros să adăugați o valoare mai mare acolo pentru a maximiza suma.
Ca și în dovedirea inegalității obișnuite de permutare, alegem astfel încât .
Apoi, așa cum este descris mai sus, . Acest lucru ne permite să efectuăm o inducție similară cu cazul obișnuit.
Înmulțind toate valorile cu , putem obține o inegalitate similară, dar cu un semn în direcția opusă, pentru funcțiile concave .
ConsecințeleDupă reducerea ambelor părți cu , obținem din nou inegalitatea obișnuită de permutare.
După luarea exponentului din ambele părți: ;
În 1946, a fost publicată o încercare (Scripta Mathematica 1946, 12(2), 164-169) de a generaliza inegalitatea după cum urmează:
Pentru și două seturi de numere reale și , dacă numărul de inversiuni în permutare este mai mic decât în permutare . |
Cu toate acestea, mai târziu s-a dovedit că această generalizare este valabilă numai pentru . Deoarece există contraexemple pentru această generalizare, cum ar fi:
Inegalitatea de permutare este interesantă prin faptul că vă permite să combinați intuitiv pe o bază comună inegalități numerice complet diferite, utilizate în diferite domenii ale matematicii.
Această secțiune tratează seturi de numere de lungime și presupune că notația pentru denotă , adică bucle de index.
Conform inegalității de permutare, pentru orice , .
De aici rezultă un caz special al inegalității Cauci-Bunyakovsky:
În mod similar, împărțind suma peste toate deplasările posibile ale indicelui dimensional și folosind o generalizare pe mai multe permutări, se obține o inegalitate mai generală pentru numerele întregi :
Inegalitatea generală Cauci-BunyakovskyDacă valorile și sunt normalizate în așa fel încât , în consecință, se obține inegalitatea Cauchy-Bunyakovsky. Pentru a face acest lucru, este suficient să împărțiți totul la , și totul la . Deoarece inegalitatea Cauci-Bunyakovsky permite astfel de diviziuni fără a schimba adevărul, aceasta dovedește afirmația.
Inegalitatea dintre media patratică și media aritmetică este derivată elementar din cazul particular al inegalității Cauci-Bunyakovsky demonstrat mai sus.
Aritmetică și geometricăInegalitatea dintre media aritmetică și geometrică afirmă că
Înmulțind ambele părți cu și luând în considerare puterile-lea ale variabilelor, vedem că aceasta este la fel ca
Ultima inegalitate este ușor de obținut din generalizarea inegalității de permutare la mai multe permutări pt
Geometric și armonicAducem inegalitatea la aceeași formă ca cea anterioară:
Având în vedere puterile-lea ale variabilelor, obținem
Ultima inegalitate este ușor de obținut prin aplicarea directă a inegalității de permutare pentru mai multe permutări.