Bevis

Ett bijektivt bevis är en bevisteknik som hittar en bijektiv funktion f  : A → B mellan två finita mängder A och B eller en storleksbevarande bijektiv funktion mellan två kombinatoriska klasser , som bevisar samma antal element, | A | = | B |. Platsen där tekniken är användbar är när vi vill veta storleken på A , men inte kan hitta ett direkt sätt att räkna elementen i uppsättningen. I det här fallet löser problemet med att upprätta en bijektion mellan A och någon mängd B om antalet element i mängd B är lättare att beräkna. En annan användbar egenskap hos denna teknik är att själva bijektionens karaktär ofta ger kraftfull information om var och en av de två uppsättningarna.

Grundläggande exempel

Bevis på symmetri av binomialkoefficienter

Symmetrin av binomialkoefficienter säger att

Det betyder att det finns exakt lika många kombinationer av k element från en mängd som innehåller n element som det finns kombinationer av n  −  k element.

Bijective proof

Observera att de två kvantiteterna för vilka vi bevisar likhet räknar antalet delmängder av storleken k respektive n  −  k , av varje n -elementuppsättning S . Det finns en enkel bijektion mellan två familjer Fk och Fn  −  k av delmängder av S — den relaterar varje k - elementdelmängd till dess komplement , som innehåller exakt de återstående n  −  k elementen av S. Eftersom F k och F n  −  k har samma antal element måste motsvarande binomialkoefficienter vara lika.

Återkommande relation för Pascals triangel

för Bijective proof

Bevis . Vi räknar antalet sätt att välja k element från en n -elementuppsättning. Återigen, per definition, är den vänstra sidan av likheten lika med antalet sätt att välja k element från n . Eftersom 1 ≤ k ≤ n − 1 kan vi fixera ett element e från en n -elementmängd, så att den återstående delmängden inte är tom. För varje k -elementuppsättning, om e väljs, finns det

sätt att välja de återstående k  − 1 elementen bland de återstående n  − 1 möjligheterna. Annars finns det

sätt att välja de återstående k elementen bland de återstående n − 1 möjligheterna. Sedan finns det

sätt att välja k element.

Andra exempel

Problem som tillåter kombinatoriskt bevis är inte begränsade till binomialkoefficienter. I takt med att problemets komplexitet ökar blir det kombinatoriska beviset mer och mer sofistikerat. Tekniken med bijektivt bevis är användbar inom områden av diskret matematik som kombinatorik , grafteori och talteori .

De mest klassiska exemplen på bijektiva bevis i kombinatorik är:

Se även

Anteckningar

Litteratur

Länkar