5.1.4. Сполучення

Кількість строго монотонних функцій або число розміщень n нерозрізнених предметів по m ящиках, не більш ніж по одному в ящик, тобто число способів вибрати з m ящиків n ящиків із предметами, називається кількістю сполучень і позначається С(m,n) або ( )

.

Розглянемо доказ.

1. Кількість розміщень без повторень потрібно розділити на кількість перестановок, оскільки предмети не помітні.

2. Кількість сполучень є кількістю строго монотонних функцій. Тому що строго монотонна функція F:1..n→1..m визначається набором своїх значень, причому 1 ≤ F(1) < ··· < F(n) ≤ m. Іншими словами, кожна строго монотонна функція визначається вибором n чисел із діапазону 1...m. Таким чином, кількість строго монотонних функцій дорівнює кількісті n-елементних підмножин m-елементної множини, що, у свою чергу, дорівнює кількості способів вибрати n ящиків із предметами з m ящиків.

За визначенням С(m,n):=0 при n>m.

Приклад. На початку гри в доміно кожному гравцю видається 7 кісток із наявних 28 різноманітних кісток. Скільки існує різноманітних комбінацій кісток, що гравець може одержати на початку гри? Очевидно, що шукане число дорівнює числу 7-елементних підмножин 28-елементної множини. Маємо

.

5.1.5. Сполучення з повтореннями

Кількість монотонних функцій або кількість розміщень n нерозрізнених предметів по m ящиках називається кількістю сполучень із повтореннями і позначається V(m,n)

V(m, n)=C(n+m-1, n).

Доказ цієї формули має такий вигляд.

Монотонній функції f:{1, ... , n}→{1, ... , m} однозначно відповідає строго монотонна функція f´:{1, ... , n}→{1, ... , n+m-1}.

Приклад. Скількома засобами можна розсадити n щойно прибулих гостей серед m гостей, які уже сидять за круглим столом? Очевидно, що між m гостями, які вже сидять за круглим столом, є m проміжків, в які можна розсаджувати щойно прибулих. Таким чином, це можна зробити способами.

5.2. Підстановки

У цьому розділі розглядаються підстановки і перестановки, що насправді є рівнозначними поняттями. Для обчислення кількості перестановок у підрозділі 5.1.3 встановлена дуже проста формула Р(n)=n! Застосовуючи цю формулу при розв'язанні практичних завдань, не варто забувати, що факторіал - це функція, яка дуже швидко зростає, зокрема, факторіал росте швидше експоненти. Дійсно, використовуючи відому з математичного аналізу формулу Стірлінга

або, більш точно,

неважко показати, що

5.2.1. Група підстановок

Взаємно однозначна функція f : X→X називається підстановкою на Х.

Якщо множина Х звісно (:Х:= n), то, не обмежуючи спільності, можна вважати, що Х=1...n зручно задавати таблицею з двох рядків. У першому рядку - значення аргументів, в іншому відповідні значення функції

Добутком підстановок f і q називається їхня суперпозиція f  q.

Приклад

.

Тотожна підстановка - це підстановка е, така що е (х)=х.

Приклад

.

Обернена підстановка - це обернена функція, що завжди існує, оскільки підстановка є біекцією. Таблицю оберненої підстановки можна одержати, якщо просто поміняти місцями рядки таблиці вихідної підстановки.

Приклад

.

Таким чином, множина підстановок утворить групу щодо операції суперпозиції. Ця група називається симетричною групою ступеня n.