Елементи комбінаторики

Комбінаторика – розділ математики, який вивчає розташування об’єктів згідно з певними правилами і методи підрахунку числа можливих способів, за якими ці розташування можна зробити.

Найпростішими комбінаціями елементів є розміщення, перестановки і сполуки.

Нехай M⁽ⁿ⁾={x₁, x₂, …, x_n}— довільна n-елементна множина.

Упорядкована k-елементна підмножина множини M⁽ⁿ⁾ називається розміщенням з п елементів по k. Число всіх таких розміщень обчислюють за формулою

(1)

При k = n розміщення є перестановкою елементів множини M⁽ⁿ⁾ причому їх число дорівнює

. (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!= 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 способами.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Програма розщеплення цілих двійкових чисел на складові А і В	\|	Приклади

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.