Комбінація (комбінаторика)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В математиці комбінація, сполука це спосіб вибору декількох речей з більшої групи, де (на відміну від розміщення) порядок не має значення. У випадку з маленькими числами можливо підрахувати кількість сполук. Наприклад, дано три фрукти, яблуко, помаранч і груша, існують три сполуки по два фрукти, що можуть бути отримані з цього набору: яблуко і груша, яблуко і помаранч, або груша і помаранч. Формальніше k-сполука множини S це підмножина утворена k різними елементами S. Якщо множина містить n елементів, тоді кількість k-сполук дорівнює біноміальному коефіцієнту

 \binom nk = C_n^k = \frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1},

який можна записати із використанням факторіалів так \frac{n!}{k!(n-k)!} коли k\leq n, і який дорівнює нулю k>n. Множина всіх k-сполук множини S іноді записується як

\binom Sk\,.

Сполуки можуть допускати повторення, а можуть ні.[1] В попередньому прикладі повторення не дозволялись. Однак, якщо вони були б дозволені, ми мали б три додаткові сполуки: два яблука, два помаранчі і дві груші.

За фіксованого n, генератрисою послідовності чисел сполук {n\choose 0}, {n\choose 1}, {n\choose 2}, … є \sum_{k=0}^n {n\choose k} x^k = (1+x)^n.

Двовимірною генератрисою чисел сполук є \sum_{n=0}^{\infty} \sum_{k=0}^n {n\choose k} x^k y^n = \sum_{n=0}^{\infty} (1+x)^n y^n = \frac{1}{1-y-xy}.

Сума всіх сполук з k від 0 до n дорівнює \sum_{k=0}^n {n\choose k} = 2^n.

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999