Kombinatorické principy

Při dokazování kombinatorických teorémů se obvykle uznává a používá několik užitečných kombinatorických pravidel nebo kombinatorických principů . Příklady:

Pravidlo sčítání , pravidlo násobení a princip zahrnutí-vyloučení se často používají pro účely výčtu .
Dirichletův princip často uvádí existenci něčeho nebo se používá k určení minimálního nebo maximálního množství něčeho v diskrétním kontextu .
Bijektivní důkaz se používá k zajištění toho, aby dvě množiny měly stejný počet prvků .
Mnoho kombinatorických identit vzniká z metody dvojitého počítání nebo metody rozlišujících prvků .
Generování funkcí a relace opakování jsou mocné nástroje, které lze použít k manipulaci se sekvencemi a mohou být užitečné při zkoumání mnoha kombinatorických situací.

Pravidlo sčítání

Pravidlo sčítání intuitivně říká, že pokud událost A má možné výsledky a událost B má možné výsledky a může nastat pouze jedna z těchto událostí, pak celkový počet možných výsledků je [1] . $A$ $b$ $a+b$

V jazyce teorie množin toto pravidlo znamená, že velikost sjednocení dvou disjunktních množin je rovna součtu velikostí těchto množin: if , then (dále symbol označuje počet prvků konečné množiny ) . $A\cap B=\varnothing$ $|A\cup B|=|A|+|B|$ $|A|$ $|A|$

Příklad . Pojďme zjistit, kolik trojciferných čísel obsahuje (v desítkovém zápisu) právě dvě devítky. Pro taková čísla existují tři možné formáty [2] :

9n9,n=0,1,2,\tečky ,8.

Celkem je k dispozici 9 možností.

99n,n=0,1,2,\tečky ,8.

Celkem je k dispozici 9 možností.

n99,n=1,2,3,\tečky ,8.

Pouze 8 možností.

Podle pravidla sčítání bude celkový počet takových čísel $9+9+8=26.$

Pravidlo násobení

Pravidlo násobení je další intuitivní princip, který říká, že pokud existují způsoby, jak něco udělat, a způsoby, jak nezávisle udělat něco jiného, pak existují způsoby, jak udělat obojí [1] . $A$ $b$ $ab$

Příklad [3] . K dispozici je 6 červených, 8 modrých a 10 zelených kostek. Pojďme zjistit, kolika způsoby mohou být uspořádány do dvou krabic. Červené kostky lze rozdělit do dvou polí takto:

0+6;1+5;2+4;3+3;4+2;5+1;6+0.

Pouze 7 možností.

Podobně a nezávisle na sobě modré kostky dávají 9 možností, zelené 11. Podle pravidla násobení se celkový počet možností rovná způsobu. $7\cdot 9\cdot 11=693$

Princip inkluze-exkluze

Princip inkluze-vyloučení dává do souvislosti velikost sjednocení několika množin s velikostí každé množiny a velikostí jejich možných průniků [4] . Nejjednodušší příklad: pokud existují dvě množiny, pak se počet prvků v jejich spojení rovná součtu počtu prvků v množinách mínus počet prvků v jejich průniku:

|A\cup B|=|A|+|B|-|A\cap B|

Tento vzorec zobecňuje výše uvedené pravidlo součtu. Varianta pro tři sady:

|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

V obecném případě princip říká [4] : pokud jsou konečné množiny , pak: $A_{1}\dots A_{n}$

{\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n }\left|A_{i}\right|-\součet _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right| \\&{}\qquad +\součet _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_ {k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{ zarovnaný}}

Příklad [5] . Ve skupině je 40 turistů. Z toho 20 mluví anglicky, 15 francouzsky a 11 španělsky. Sedm lidí umí anglicky a francouzsky, pět lidí umí anglicky a španělsky a tři lidé umí francouzsky a španělsky. Dva turisté mluví všemi třemi jazyky. Kolik lidí ve skupině nezná žádný z těchto jazyků? Pomocí vzorce inkluze-vyloučení vypočítáme celkový počet turistů, kteří ovládají alespoň jeden z uvedených jazyků: Odpověď tedy zní: $20+15+11-7-5-3+2=33.$ $40-33=7.$

Pravidlo dělení

Kombinatorická definice: pokud je problém řešen pomocí postupu, který lze provést různými způsoby, a pro každou metodu existují výsledky, které jsou od ní nerozeznatelné, pak existují různé způsoby dokončení úkolu. $n$ $d-1$ $n/d$

V jazyce teorie množin: je-li konečná množina spojením párově disjunktních podmnožin, z nichž každá obsahuje prvky, pak $A$ $n$ $d$ $n=|A|/d.$

V jazyce funkcí: pokud funkce mapuje konečnou množinu na konečnou množinu a předobraz každé hodnoty obsahuje přesně hodnoty z A, pak $F$ $A$ $b,$ $b\in B$ $d$ $|B|=|A|/d.$

Příklad . Kolik různých způsobů existuje, jak posadit čtyři lidi ke kulatému stolu? Metody se považují za odlišné, pokud má alespoň jedna osoba jiného souseda nalevo nebo napravo. Řešení: pokud podmínku zahodíme, tak cesty jsou, ale každá cesta má 3 "dvojčata", která se liší rotací kolem stolu a podle stavu problému jsou všechna považována za jednu cestu. V důsledku toho máme různé způsoby. $4!=24$ $24/4=6$

Dirichletův princip

Dirichletův princip v kombinatorice v nejjednodušší formulaci říká, že pokud jsou předměty umístěny v krabicích, pak alespoň jedna krabice bude obsahovat více než jeden objekt [6] . Pomocí tohoto principu a jeho zobecnění lze například demonstrovat existenci prvku v množině s některými specifickými vlastnostmi. $A$ $b$ $a>b,$

