Kombinatoriska principer

För att bevisa resultat i kombinatorik erkänns och används ofta flera användbara kombinatoriska regler eller kombinatoriska principer .

Regeln om summa , regel för produkt och principen om inkludering och uteslutning används ofta i uppräkningssyfte . Bijektiva bevis används för att visa att två uppsättningar har samma antal element . Duvhålsprincipen fastställer ofta existensen av något eller används för att bestämma minsta eller maximala antalet av något i ett diskret sammanhang .

Många kombinatoriska identiteter uppstår från dubbelräkningsmetoder eller metoden för distinguished element . Genererande funktioner och återkommande relationer är kraftfulla verktyg som kan användas för att manipulera sekvenser, och kan beskriva om inte lösa många kombinatoriska situationer.

Summaregel

Huvudartikel: Summaregel

Summaregeln är en intuitiv princip som säger att om det finns ett möjligt utfall för en händelse (eller sätt att göra något) och b möjliga utfall för en annan händelse (eller sätt att göra en annan sak), och de två händelserna kan inte båda inträffa ( eller att de två sakerna inte kan göras båda två), så finns det a + b totalt möjliga utfall för händelserna (eller totalt möjliga sätt att göra en av sakerna). Mer formellt är summan av storlekarna av två disjunkta uppsättningar lika med storleken på deras förening.

Produktens regel

Huvudartikel: Produktregel

Produktens regel är en annan intuitiv princip som säger att om det finns ett sätt att göra något och b sätt att göra en annan sak, så finns det a · b sätt att göra båda sakerna.

Principen för inkludering–uteslutning

Inkludering–uteslutning illustreras för tre uppsättningar

Huvudartikel: Principen för inkludering–uteslutning

Inklusions-exkluderingsprincipen relaterar storleken på föreningen av flera uppsättningar, storleken på varje uppsättning och storleken på varje möjlig skärningspunkt mellan uppsättningarna. Det minsta exemplet är när det finns två uppsättningar: antalet element i föreningen av A och B är lika med summan av antalet element i A och B , minus antalet element i deras skärningspunkt.

I allmänhet, enligt denna princip, om A ₁ , …, A _n är ändliga mängder, då

${\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|&{}=\sum _{i=1}^{n}\left| A_{i}\right|-\summa _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{ }\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\ höger|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}$

Indelningsregeln

Huvudartikel: Rule of division (combinatorics)

Indelningsregeln säger att det finns n/d sätt att utföra en uppgift om det kan göras med en procedur som kan utföras på n sätt, och för varje sätt w, exakt d av n sätten motsvarar sätt w.

Opiniskt bevis

Huvudartikel: Bijective proof

Bijektiva bevis bevisar att två mängder har samma antal element genom att hitta en bijektiv funktion (en-till-en-korrespondens) från den ena mängden till den andra.

Dubbelräkning

Huvudartikel: Dubbelräkning (bevisteknik)

Dubbelräkning är en teknik som likställer två uttryck som räknar storleken på en mängd på två sätt.

Duvhålsprincip

Huvudartikel: Pigeonhole-principen

Duvhålsprincipen säger att om ett föremål placeras i en av b lådor, där a > b , så innehåller en av lådorna mer än ett föremål. Genom att använda detta kan man till exempel visa att det finns ett element i en uppsättning med vissa specifika egenskaper.

Metod för särskiljande element

Huvudartikel: Metod för distinguished element

Metoden för distinguished element pekar ut ett "distinguished element" i en uppsättning för att bevisa något resultat.

Genererande funktion

Huvudartikel: Genererande funktion

Genererande funktioner kan ses som polynom med oändligt många termer vars koefficienter motsvarar termer i en sekvens. Denna nya representation av sekvensen öppnar upp för nya metoder för att hitta identiteter och slutna former som hänför sig till vissa sekvenser. Den (vanliga) genererande funktionen för en sekvens a _n är

$G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.$

Återkommande förhållande

Huvudartikel: Återkommande relation

En återkommande relation definierar varje term i en sekvens i termer av de föregående termerna. Återkommande relationer kan leda till tidigare okända egenskaper hos en sekvens, men i allmänhet är uttryck i sluten form för termerna i en sekvens mer önskvärda.

•   van Lint, JH; Wilson, RM (2001). A Course in Combinatorics (2nd ed.). Cambridge University Press. ISBN 0-521-00601-5 .