Permutační nerovnost nebo nerovnost o jednomonotónních sekvencích nebo „ trans- nerovnost “ říká, že tečkový součin dvou sad čísel je maximální možný, pokud jsou množiny jednomonotónní (to znamená, že obě jsou současně neklesající). nebo současně nerostoucí) a nejmenší možnou, pokud jsou množiny opačné monotonie (pak jedna je neklesající a druhá nerostoucí).
Jinými slovy, if a , pak pro libovolnou permutaci čísel platí následující nerovnost:
Zejména pokud , pak bez ohledu na pořadí .
Důsledkem permutační nerovnosti je Čebyševova nerovnost pro součty .
Označme . Pro důkaz je vhodné tvrzení poněkud přeformulovat:
Zde je množina všech možných permutací a je totožná permutace .
Hlavní myšlenkou důkazu je, že pokud pro některé , pak prohozením hodnot a nesnížíme hodnotu součtu .
Zvažte uvedený součet pro nějakou permutaci a takový pár . Zvažte permutaci vytvořenou z inverzí tohoto páru.
Podle definice,
Volbou a předpokladem uspořádání je nerovnost pravdivá , takže .
Proto můžeme snížit počet inverzí, aniž bychom snížili hodnotu (například fixací inverzí v bublinovém řazení ). V důsledku toho takový proces povede k transformaci na , takže .
Nechat dané uspořádané sekvence . Označme . Identická permutace bude stále označena jako .
Pak pro jakoukoli sadu .
DůkazDokazuje se podobně jako obvyklá permutační nerovnost (speciální případ pro ).
Bez ztráty obecnosti budeme předpokládat, že , protože jinak můžeme jednoduše vynásobit všechny permutace beze změny hodnoty součtu.
Pokud je alespoň jedna z permutací odlišná od , pak pro ni (označujeme ji ) existuje taková, že .
Pak, pokud ve všech permutacích z množiny, pro kterou jsou hodnoty \sigma (i) > \sigma (j) zaměněny , pak se hodnota nesníží, ale celkový počet inverzí mezi nimi se sníží.
Provedením takových akcí nezbytným (konečným) počtem opakování se dostaneme k množině, aniž bychom snížili hodnotu .
Myšlenka důkazu pomocí postupné korekce inverzí je použitelná pro širší třídu případů, než je pouze bodový součin.
Dovolit být konvexní funkce , a být uspořádány v non-klesající pořadí. Pak
DůkazPodle definice konvexní funkce, if , then , to je . Dosazením a přičtením obou hodnot dostaneme . Jinými slovy, čím větší je argument, tím větší je ohyb funkce směrem nahoru a tím cennější je přidat větší hodnotu, aby se maximalizoval součet.
Jako v důkazu obvyklé permutační nerovnosti volíme takovou, že .
Poté, jak je popsáno výše, . To nám umožňuje provést indukci podobnou obvyklému případu.
Vynásobením všech hodnot pomocí můžeme odvodit podobnou nerovnost, ale se znaménkem v opačném směru pro konkávní funkce .
DůsledkyPo zmenšení obou částí o , opět získáme obvyklou permutační nerovnost.
Po převzetí exponentu z obou částí: ;
V roce 1946 byl publikován pokus (Scripta Mathematica 1946, 12(2), 164-169) zobecnit nerovnost takto:
For a dvě sady reálných čísel a , pokud je počet inverzí v permutaci menší než v permutaci . |
Později se však ukázalo, že toto zobecnění platí pouze pro . Protože pro toto zobecnění existují protipříklady, jako například:
Permutační nerovnost je zajímavá tím, že umožňuje intuitivně kombinovat na společném základě navenek zcela nepodobné číselné nerovnosti používané v různých oblastech matematiky.
Tato část se zabývá sadami čísel délek a předpokládá, že zápis pro označuje , tedy indexové smyčky.
Podle permutační nerovnosti pro libovolné , .
Z toho je odvozen zvláštní případ Cauchy-Bunyakovského nerovnosti:
Podobně, rozdělením součtu přes všechny možné posuny -rozměrného indexu a použitím zobecnění přes několik permutací se získá obecnější nerovnost pro celá čísla :
Obecná Cauchy-Bunyakovského nerovnostPokud jsou hodnoty a normalizovány takovým způsobem, že v důsledku toho se získá Cauchy-Bunyakovského nerovnost. K tomu stačí vydělit vše , a vše . Vzhledem k tomu, že nerovnost Cauchy-Bunyakovského umožňuje taková rozdělení, aniž by se změnila pravda, toto tvrzení potvrzuje.
Nerovnost mezi středním kvadratickým a aritmetickým průměrem je elementárně odvozena z konkrétního případu Cauchy-Bunyakovského nerovnosti dokázaného výše.
Aritmetika a geometrickáNerovnost mezi aritmetickým a geometrickým průměrem to říká
Vynásobením obou částí a uvážením tých mocnin proměnných vidíme, že je to stejné jako
Poslední nerovnost lze snadno získat zobecněním permutační nerovnosti na několik permutací pro
Geometrické a harmonickéPřivedeme nerovnost do stejného tvaru jako předchozí:
Uvážíme -li th mocniny proměnných, dostaneme
Poslední nerovnost lze snadno získat přímou aplikací permutační nerovnosti pro několik permutací.