Bijektivní důkaz

Bijektivní důkaz je důkazová technika , která najde bijektivní funkci f : A → B mezi dvěma konečnými množinami A a B nebo bijektivní funkci zachovávající velikost mezi dvěma kombinatorickými třídami , která dokazuje stejný počet prvků, | A | = | B |. Místo, kde je tato technika užitečná, je, když chceme znát velikost A , ale nemůžeme najít přímý způsob, jak spočítat prvky sady. V tomto případě vytvoření bijekce mezi A a nějakou množinou B vyřeší problém, pokud je počet prvků množiny B snazší vypočítat. Další užitečnou vlastností této techniky je, že samotná povaha bijekce často poskytuje silné informace o každé ze dvou množin.

Základní příklady

Důkaz symetrie binomických koeficientů

Symetrie binomických koeficientů říká, že

{n \choose k}={n \choose nk}.

To znamená, že z množiny obsahující n prvků existuje přesně tolik kombinací k prvků , kolik je kombinací n − k prvků.

Bijektivní důkaz

Všimněte si, že dvě veličiny, pro které dokazujeme rovnost, počítají počet podmnožin o velikosti k a n − k , v tomto pořadí libovolné n -prvkové množiny S . Mezi dvěma rodinami F k a F n − k podmnožin S existuje jednoduchá bijekce — vztahuje každou k -prvkovou podmnožinu k jejímu doplňku , který obsahuje právě zbývajících n − k prvků S . Protože F k a F n − k mají stejný počet prvků, musí být odpovídající binomické koeficienty stejné.

Rekurentní vztah Pascalova trojúhelníku

{\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k))

pro

1\leq k\leq n-1.

Bijektivní důkaz

Důkaz . Spočítáme počet způsobů, jak vybrat k prvků z n -prvkové množiny. Opět, podle definice, levá strana rovnosti je rovna počtu způsobů, jak vybrat k prvků z n . Protože 1 ≤ k ≤ n − 1, můžeme fixovat prvek e z n -prvkové množiny, takže zbývající podmnožina není prázdná. Pro každou množinu k -prvků, je-li zvoleno e , existuje

{n-1 \choose k-1}

způsoby, jak vybrat zbývajících k − 1 prvků ze zbývajících n − 1 možností. Jinak existuje

{\displaystyle {n-1 \vyberte k))

způsoby, jak vybrat zbývajících k prvků ze zbývajících n − 1 možností. Pak existuje

{\displaystyle {n-1 \choose k-1}+{n-1 \choose k))

způsobů výběru k prvků. $\Box$

Další příklady

Problémy, které umožňují kombinatorický důkaz, nejsou omezeny na binomické koeficienty. Se zvyšující se složitostí problému se kombinatorický důkaz stává stále sofistikovanějším. Technika bijektivního důkazu je užitečná v oblastech diskrétní matematiky , jako je kombinatorika , teorie grafů a teorie čísel .

Nejklasičtější příklady bijektivních důkazů v kombinatorice jsou:

Pruferův kód poskytující důkaz Cayleyho vzorce pro počet označených stromů .
Algoritmus Robinson-Schoenstead , který poskytuje důkaz Burnsideova vzorce pro symetrickou grupu .
Konjugace Youngových diagramů , poskytující důkaz klasického výsledku na počtu některých oddílů celých čísel .
Bijektivní důkazy věty o pětiúhelníkových číslech .
Bijektivní důkazy vzorce pro katalánská čísla .

Viz také

Binomická věta
Cantor-Bernsteinova věta
Dvojité počítání (technika důkazu)
kombinatorické principy
Kombinační důkaz
Kategorizace

Poznámky

Literatura

Nicholas A. Loehr. Bijektivní kombinatorika . - CRC Press, 2011. - ISBN 978-1439848845 . Archivováno z originálu 23. října 2015.

Odkazy

"Dělení třemi" - Doyle a Conway .
„Přímý bijektivní důkaz vzorce délky háčku“ – od Novelli, Pak a Stoyanovsky.
„Bijektivní sčítání a náhodné generování eulerovských rovinných map s předepsanými vrcholovými stupni“ – Gilles Schaeffer.
„Konstruktivní důkaz Unimodality Gaussových polynomů Kathy O'Hara“ – Doron Zeilberger.
"Rozdělení Bijekce, průzkum" - Igor Pak.
Garsia-Milneův princip involuce – z MathWorld .