Сполучення

Означення. С полученням з n елементів по m елементів називають будь-яку m-елементну підмножину n-елементної множини.

Звідси випливає, що сполучення з n елементів по m елементів - це всі m-елементні підмножини n-елементної множини, причому різними підмножинами вважаються ті, склад яких відрізняється хоч би одним елементом. Підмножини, які відрізняються між собою лише порядком слідування елементів, не є різними. Отже, комбінації на відміну від розміщень, - це невпорядковані підмно­жини даної множини.

Кількість всіх сполучень з n елементів по m елементів поз­начають символом (читають: "число комбінацій з n по m" або "це із n по m). С - перша буква французького слова combinasion - комбінація. Для сполучень m£n.

Для обчислення числа сполучень з n елементів по m елемен­тів існує декілька формул.

Теорема 5. Для довільних натуральних n i m (m£n) має місце формула

= (1)

Доведення. Спочатку утворимо всі можливі неупорядковані m-елементні підмножини n-елементної множини, їх число дорівнює . Потім з кожної одержаної m-елементної підмножини перестанов­кою її елементів одержимо всі упорядковані m-елементні підмножи­ни, яких буде у m! раз більше, бо кожну m-елементну підмножину можна упорядкувати m! способами. Отже, дістанемо

=m! ,

а звідси =

Цю теорему можна довести іншими способами, зокрема методом мате­матичної індукції.

Формулу (1) для числа комбінацій можна записати в іншому вигляді. Якщо чисельник і знаменник її помножити на (n-m)!, то дістанемо:

(2)

Число має ряд цікавих i важливих у практичних застосу­ваннях властивостей, які подамо у вигляді теорем.

Теорема 6. Для довільних натуральних n і m (m£n) справджує­ться рівність

= (3)

Доведення. Рівність (3) безпосередньо випливає з формули (2). Справді,

=

Теорема 7. Для довільних натуральних m i n (m£n) справджу­ється рівність

+ = (4)

Доведення. Використаємо формулу (2):

+ + =

= =

= .

Наслідок 1. Формулу (4) при розв'язуванні задач зручно ін­коли використовувати в такому вигляді:

+ = , (5)

яка є наслідком формули(4).

Формулу (5) називають ще формулою Паскаля.

Наслідок 2. Число комбінацій з nелементів по m елементів виражаєть­ся через: а) число розміщень в n елементів по m елементів форму­лою

= -наслідок з (1);