Kombinatorické principy - Combinatorial principles

Při prokazování výsledků v kombinatorika několik užitečných kombinatorická pravidla nebo kombinatorické principy jsou běžně uznávány a používány.

The pravidlo součtu, pravidlo produktu, a zásada začlenění - vyloučení jsou často používány pro enumerativní účely. Bijektivní důkazy jsou použity k prokázání, že dvě sady mají stejné počet prvků. The princip pigeonhole často zjišťuje existenci něčeho nebo se používá k určení minimálního nebo maximálního počtu něčeho v a oddělený kontext.

Mnoho kombinatorické identity vyvstat z dvojité počítání metody nebo metoda rozlišujícího prvku. Generování funkcí a relace opakování jsou výkonné nástroje, které lze použít k manipulaci se sekvencemi, a mohou popsat, pokud ne, vyřešit mnoho kombinačních situací.

Pravidlo součtu

Pravidlo součtu je intuitivní princip, který říká, že pokud existují A možné výsledky akce (nebo způsoby, jak něco udělat) a b možné výsledky pro jinou událost (nebo způsoby, jak udělat jinou věc) a tyto dvě události nemohou nastat oba (nebo tyto dvě věci nelze provést obě), pak existují a + b celkový počet možných výsledků událostí (nebo celkový počet možných způsobů provedení jedné z věcí). Více formálně, součet velikostí dvou disjunktní sady se rovná velikosti jejich svazku.

Pravidlo produktu

Pravidlem produktu je další intuitivní princip, který říká, že pokud existují A způsoby, jak něco udělat a b způsoby, jak udělat jinou věc, pak existují A · b způsoby, jak dělat obě věci.

Princip začlenění - vyloučení

Zahrnutí - vyloučení je znázorněno na třech souborech

Princip zahrnutí-vyloučení souvisí s velikostí sjednocení více množin, velikostí každé množiny a velikostí každého možného průniku množin. Nejmenší příklad je, když existují dvě sady: počet prvků v jednotce A a B se rovná součtu počtu prvků v A a B, minus počet prvků v jejich průsečíku.

Obecně podle tohoto principu, pokud A₁, ..., A_n jsou tedy konečné množiny

${ displaystyle { begin {aligned} { biggl |} bigcup _ {i = 1} ^ {n} A_ {i} { biggr |} & {} = sum _ {i = 1} ^ {n } left | A_ {i} right | - sum _ {i, j ,: , 1 leq i$

Pravidlo rozdělení

Uvádí, že existují n / d způsoby, jak provést úkol, pokud to lze provést pomocí postupu, který lze provést n způsoby, a pro každý způsob w přesně d z n způsobů odpovídá způsobu w.

Bijektivní důkaz

Bijektivní důkazy dokazují, že dvě sady mají stejný počet prvků nalezením a bijektivní funkce (korespondence 1: 1) z jedné sady do druhé.

Dvojité počítání

Dvojité počítání je technika, která rovná dva výrazy, které počítají velikost sady dvěma způsoby.

Princip holubí díry

Princip pigeonhole uvádí, že pokud A položky jsou vloženy do jednoho z b krabice, kde A > b, pak jedno z polí obsahuje více než jednu položku. Pomocí tohoto lze například demonstrovat existenci nějakého prvku v sadě s některými specifickými vlastnostmi.

Metoda rozlišujícího prvku

Metoda rozlišujícího prvku vyčleňuje „rozlišující prvek“ množiny, aby se prokázal nějaký výsledek.

Generující funkce

Generační funkce lze považovat za polynomy s nekonečně mnoha členy, jejichž koeficienty odpovídají podmínkám sekvence. Tato nová reprezentace sekvence otevírá nové metody pro hledání identit a uzavřených forem vztahujících se k určitým sekvencím. (Běžná) generující funkce sekvence A_n je

${ displaystyle G (a_ {n}; x) = součet _ {n = 0} ^ { infty} a_ {n} x ^ {n}.}$

Vztah opakování

Relace opakování definuje každý člen posloupnosti z hlediska předcházejících pojmů. Vztahy opakování mohou vést k dříve neznámým vlastnostem sekvence, ale obecně uzavřené výrazy protože pojmy sekvence jsou více žádané.

Reference

• J. H. van Lint a R. M. Wilson (2001), Kurz kombinatoriky (brožovaný), 2. vydání, Cambridge University Press. ISBN  0-521-00601-5