Презентація на тему:
Основні правила комбінаторики

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

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

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

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

Задача 1. У групі 21 студент. Скількома способами можна вибрати трьох студентів для проходження педагогічної практики в трьох різних школах? 21 ∙ 20 ∙ 19 =7980 Задача 2. У трьох учнів – Марії, Тетяни, Миколи – виникла потреба розподілити між собою 3 книжки. Скількома способами можна це зробити ? 3 ∙ 2 ∙ 1 = 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) = 20 + 24 +17 – – ( 6 + 12 + 12) +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 < n, k > 0), називається розміщенням з n елементів по k. Позначається : (n-k)! n! Аn k =

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

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

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

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

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

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

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