Overordnet bevis

Et bijektivt bevis er en bevisteknik , der finder en bijektiv funktion f : A → B mellem to endelige mængder A og B eller en størrelsesbevarende bijektiv funktion mellem to kombinatoriske klasser , som beviser det samme antal elementer, | A | = | B |. Det sted, hvor teknikken er nyttig, er, når vi gerne vil vide størrelsen af A , men ikke kan finde en direkte måde at tælle sættets elementer på. I dette tilfælde løser det at etablere en bijektion mellem A og nogle mængder B problemet, hvis antallet af elementer i mængde B er lettere at beregne. En anden nyttig egenskab ved denne teknik er, at arten af selve bijektionen ofte giver kraftfuld information om hvert af de to sæt.

Grundlæggende eksempler

Bevis for symmetrien af binomiale koefficienter

Symmetrien af binomiale koefficienter siger det

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

Det betyder, at der er nøjagtig lige så mange kombinationer af k elementer fra en mængde, der indeholder n elementer, som der er kombinationer af n − k elementer.

Bijective proof

Bemærk, at de to størrelser, for hvilke vi beviser lighed, tæller antallet af delmængder af henholdsvis størrelsen k og n − k af enhver n -elementmængde S . Der er en simpel bijektion mellem to familier Fk og Fn − k af delmængder af S — den relaterer hver k - elementdelmængde til dens komplement , som indeholder nøjagtigt de resterende n − k elementer af S. Da F k og F n − k har det samme antal elementer, skal de tilsvarende binomiale koefficienter være ens.

Gentagelsesrelation af Pascals trekant

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

til

1\leq k\leq n-1.

Bijective proof

Bevis . Vi tæller antallet af måder at vælge k elementer fra et n -elementsæt. Igen, per definition, er venstre side af ligheden lig med antallet af måder at vælge k elementer fra n på . Da 1 ≤ k ≤ n − 1, kan vi fiksere et element e fra en n -elementmængde, så den resterende delmængde ikke er tom. For hvert k -elementsæt, hvis e er valgt, er der

{n-1 \choose k-1}

måder at vælge de resterende k − 1 elementer blandt de resterende n − 1 muligheder. Ellers er der

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

måder at vælge de resterende k elementer blandt de resterende n − 1 muligheder. Så er der

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

måder at vælge k elementer på. $\Boks$

Andre eksempler

Problemer, der tillader kombinatorisk bevis, er ikke begrænset til binomiale koefficienter. Efterhånden som problemets kompleksitet øges, bliver det kombinatoriske bevis mere og mere sofistikeret. Teknikken med bijektiv bevis er nyttig inden for områder af diskret matematik såsom kombinatorik , grafteori og talteori .

De mest klassiske eksempler på bijektive beviser i kombinatorik er:

En Prufer-kode, der giver et bevis på Cayleys formel for antallet af mærkede træer .
Robinson-Schoenstead-algoritmen , som giver et bevis på Burnside -formlen for den symmetriske gruppe .
En konjugation af unge diagrammer , der giver et bevis på et klassisk resultat på antallet af nogle partitioner af heltal .
Bijektive beviser for sætningen om femkantede tal .
Bijektive beviser for formlen for de catalanske tal .

Se også

Binomial sætning
Cantor-Bernsteins sætning
Dobbelttælling (bevisteknik)
kombinatoriske principper
Kombinatorisk bevis
Kategorisering

Noter

Litteratur

Nicholas A. Loehr. Bijective Combinatorics . - CRC Press, 2011. - ISBN 978-1439848845 . Arkiveret fra originalen den 23. oktober 2015.