Правило суми

В комбінаториці правило суми — це основний комбінаторний принцип. Основна ідея, в тому, що якщо у нас A способів зробити щось одне і B способів зробити щось інше, і ми не можемо робити їх одночасно, то існує A + B способів вибрати одну з дій.

Більш формально, правило суми — є фактом теорії множин, яке полягає в тому, що сума кількостей елементів скінченного набору попарно неперетинних множин дорівнює кількості елементів об'єднання цих множин. Тобто, якщо $S_{1},S_{2},...,S_{n}$ попарно неперетинні множини, то ми маємо:

|S_{1}|+|S_{2}|+\cdots +|S_{n}|=|S_{1}\cup S_{2}\cup \cdots \cup S_{n}|

Простий приклад

Жінка вирішила сьогодні зробити покупку в одному магазині з двох: розташованому або в північній або в південній частині міста. Якщо вона відвідає північну частину міста, то вона може зробити придбання в торговому центрі, або в меблевому магазині, або у ювелірному магазині (3 способи). Якщо вона відвідає південну частину міста, то вона може зробити придбання або в магазині одягу або у взуттєвому магазині (2 способи).

Таким чином, є 3 + 2 = 5 можливих варіантів вибору магазину, в якому жінка сьогодні зробить покупки.

Принцип включення-виключення

Принцип включення-виключення можна розглядати як узагальнення правила суми на випадок, коли можливий перетин множин. Принцип для скінченних множин A₁, …, A_n стверджує, що

{\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leqslant i<j\leqslant n}\left|A_{i}\cap A_{j}\right|+\\&{}\qquad +\sum _{i,j,k\,:\,1\leqslant i<j<k\leqslant 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{aligned}}

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.