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:
Især hvis , så uanset bestilling .
En konsekvens af permutationsuligheden er Chebyshev-uligheden for summerne .
Lad os betegne . Til beviset er det praktisk at omformulere påstanden noget:
Her er sættet af alle mulige permutationer , og er den identiske permutation .
Hovedideen med beviset er, at hvis for nogle , så ved at bytte værdierne af og , vil vi ikke mindske værdien af summen .
Overvej den angivne sum for en eller anden permutation og sådan et par . Overvej permutationen dannet fra inversionerne af dette par.
Per definition,
Ved valg og ordensantagelsen er uligheden sand , således at .
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å .
Lad givne ordnede sekvenser . Lad os betegne . Den identiske permutation vil stadig blive betegnet som .
Så for ethvert sæt .
BevisDet bevises på samme måde som den sædvanlige permutationsulighed (et særligt tilfælde af dette for ).
Uden tab af generalitet vil vi antage, at , for ellers kan vi simpelthen gange alle permutationer med uden at ændre værdien af summen.
Hvis mindst en af permutationerne er forskellig fra , så eksisterer der for den (vi betegner det med ) sådan at .
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.
Ved at udføre sådanne handlinger det nødvendige (endelige) antal gange, kommer vi til sættet uden at formindske værdien af .
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
BevisPer 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.
Som i beviset for den sædvanlige permutationsulighed vælger vi sådan, at .
Så, som beskrevet ovenfor . Dette giver os mulighed for at udføre en induktion svarende til det sædvanlige tilfælde.
Ved at gange alle værdier med , kan vi udlede en lignende ulighed, men med et fortegn i den modsatte retning, for konkave funktioner .
KonsekvenserEfter at have reduceret begge dele med , opnår vi igen den sædvanlige permutationsulighed.
Efter at have taget eksponenten fra begge dele: ;
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 , hvis antallet af inversioner i permutationen er mindre end i permutationen . |
Senere viste det sig dog, at denne generalisering kun gælder for . Da der er modeksempler på denne generalisering, såsom:
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.
Ifølge permutation ulighed, for enhver , .
Heraf udledes et særligt tilfælde af Cauchy-Bunyakovsky-uligheden:
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 :
Den generelle Cauchy-Bunyakovsky ulighedHvis 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.
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 geometriskUligheden mellem det aritmetiske og geometriske middelværdi angiver det
Hvis vi multiplicerer begge dele med og betragter variablernes th potenser, ser vi, at dette er det samme som
Den sidste ulighed opnås let fra generaliseringen af permutationsuligheden til flere permutationer for
Geometrisk og harmoniskVi bringer uligheden til samme form som den foregående:
I betragtning af variablenes th potenser får vi
Den sidste ulighed er let at opnå ved direkte anvendelse af permutationsuligheden for flere permutationer.