Основні правила комбінаторики

Мотивація вивчення теми Часто приходиться складати з скінченного числа елементів різні комбінації і підраховувати число всіх можливих комбінацій, що складені за якимись правилами. Такі задачі називаються комбінаторними, а розділ математики, що займається їх розв'язуванням називається комбінаторикою.

Основою комбінаторики є теорія перелічувань, яка базується на правилах суми та добутку. Задача. Скільки трицифрових чисел можна записати за допомогою цифр 1, 2, 3, не повторюючи цифри в запису числа ? Якщо деякий об'єкт А можна вибрати m способами, і після кожного такого вибору інший об'єкт В можна вибрати ( незалежно від вибору об'єкта А) n способами, то пари об'єктів А і В можна вибрати m · n способами. Для першої цифри 3 варіанта, для другої – 2, а для третьої – 1. Всього: = 6 Основне правило комбінаторики – правило множення

Для ілюстрації скористаємося деревом логічних можливостей

Задача 1. У групі 21 студент. Скількома способами можна вибрати трьох студентів для проходження педагогічної практики в трьох різних школах? =7980 Задача 2. У трьох учнів – Марії, Тетяни, Миколи – виникла потреба розподілити між собою 3 книжки. Скількома способами можна це зробити ? = 6

в) для першої цифри дві можливості, друга лише одна, отже, 2 1 = 2 Задача. Скільки двоцифрових чисел можна скласти в трійковій системі числення таких що: а) кожна з цифр повторюється не більше ніж один раз; б) цифри можуть повторюватися; в) числа можуть бути непарними (цифри можуть повторюватися )? а) першою цифрою може бути – 1 або 2; Друга цифра теж може бути вибраною двома способами. Тоді загальна кількість способів 2 2 = 4; б) для першої цифри дві можливості, а для кожної наступної маємо три можливості, отже, 2 3 = 6;

Комбінаторне правило додавання Нехай n(A) – кількість елементів множини А, а n(В) – кількість елементів множини В. Якщо множини не мають спільних елементів, то їх об'єднання А U В містить n(A) + n(В) елементів, n(A U В) = n(A) + n(В). Якщо множини мають спільні елементи, то вони ввійдуть у суму двічі. Тому: n(A U В) = n(A) + n(В) – n(АВ).

Задача. Кожен учень класу – або дівчинка, або блондин, або любить математику. У класі 20 дівчаток, з них 12 блондинок, а одна блондинка любить математику. Всього у класі 24 учні- блондини, математику з них люблять 12, а всього учнів (хлопчиків та дівчаток), які люблять математику, 17, з них 6 дівчаток. Скільки учнів у цьому класі? А – множина дівчаток, В – блондинів, С – учнів, які люблять математику, то n(А U B U C) – шукане число. А В – множина блондинок; А С – множина дівчаток, які люблять математику ; В С – множина всіх блондинів (хлопчиків та дівчаток), які люблять математику ; Тоді: n(А U B U C) = n(A) + n(В) + n(С) – n(АС) – – n(АВ) – n(ВС) + n(А B C) = – – ( ) +1 = 32.

Перестановки Перестановкою називається встановлений у множині порядок. Приклад : Нехай дано множину: { а, в, с }. Існує шість способів розташування елементів множини: авс, асв, вас, вса, сва, сав. Число перестановок з n елементів позначають Р n.

Розглянемо випадки: Р 1 =1=1! Р 2 =1·2=2! Р 3 =1 ·2 ·3=3! Гіпотеза Р n = n!

Задачі : 1. Скількома способами можно скласти список з 9 учнів ? 2. У поїзді 14 вагонів. Скількома способами можна розмістити 14 провідників, якщо за кожним вагоном закріплюється один провідник. 3. З цифр 0, 1, 2, 3 складені усі чотиризначні числа так, що у кожному числі не має однакових цифр. Скільки отримали чисел?

Розміщення Упорядкована k – елементна підмножина n – елементної множини (k 0), називається розміщенням з n елементів по k. Позначається : (n-k)! n! АnАn k =

Задачі : 1. Скількома способами можна вибрати чотирьох людей на чотири різні посади з девяти кандидатів на ці посади ? 2. Скількома способами можуть розміститися 10 учнів на 25 стільцях ?

Комбінації Кожна k – елементна підмножина n – елементної множини називається комбінацією з n елементів по k і позначається: С nС n k = n! (n-k)! K!K!

Задачі : 1. Скількома способами можна вибрати 3 книжки з 6 ? 2.Скільки можна скласти з простих дільників числа 2310 складених чисел, які містили б тільки два простих дільника ?

Властивості комбінацій:

Задача. З 10 різних квітів треба скласти букет так, щоб в нього входило не менше двох квітів. Скільки способів існує для складання такого букету ?

Домашнє завдання Розв'язати: 306 – 315. Опрацювати: § 10, 11, ст.204 – 217.

Бажаю успіхів !