Главная | Обратная связь

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

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

Значне число формул і теорем комбінаторики ґрунтується на двох основних принципах.

Принцип суми. Якщо множина А містить N(A)=n елементів, множна В – N(B)=m елементів, а АВ= , тоді множина А+В містить N(A+B)=n+m елементів.

Цей принцип має місце для будь-якого скінченного числа множин. Для множин, які мають спільну частину:

N(A+B)=N(A)+N(B)–N(AB);

N(A+B+C)=N(A)+N(B)+N(C)–N(AB)–N(BC)+N(ABC) і т.д.

Принцип добутку. Нехай потрібно послідовно k дій. Якщо першу подію можна виконати n₁ способами, другу n₂ способами, третього n₃ cпособами і так до k- ої дії яку можна виконати n_k способами то всі k дій можуть бути виконанні n₁*n₂*…*n_k способами.

Множина називається упорядкованою, якщо кожному її елементу поставлено у відповідність деяке натуральне число (номер елемента) так, що різним елементам відповідають різні числа.

Упорядковані множини називаються різними, якщо вони відрізняються своїми елементами, або їх порядком.

1. Розміщенням з n елементів по k (k є n) називають такі упорядковані сполуки, які складаються з k елементів, взятих із даних n елементів і відрізняються одна від другої елементами або їх порядком

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

=n(n–1)(n–2)…(n–k+1)= (1)

n!=1*2*3*…*n; 0!=1

На першому місці може стати будь-який із n елементі, на 2-му – будь-який із (n–1) елементів, які залишились і т. д. На k- му місці – будь-який із (n–k+1) елемент, які залишились.

Приклад. Скількома способами можна розмістити 4 студентів на 25 стільцях?

= =25*24*23*22=303600

2. Розміщення з n елементів по n називаються перестановками

P_n = =n(n–1)(n–2)…1=n! (2)

Різні перестановки з n елементів відрізняються лише порядком елементів.

Приклад. Скількома способами можна розмістити на книжковій полиці чотири томи математичної енциклопедії?

P₄ =4!=24

3. Сполученням (комбінаціями) із n елементів по k називаються сполуки, що містять k елементів, і які відрізняються хоча б одним елементом.

Сполуки отримують із розміщень, вилучивши сполуки, які відрізняються лише порядком елементів, тобто перестановки.

Приклад. Скількома способами можна вибрати 3 книги з 7?

=35

Властивості сполучень:

а)

б)

в)

4. Розміщення з повтореннями із n елементів по k називають будь-яку упорядковану сполуку, що містить k елементів, взятих із даних n елементів, серед яких є однакові.

=n^k (4)

Приклад. Автомобільний номер складається з трьох букв та чотирьох цифр. Знайти кількість усіх можливих номерів, якщо використовуються 32 літери української абетки.

Оскільки літери і цифри в номері можуть повторюватись, то за правилом добутку шукане число є:

=32³ *10⁴ =327 680 000

5. Перестановки з повтореннями. Це будь-яке упорядкування множини з n елементів, серед яких є однакові.

P_n (n₁*n₂*…*n_k)=

Приклад. Скільки різних слів(у тому числі беззмістовних) можна утворити p з слова ,математика,?

P₁₀ (2;3;2;1;1;1;)= =151 200

6. Сполучення з повтореннями. Це сполука, що містить k елементів, взятих із даних n елементів, серед яких є однакові.

Приклад. Скількома способами можна купити 8 тістечок в кондитерській, де є 6 їх різних видів?

=1287

Лекція 2