W matematyce , A dowód z bijekcji (lub dowód przez bijekcji ) jest dowodem techniką, która polega na uzyskaniu równość dwóch wyrażeń całkowitą od wykazuje bijection dwóch zestawów, z których dwa są z wyrażenia Cardinals . Innymi słowy, badamy dwa skończone zbiory X i Y , liczymy je i za pomocą bijeksji z X na Y dedukujemy, że wyniki obliczeń są równe.
Dowód często przedstawia się mówiąc, że problem wyliczenia został przekształcony w problem równoważny.
Gałąź kombinatoryki, która w szczególności zajmuje się badaniem dowodów przez bijekcję, nazywa się kombinatoryką bijektywną .
Jeśli dowolnej części X zbioru E z n elementami skojarzymy jej charakterystyczną funkcję określoną przez si , = 0, w przeciwnym razie otrzymujemy bijekcję między częściami E i mapami E w {0,1}. Ponieważ istnieją mapy od E do {0,1}, zbiór E ma części.
Symetrię współczynników dwumianowych wyraża wzór:
.Innymi słowy, nie są dokładnie tak, jak wielu kombinacjach z k elementów spośród n jak istnieją kombinacje n - k elementów spośród n .
Dowód przez bijekcjajest liczbą elementów zbioru części o k elementach zbioru E o n elementach. Obecnie jest to prosty korespondencji pomiędzy i który łączy każdą część k elementy jego komplementarne , które zawierają dokładnie n - k pozostałe elementy E . Na przykład w zbiorze E = {a, b, c, d, e} możemy powiązać część {a, c} z jej dopełnieniem {b, d, e} . Wnioskujemy, że jest tyle części o k elementach, ile jest części o nk elementach, a zatem odpowiadające im współczynniki dwumianowe są równe.
To jest relacja, ważna dla :
.Dowód przez bijekcjaPierwsza suma to liczba części E , zbiór n elementów o parzystej liczbie elementów, a druga to liczba części o nieparzystej liczbie.
Po ustaleniu elementu a z E, uzyskujemy bijekcję między częściami parzystymi i nieparzystymi przez przypisanie części parzystej X części otrzymanej przez dodanie a, jeśli X go nie zawiera, i usunięcie go z niej, jeśli ją zawiera. To potwierdza związek.
Oto kilka klasycznych przykładów dowodów bijekcyjnych w analizie kombinatorycznej:
Dowód przez podwójnego liczenia polega na liczeniu liczby elementów tego samego zestawu na dwa różne sposoby, do ustanowienia równości powstałych wyrażeń.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">