Příklad . Část společnosti lidí potřást rukou. Dokažte, že ve firmě jsou alespoň dva lidé, kteří provedli stejný počet podání rukou [7] . Důkaz . Definujme „krabice“ a vložme do krabice ty členy společnosti, kteří si podali ruku. Pokud krabice není prázdná, pak jeden nebo více členů společnosti nepodali žádné handshake, a proto je krabice prázdná, protože počet podání ruky je pak menší . Z toho vyplývá, že neprázdných je vždy méně krabice než , a proto alespoň jedna krabice odpovídá dvěma nebo více lidem. ■ $N$ $(N>1)$ $N$ ${\displaystyle H_{0},H_{1}\tečky H_{N-1))$ $H_{k}$ $k$ $H_{0}$ $H_{N-1}$ $N.$ $N,$

Bijektivní důkaz

Bijektivní důkazy se používají k důkazu, že dvě konečné množiny mají stejný počet prvků; jsou zvláště užitečné v případech, kdy je počet prvků v jedné sadě snadněji zjistitelný než v jiné. V průběhu důkazu je mezi těmito množinami sestrojena bijektivní funkce (korespondence jedna ku jedné).

Příklad . Dokažme jednu z variant Pascalova pravidla : kde a binomický koeficient zároveň charakterizuje počet -prvkových podmnožin přirozeného intervalu . Přiřaďme si každou elementární podmnožinu intervalu k této samotné podmnožině, pokud neobsahuje číslo nebo je obsahuje mínus . Je snadné ukázat, že pro každý dostaneme bijekci -prvkových podmnožin , na jedné straně a podmnožin délky a , na straně druhé. Tato skutečnost odráží Pascalovo pravidlo [8] . $C_{n+1}^{k+1}=C_{n}^{k+1}+C_{n}^{k},$ $0\leqslant k\leqslant n-1,$ ${\displaystyle C_{n}^{m))$ $m$ $\mathbb {R_{n}} =\{1,2,\tečky n\}$ $(k+1)$ $\mathbb {R_{n+1}}$ $n+1,$ $n+1,$ $k$ $(k+1)$ $\mathbb {R_{n+1}} ,$ $\mathbb {R_{n}}$ $k+1$ $k$

Metoda dvojitého počítání

Dvojité počítání je metoda, která dává rovnítko mezi dva výrazy pro velikost zkoumaného souboru, získané dvěma různými způsoby [9] . Tato metoda je mimořádně užitečná například pro získávání kombinatorických identit.

Nejjednodušší příklad (viz obrázek): počítání objektů v obdélníkové tabulce po řádcích a po sloupcích vede ke stejnému výsledku, což implikuje komutativnost násobení.

Metoda vybraného prvku

Metoda vybraného prvku označí nějaký "vybraný prvek" sady, aby se prokázal požadovaný výsledek.

Generující funkce

Generující funkcí posloupnosti je mocninná řada, jejíž koeficienty odpovídají členům dané posloupnosti. ${\displaystyle \{a_{1},a_{2},a_{3}\tečky \))$

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

Tato reprezentace často umožňuje aplikovat výkonné metody matematické analýzy na kombinatorické problémy [10] .

Relace opakování

Relace rekurence definuje každý člen posloupnosti, kromě počátečního, přes předchozí členy [11] . Příklad: Fibonacciho čísla .

Rekurentní vztahy mohou vést k dříve neznámým vlastnostem sekvence, ale obvykle jsou vhodnější výrazy v uzavřené formě pro členy sekvence.

Poznámky

↑ 1 2 Okulov, 2012 , str. 25.
↑ Kombinatorika: Pravidla součtu a součinu . Foxford . Získáno 21. listopadu 2020. Archivováno z originálu dne 21. ledna 2021. (neurčitý)
↑ Okulov, 2012 , str. 49,285.
↑ 1 2 Okulov, 2012 , str. 26-28.
↑ Jakovlev I. V. Vzorec inkluzí a výluk . Získáno 21. listopadu 2020. Archivováno z originálu dne 20. října 2019. (neurčitý)
↑ Dirichletův princip, krabice // Matematická encyklopedie (v 5 svazcích). - M .: Sovětská encyklopedie , 1982. - T. 2. - S. 182.
↑ Dirichletův princip . Získáno 30. března 2020. Archivováno z originálu dne 24. září 2020. (neurčitý)
↑ Glibichuk et al., 2016 , str. 9-10.
↑ Glibichuk et al., 2016 , str. 18-20.
↑ Okulov, 2012 , str. 90.
↑ Okulov, 2012 , str. 76.

Literatura

Glibichuk A. A., Dainyak A. B., Ilyinsky D. G., Kupavsky A. B., Raigorodsky A. M., Skopenkov A. B., Chernov A. A. Prvky diskrétní matematiky v problémech. - M. : MTSNMO, 2016. - 174 s. — ISBN 978-5-4439-3024-4 .
Okulov S. M. Diskrétní matematika. Teorie a praxe řešení problémů v informatice: učebnice. - 2. vyd. — M. : BINOM. Vědomostní laboratoř, 2012. - 422 s. - (vzdělávání učitelů). - ISBN 978-5-9963-0893-4 .
JH van Lint, RM Wilson (2001), Kurz kombinatoriky (brožovaná vazba), 2. vydání, Cambridge University Press. ISBN 0-521-00601-5 .

Odkazy

Užitečné identity v kombinatorice . Datum přístupu: 19. listopadu 2020.