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:
I synnerhet om , då oavsett beställning .
En konsekvens av permutationsojämlikheten är Chebyshev-ojämlikheten för summorna .
Låt oss beteckna . Som bevis är det lämpligt att omformulera uttalandet något:
Här är uppsättningen av alla möjliga permutationer , och är den identiska permutationen .
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 .
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.
Per definition,
Genom val och ordningsantagandet är ojämlikheten sann , så att .
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å .
Låt de ordnade sekvenserna ges . Låt oss beteckna . Den identiska permutationen kommer fortfarande att betecknas som .
Sedan för vilken uppsättning som helst .
BevisDet bevisas på samma sätt som den vanliga permutationsojämlikheten (ett specialfall av detta för ).
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.
Om åtminstone en av permutationerna skiljer sig från , så finns det för den (vi betecknar den med ) sådana att .
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.
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å .
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
BevisPer 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.
Som i beviset på den vanliga permutationsojämlikheten väljer vi så att .
Sedan, som beskrivits ovan . Detta möjliggör induktion liknande det vanliga fallet.
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 .
KonsekvenserEfter att ha reducerat båda delarna med får vi återigen den vanliga permutationsojämlikheten.
Efter att ha tagit utställarna från båda delarna :;
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 , Om antalet inversioner i permutationen är mindre än i permutationen . |
Men senare visade det sig att denna generalisering endast gäller för . Eftersom det finns motexempel för denna generalisering, som:
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.
Enligt permutation ojämlikhet, för alla , .
Ur detta härleds ett specialfall av Cauchy-Bunyakovsky-ojämlikheten:
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 :
Den allmänna Cauchy-Bunyakovsky ojämlikhetenOm 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.
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 geometriskaOlikheten mellan det aritmetiska och geometriska medelvärdet säger att
Om vi multiplicerar båda delarna med och tar hänsyn till variablernas th potenser ser vi att detta är detsamma som
Den sista olikheten erhålls lätt från generaliseringen av permutationsojämlikheten till flera permutationer för
Geometrisk och harmoniskVi tar ojämlikheten till samma form som den föregående:
Med tanke på variablernas e potenser får vi
Den sista olikheten är lätt att erhålla genom direkt tillämpning av permutationsolikheten för flera permutationer.