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

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

${\displaystyle {\binom {n}{k}}=C_{n}^{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}},}$

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

${\displaystyle {\binom {S}{k}}\,.}$

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

Число комбінацій з повтореннями з n по k дорівнює числу комбінацій без повторень з (n+k-1) по k.

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

Двовимірною генератрисою чисел сполук є ${\displaystyle \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 дорівнює ${\displaystyle \sum _{k=0}^{n}{n \choose k}=2^{n}.}$