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

В математиці комбінація, сполука це спосіб вибору декількох речей з більшої групи, де (на відміну від розміщення) порядок не має значення. У випадку з маленькими числами можливо підрахувати кількість сполук. Наприклад, дани три фрукти, яблуко, помаранч і груша, існують три сполуки по два фрукти, що можуть бути отримані з цього набору: яблуко і груша, яблуко і помаранч, або груша і помаранч. Формальніше 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\,.$

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

За фіксованого 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.$

Див. також

• Біноміальний коефіцієнт