1.3. Перестановки, сполучення, розміщення
Комбінаторика (the combinatorics) це розділ елементарної алгебри, в якому вивчаються деякі операції над скінченними множинами і розв'язуються задачі, пов'язані з цими операціями.
Слово «комбінаторика» вперше зустрічається в «Міркуваннях про комбінаторне мистецтво» роботі двадцятирічного Лейбніца (1666 р.), яка стала початком цього розділу математики як самостійної науки.
«Міркування» Лейбніца містило ряд теорем про сполучення та перестановки, але, крім того, автор проголошував дуже широку застосовуваність нової науки до таких різноманітних предметів, як змішування кольорів, логіка, геометрія, військове мистецтво, граматика, юриспруденція, медицина і богослов'я. Лейбніц обмірковував грандіозний задум комбінаторики, вважаючи, що так само як звичайна математика займається великим і малим, цілим і частиною, так комбінаторика повинна займатися однаковим і різним, схожим і несхожим, абсолютним і відносним місцем розташування.
Поняття множини одне з понять, яке не визначається в математиці. Наприклад, множина натуральних чисел; множина простих чисел. Об'єкти, з яких складається множина, називаються елементами цієї множини. Множина, що складається зі скінченного числа елементів, називається скінченною. Такими множинами є: множина всіх двозначних чисел, множина вершин даного многокутника і множина його діагоналей. Множина, яка містить необмежену кількість елементів, називається нескінченною. Нескінченною множиною є множина всіх натуральних чисел; всіх простих чисел. Множина, яка не містить елементів, називається пустою множиною.
I. Перестановки
Нехай є множина М, яка складається із n елементів: а1, a2, а3,…, аn. Якщо переставляти ці елементи можливими способами, залишаючи незмінним їх загальне число, одержуємо декілька послідовностей: а1, а2, а3,…,аn,…,аn-1,аn-2,…, а1 і т. д. Кожна з таких послідовностей є перестановкою із даних n елементів.
Перестановкою (the permutation) із n елементів називається будь-яка скінченна послідовність (progression), яка одержується в результаті упорядкування деякої скінченної множини, складеної з n елементів. Число всіх перестановок із n елементів позначається Рn. Це число дорівнює добутку всіх цілих чисел від 1 до n. Позначають:
.
Добуток n перших натуральних чисел прийнято позначати символом n!
Символ n! читають "eн факторіал". Це слово походить від латинського factor, що означає “множник”. При n=1 у виразі 
залишається одне число 1. Тому приймається (як визначення), що 1!=1. При n=0 вираз 
немає змісту, з числа 0 існує одне переміщення, тому приймається, що 0!=1. Значить, Рn=n! правильна формула 
.
Приклад. Якою кількістю способів можна розсадити 8 студентів в ряд з 8 місць:
.
II Сполучення (комбінації)
Нехай є множина М, яка складається з n різних елементів. Будь-яка підмножина множини М, яка містить k елементів (k=0, 1, 2, ..., n), називається сполученням (combination) або комбінацією з даних n елементів по k елементів, якщо ці підмножини відрізняються хоча б одним елементом. Число різних сполучень із n елементів по k позначається 
(combination від combinare лат. сполучати). Іноді замість 
пишуть (
).
Приклад. Із множини цифр 1, 2, 3, 4 можна утворити такі сполучення по два елементи: 1,2; 1,3; 1,4; 2,3; 2,4; 3,4.
Число всіх сполучень із n елементів по k, де 
, дорівнює добутку k послідовних натуральних чисел, з яких найбільше є n, діленому на добуток всіх натуральних чисел від 1 до k.
.
Формулу для 
можна записати в іншому вигляді. Помноживши чисельник i знаменник дробу в правій частині на добуток 
, одержуємо:
.
Зауваження. Із n елементів можна скласти тільки одне сполучення, що містить всі n елементів, тому прийнято:
.
Властивості сполучень:
а) 
;
б) 
.
III Розміщення
Кожна впорядкована підмножина, яка містить k елементів даної множини з n елементів, називається розміщенням (accommodation) із n по k елементів. Таким чином, два різних розміщення із даних n елементів по k відрізняються один від одного або складом елементів, або порядком їх розміщення.
Приклад. Із трьох цифр 1, 2, 3 можна утворити такі розміщення по два: 1,2; 2,1; 1,3; 3,1; 2,3; 3,2. Число розміщень із n елементів по k позначається символом 
(аrrangement (франц.) розміщення). Число всіх можливих розміщень із n елементів по k дорівнює добутку k послідовних чисел, з яких найбільшим є n, тобто:
, або 
.
Приклад. В класі 10 навчальних предметів і 5 різних уроків в день. Скількома способами можна розподілити уроки в день.
Розв'язання.
Всі можливі розподіли уроків в день являють собою, очевидно, всі можливі розміщення з 10 елементів по 5; тому всіх способів розподілу повинно бути: 
Приклад. Скількома можливими способами можна вибрати з 15 людей делегацію в складі 3 осіб.
Розв'язання. Шукане число (кількість можливих вибірок) є числом сполучень із 15 по 3: 
.
Приклад. Скільки є можливих способів для утворення дозору з трьох солдатів та одного офіцера, якщо є 80 солдат і 3 офіцери?
Розв'язання.
При одному офіцері і 80 солдатах можна утворити дозор 
способами. При трьох офіцерах число способів буде в три рази більше, а саме 
.
Приклад. Знайти число діагоналей опуклого десятикутника.
Розв'язання.
Вершини десятикутника утворюють сукупність 10 точок площини, з яких довільні три не лежать на одній прямій. З'єднуючи будь-яку пару цих точок відрізками одержимо: 
відрізків, 10 з яких є сторонами многокутника. Отже, діагоналей 35.
Розвиток теорії ймовірності, починаючи з XVII ст., був неможливий без достатньо розвинутого математичного апарату комбінаторики. З його допомогою розв’язувалися майже всі задачі того часу до періоду, коли почали застосовувати аналіз нескінченно малих.
Ця наука (комбінаторика) своїм корінням сягає ще школи піфагорійців (IV-III ст. до н. е.). В школі піфагорійців досліджувалися трикутні числа: 1, 3=1+2, 6=1+2+3, 10= 1+2+3+ 4 і взагалі:
Можливо, комбінаторика виникла і розвинулась в Індії у зв’язку з підрахунком в n-складній стопі. Таблиця біноміальних коефіцієнтів до восьмого степеня була відома ще китайському математику Чжу Ши-цзе (1303 р.). Можливо, у той час була відома й узагальнена формула .
Систематичні дослідження з питань комбінаторики містяться у роботах Леві ен Герсона (XVIII ст.), він отримав рекурентну формулу для обчислення числа розміщень з n об’єктів по p. Вагомий внесок у розвиток теорії ймовірності зробив Г. В. Лейбніц, у 1666 р. було опубліковано його книгу “Міркування про комбінаторне мистецтво”. В цій роботі Лейбніц суттєво розробив комбінаторику, в першу чергу з метою глибшого вивчення логіки. В одній із задач він знаходить за даним числом елементів кількість перестановок з 24 елементів. Зокрема, у нього записано, що кількість перестановок з 24 елементів дорівнює 24!
Згідно з періодизацією, запропонованою К. А. Рибніковим, розвиток комбінаторного аналізу ділиться на три періоди:
1) до XVI століття включно - накопичення комбінаторних фактів;
2) з XVII століття до середини XIX століття - від оформлення комбінаторики до створення комбінаторної школи;
3) з середини XIX століття - розвиток сучасного комбінаторного аналізу.
Дослідження становлення фундаментального розділу комбінаторного аналізу - теорії сполук - повністю підтверджує обгрунтованість цих тимчасових кордонів трьох періодів.
Другий період розвитку комбінаторного аналізy умовно можна розділити на такі етапи:
а) формування теорії сполучень при вирішенні загальних проблем теорії чисел, музики та інших;
б) становлення комбінаторного числення після формулювання Г. В. Лейбніцем глобальної ідеї створення загальної характеристики - комбінаторики;
в) різні шляхи розвитку комбінаторного аналізу в період XVIII - початок XIX століття.
Наведемо історичну задачу комбінаторики.
А тримає парі з В, що він витягне з 24 гральних карт, з яких 10 карт різної масті, 4 карти різної масті. Як співвідносяться їх шанси?
