Bijektivní důkaz

v kombinatorika, bijektivní důkaz je důkaz technika, která najde a bijektivní funkce (tj jedna ku jedné a na funkce) $F : A \to B$ mezi dvěma konečné množiny $A$ a $B$ nebo bijektivní funkce zachovávající velikost mezi dvěma kombinatorické třídy, což dokazuje, že mají stejný počet prvků, $| A | = | B |$ . Jedno místo, kde je tato technika užitečná, je místo, kde chceme znát její velikost $A$ , ale nemůže najít žádný přímý způsob počítání jeho prvků. Stanovením bijekce z $A$ některým $B$ řeší problém, pokud $B$ je snadněji spočítatelné. Další užitečnou vlastností této techniky je, že samotná podstata bijekce často poskytuje mocný vhled do každé nebo obou sad.

Základní příklady

Prokazování symetrie binomických koeficientů

Symetrie binomických koeficientů to říká

{ displaystyle {n zvolit k} = {n zvolit n-k}.}

To znamená, že je přesně tolik kombinace z $k$ věci v sadě velikostí $n$ protože existují kombinace $n - k$ věci v sadě velikostí $n$ .

Klíčovou myšlenku důkazu lze pochopit z jednoduchého příkladu: výběr ze skupiny $n$ děti, které $k$ odměna kornouty na zmrzlinu má přesně stejný účinek jako volba místo $n - k$ dětem, které jim mají být odepřeny.

Více abstraktně a obecně,^[1] dvě tvrdená množství, která se rovnají, počítají podmnožiny velikosti $k$ a $n - k$ , respektive jakékoli $n$ - sada prvků $S$ . Nechat $A$ být množinou všeho $k$ -prvkové podmnožiny $S$ , sada $A$ má velikost ${ displaystyle { tbinom {n} {k}}.}$ Nechat $B$ být množinou všeho $n - k$ podmnožiny $S$ , sada B má velikost ${ displaystyle { tbinom {n} {n-k}}}$ . Mezi oběma sadami existuje jednoduchá bijekce $A$ a $B$ : sdružuje všechny $k$ - podmnožina prvku (tj. člen $A$ ) s jeho doplněk, který obsahuje přesně zbývající $n - k$ prvky $S$ , a proto je členem $B$ . Formálně to lze napsat pomocí funkční notace tak jako, $F : A \to B$ definován $F (X) = X C$ pro $X$ žádný $k$ - podmnožina prvků $S$ a doplněk přijatý $S$ . Chcete-li ukázat, že f je bijekce, nejprve to předpokládejte $F (X 1) = F (X 2)$ , to znamená, $X 1 C = X 2 C$ . Vezměte doplňky každé strany (v $S$ ), s využitím skutečnosti, že doplněk doplňku sady je původní množina, získat $X 1 = X 2$ . To ukazuje $F$ je jedna ku jedné. Nyní si vezměte $n - k$ - podmnožina prvků $S$ v $B$ , řekněme $Y$ . Jeho doplněk v $S$ , $Y C$ , je $k$ - podmnožina prvku, a tedy prvek $A$ . Od té doby $F (Y C) = (Y C) C = Y$ , $F$ je také na a tedy bijekce. Výsledek nyní následuje, protože existence bijekce mezi těmito konečnými množinami ukazuje, že mají stejnou velikost, tj. ${ displaystyle { tbinom {n} {k}} = { tbinom {n} {n-k}}}$ .

Další příklady

Problémy, které připouštějí bijektivní důkazy, se neomezují pouze na identitu binomického koeficientu. Jak se složitost problému zvyšuje, bijektivní důkaz může být velmi sofistikovaný. Tato technika je zvláště užitečná v oblastech diskrétní matematika jako kombinatorika, teorie grafů, a teorie čísel.

Mezi nejklasičtější příklady bijektivních důkazů v kombinatorice patří:

Prüferova sekvence, což dokazuje Cayleyův vzorec pro počet označené stromy.
Robinson-Schenstedův algoritmus, což dokazuje Burnside vzorec pro symetrická skupina.
Časování z Mladé diagramy, což dokazuje klasický výsledek o počtu jistých celočíselné oddíly.
Bijektivní důkazy věta o pětiúhelníku.
Bijektivní důkazy o vzorci pro Katalánská čísla.

Viz také

Reference

^ Mazur, David R. (2010), Kombinatorika / Prohlídka s průvodcem„The Mathematical Association of America“, s. 28, ISBN 978-0-88385-762-5

Další čtení

Loehr, Nicholas A. (2011). Bijective Combinatorics. CRC Press. ISBN 143984884X, ISBN 978-1439848845.

externí odkazy

"Dělení třemi" - Doyle a Conway.
„Přímý bijektivní důkaz vzorce délky háku“ - Novelli, Pak a Stojanovskij.
„Sčítání bijektů a náhodné generování euleriánských planárních map s předepsanými stupni vrcholů“ - Gilles Schaeffer.
„Konstruktivní důkaz unimodality gaussovských polynomů Kathy O'Hary“ - od Doron Zeilberger.
„Partition Bijections, an Survey“ - od Igor Pak.
Princip involuce Garsia-Milne - z MathWorld.

[1] Mazur, David R. (2010), Kombinatorika / Prohlídka s průvodcem„The Mathematical Association of America“, s. 28, ISBN 978-0-88385-762-5

[1]