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

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

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

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

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

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

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

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