Комбінаторика – розділ математики, який вивчає розташування об’єктів згідно з певними правилами і методи підрахунку числа можливих способів, за якими ці розташування можна зробити.
Найпростішими комбінаціями елементів є розміщення, перестановки і сполуки.
Упорядкована k-елементна підмножина множини M(n) називається розміщенням з п елементів по k. Число всіх таких розміщень обчислюють за формулою
(1)
При k = n розміщення є перестановкою елементів множини M(n) причому їх число дорівнює
. (2)
Розміщення вважаються різними, якщо вони відрізняються складом елементів або порядком їх розташування.
Будь-яка невпорядкована k-елементна підмножина множини M називається сполукою з n елементів по k. Число різних таких сполук позначається символом і обчислюється за формулою
. (3)
Числа є коефіцієнтами в розкладі бінома Ньютона:
(4)
де a, bÎR, nÎN.
Сполуки вважаються різними, якщо вони відрізняються складом елементів.
Наприклад, нехай маємо множину М = {1, 2, 3}. Розміщеннями по два елементи є (1, 2), (1, 3), (2, 3), (2, 1), (3, 1) і (3, 2), а їх число . Перестановками елементів множини М є (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) і (3, 2, 1), а їх число П3=3!= 1·2·3= 6. Сполуками по два елементи є (1, 2), (1, 3) і (2, 3), а їх число .
Число різних розміщень з повтореннями з n елементів по k обчислюють за формулою
. (5)
Для множини М = {1, 2, 3} число розміщень з повтореннями по 2 елементи є . До розглянутих вище розміщень (без повторень) слід додати ще такі: (1, 1), (2, 2), (3, 3).
Число різних сполук з повтореннями з n елементів по k визначають за формулою
(6)
Для множини М = {1, 2, 3} сполуками з повтореннями по 2 елементи будуть такі (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2,3), а їх число
Основні властивості розміщень і сполук
а) . (7)
Правило добутку. Якщо об'єкт А із сукупності об’єктів можна вибрати k способами і після кожного з цих виборів об'єкт В, в свою чергу, можна вибрати l способами, то вибір А і В можна здійснити kl способами.