КОМБІНАТОРИКА

Цілі уроку:

• Дізнатись, що вивчає комбінаторика
• Дізнатися, як виникла комбінаторика
• Вивчити формули комбінаторики та навчитися застосовувати їх при вирішенні задач

Народження комбінаторики як розділу математики пов'язане з працями Блеза Паскаля та П'єра Ферма з теорії азартних ігор.

Блез Паскаль

П'єр Ферма

Великий внесок у розвиток комбінаторних методів зробили Г.В. Лейбніц, Я. Бернуллі та Л. Ейлер.

Г.В. Лейбніц

Л. Ейлер.

Я. Бернуллі

Лемма. Нехай у множині A m елементів, а у множині B - n елементів. Тоді число всіх різних пар (a, b), де a in, b in B буде дорівнює mn. Доказ. Дійсно, з одним елементом з множини A ми можемо скласти n таких різних пар, а всього в множині A m елементів.

Розміщення, перестановки, сполучення Нехай у нас є безліч трьох елементів a,b,c. Якими способами ми можемо вибрати із цих елементів два? ab,ac,bc,ba,ca,cb.

Перестановки Будемо переставляти їх усіма можливими способами (кількість об'єктів залишається незмінними, змінюється лише їхній порядок). Комбінації, що виходять, називаються перестановками, а їх число одно Pn = n! =1 · 2 · 3 · ... · ( n-1) · n

Символ n! називається факторіалом і позначає добуток усіх цілих чисел від 1 до n. За визначенням вважають, що 0!=1 1!=1 Приклад всіх перестановок з n = 3 об'єктів (різних фігур) - на малюнку. Відповідно до формули, їх має бути рівно P3=3!=1⋅2⋅3=6 так і виходить.

Зі зростанням кількості об'єктів кількість перестановок дуже швидко зростає і зображати їх наочно стає важко. Наприклад, число перестановок із 10 предметів - вже 3628800 (Більше 3 мільйонів!).

Розміщення Нехай є n різних об'єктів. Вибиратимемо з них m об'єктів і переставлятимемо всіма можливими способами між собою (тобто змінюється і склад обраних об'єктів, і їх порядок). Комбінації, що виходять, називаються розміщеннями з n об'єктів по m, а їх число дорівнює Aⁿm =n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

Визначення. Розміщеннями множини з n різних елементів по m елементів (m ≤ n) називаються комбінації , які складені з даних n елементів m елементів і відрізняються або самими елементами, або порядком елементів.

Поєднання Нехай є n різних об'єктів. Вибиратимемо з них m об'єктів усілякими способами (тобто змінюється склад обраних об'єктів, але порядок не важливий). Комбінації, що виходять, називаються сполученнями з n об'єктів по m, а їх число одно Cmn=n!(n−m)!⋅m!

Приклад всіх поєднань з n = 3 об'єктів (різних фігур) по m = 2 - на картинці знизу. Відповідно до формули, їх має бути рівно C23=3!(3−2)!⋅2!:3!=3. Ясно, що поєднань завжди менше ніж розміщень (оскільки при розміщеннях порядок важливий, а для поєднань - ні), причому саме в m! раз, тобто вірна формула зв'язку: Amn=Cmn⋅Pm.

Спосіб 1. В одній грі беруть участь 2 особи, отже, потрібно обчислити, скількома способами можна відібрати 2-х осіб із 15, причому порядок у таких парах не важливий. Скористаємося формулою для знаходження числа поєднань (вибірок, що відрізняються лише складом) з n різних елементів по m елементів

n!= 1⋅ 2 ⋅3⋅...⋅ n , при n=2, m=13.

Спосіб 2.Перший гравець зіграв 14 партій (з 2-м, 3-м, 4-м, і так до 15-го), 2-й гравець зіграв 13 партій (3-му, 4-му, і т.д. до 15-го) го, виключаємо те, що з першим партія вже була), третій гравець – 12 партій, 4-ий – 11 партій, 5 – 10 партій, 6 – 9 партій, 7 – 8 партій, 8 – 7 партій,

а 15-ий уже грав із усіма.

Разом: 14+13+12+11+10+9+8+7+6+5+4+3+2+1=105 партій

ВІДПОВІДЬ. 105 партій.

Вчитель математики Аксьонова Світлана Валеріївна

Бугрівська ЗОШ Всеволожського району Ленінградської області

Слайд 1

Слайд 2

Слайд 3

Слайд 4

Слайд 5

Слайд 6

Слайд 7

Слайд 8

Слайд 9

Слайд 10

Слайд 11

Слайд 12

Слайд 13

Слайд 14

Слайд 15

Слайд 16

Слайд 17

Слайд 18

Слайд 19

Слайд 20

Слайд 21

Слайд 22

Слайд 23

Слайд 24

Презентацію на тему "Дискретний аналіз. Комбінаторика. Перестановки" можна скачати безкоштовно на нашому сайті. Предмет проекту: Інформатика. Барвисті слайди та ілюстрації допоможуть вам зацікавити своїх однокласників чи аудиторію. Для перегляду вмісту скористайтесь плеєром, або якщо ви хочете завантажити доповідь - натисніть відповідний текст під плеєром. Презентація містить 24 слайд(ів).

Слайди презентації

Слайд 1

Дискретний аналіз

Лекція 3. Комбінаторика. Перестановки

Слайд 2

Перестановки

Нехай задано безліч із n елементів. Упорядкування цих елементів називається перестановкою. Іноді додають "з n елементів". Зазвичай виділяється одне, основне чи природне, упорядкування, яке називається тривіальною перестановкою. Самі елементи безлічі нас не цікавлять. Часто як елементи беруть цілі числа від 1 до n або від 0 до n-1. Позначимо безліч перестановок з n елементів через Pn, яке потужність через Pn. Поставимо ті самі три питання: чому дорівнює Pn, як перебрати елементи Pn, як їх перенумерувати.

Слайд 3

Теорема про кількість перестановок

Число перестановок з n елементів одно n! - Добутку чисел від 1 до n. (n! читається n-факторіал) Доказ. По індукції. Для n=1 формула явно правильна. Нехай вона є вірною для n-1, доведемо, що вона вірна і для n. Перший елемент упорядкування можна вибрати n способами, а до обраного першого елементу можна приписати способи решта. Тому правильна формула Pn=Pn-1n. Якщо Pn-1=(n-1)!, то Pn=n!

Слайд 4

Нумерація перестановок

Щоб нумерувати перестановки, ми відобразимо безліч Pn взаємнооднозначно в інше безліч Tn, на якому ввести нумерацію буде набагато простіше, а потім для будь-якого елемента pPn як його номер візьмемо номер його образу Tn. Безліч Tn – це прямий добуток кількох числових відрізків Tn =(0:(n-1))(0:(n-2) … (0). Тобто кожен елемент Tn– це набір невід'ємних чисел i1, i2, …, in-1, in, причому iknk.

Слайд 5

Відображення

Візьмемо перестановку і випишемо поруч із нею тривіальну перестановку. Як перший індекс візьмемо місце першого елемента (вважаючи від нуля) у тривіальній перестановці. Запишемо замість тривіальної перестановки рядок символів, що залишилися. Як другий індекс візьмемо місце другого елемента перестановки в цьому рядку. Повторимо процес до кінця. Очевидно, що k–й індекс буде менше довжини k–го рядка, а останній індекс дорівнюватиме нулю. Подивимося цей процес на прикладі.

Слайд 6

Приклад відображення

0 1 2 3 4 5 6 Індекс cadfgbeabcdefg 2 2 adfgbeabdefg 0 2 0 dfgbebdefg 1 2 0 1 fgbebefg 2 2 0 1 2 gbebeg 2 2 0 1 2 2 bebe 0 2 2 Очевидно, що цей процес оборотний і зворотне відображення побудує набір індексів вихідну перестановку.

Слайд 7

Нумерація множини Tn

Будь-яке пряме твір упорядкованих множин можна як систему числення зі змінним підставою. Згадайте приклад із секундами з першої лекції або розгляньте будь-яку стару шкалу розмірів: 1 ярд = 3 фути, 1 фут = 12 дюймів, 1 дюйм = 12 ліній, 1 лінія = 6 пунктів. (2, 0, 4, 2, 3) = 2 ярди 0 футів 4 дюйми 2 лінії 3 пункти, скільки ж це пунктів? Потрібно порахувати (це називається схемою Горнера) (((2  3+0)  12+4)  12+2)  6+3

Слайд 8

Нумерація множини Tn - 2

Формулу #, що знаходить номер для набору індексів i1, i2, …, in-1, in, ми надамо перевагу написати у вигляді рекурентних виразів # (i1, i2, …, in) = a (i1, i2, …, in-1, n-1); a(i1, i2, …, ik,k) = a(i1, i2, …, ik-1,k-1)(n-k+1)+ ik; a(порожньо,0) = 0; За цією формулою #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Маємо a(2,1)=2; a(2,0,2) = 26+0=12; a(2,0,1,3)=125+1=61; a(2,0,1,2,4) =614+2=246; a(2,0,1,2,2,5) =2463+2=740; a(2,0,1,2,2,0,6) =7402+0=1480;

Слайд 9

Перебір наборів індексів

Виходячи з вищевикладеного, перебрати перестановки просто: потрібно перебрати всі набори індексів і по кожному набору будувати відповідну йому перестановку. Для перебору наборів індексів зауважимо, що кожен набір – це запис числа у спеціальній системі числення зі змінним підставою (система називається факториальной). Правила додавання 1 у цій системі майже такі ж прості, як у двійковій: рухаючись від останнього розряду намагатися додати в поточному розряді 1. Якщо це можливо, то додавши 1 зупинитися. Якщо неможливо, записати в розряд нуль та перейти до наступного розряду.

Слайд 10

Перебір наборів індексів - 2

Розглянемо приклад: 7 6 5 4 3 2 1 Це змінні підстави 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Зверніть увагу, що у 3 4 4 2 2 1 0 кожному рядку почало таке 3 4 4 3 0 0 0 ж, як і в попередній, 3 4 4 3 0 1 0 потім йде елемент, суворо 3 4 4 3 1 0 0 більший, . . . , А 3 4 4 3 1 1 0 подальше не суттєво. 3 4 4 3 2 0 0 Значить, кожен рядок 3 4 4 3 2 1 0 лексикографічно більший за 3 5 0 0 0 0 0 попереднього. 3 5 0 0 0 1 0

Слайд 11

Теорема про лексикографічний перебір перестановок

Описаний алгоритм перебирає перестановки порядку лексикографічного зростання. Доказ. Нам достатньо показати, що якщо ми маємо два набори індексів I1 та I2, та I1 лексикографічно передує I2, то перестановка (I1) лексикографічно передує (I2). Ці перестановки формуються послідовно і поки збігаються I1 і I2, збігаються і їх перестановки. А більшого значення індексу відповідає і більший елемент.

Слайд 12

Прямий алгоритм лексикографічного перебору перестановок

Візьмемо якусь перестановку p і знайдемо прямо лексикографічно наступну. Візьмемо початок – перші елементи. Серед його продовжень відомі мінімальне, в якому всі елементи розташовані за зростанням, і максимальне, в якому за спаданням. Наприклад, у перестановці p = (4, 2, 1, 7, 3, 6, 5) всі продовження для (4, 2, 1) лежать між (3, 5, 6, 7) і (7, 6, 5, 3). Існуюче продовження менше максимального, і третій елемент ще можна не змінювати. І 4-й теж. А 5-й треба змінити. Для цього з елементів, що залишилися, потрібно взяти наступний по порядку, поставити його 5-м і приписати мінімальне продовження. Вийде (4, 2, 1, 7, 5, 3, 6).

Слайд 13

Прямий алгоритм лексикографічного перебору перестановок.

Випишемо кілька наступних перестановок. (4, 2, 1, 7, 5, 3, 6) (4, 2, 1, 7, 5, 6, 3) (4, 2, 1, 7, 6, 5, 3) (4, 2, 3, 1, 5, 6, 7) (4, 2, 3, 1, 5, 7, 6) (4, 2, 3, 1, 6, 5, 7) (4, 2, 3, 1, 6) , 7, 5) (4, 2, 3, 1, 7, 5, 6) (4, 2, 3, 1, 7, 6, 5) (4, 2, 3, 5, 1, 6, 7)

Слайд 14

Формальний опис алгоритму

Робочий стан: Перестановка p і Бульова ознака єActive. Початковий стан: У записана тривіальна перестановка та isActive = True. Стандартний крок: Якщо isActive, видати перестановку як результат. Рухаючись з кінця, знайти в перестановці найбільший монотонно спадний суфікс. Нехай k - Позиція перед суфіксом. Покласти isActive:= (k > 0). Якщо isActive, то знайти в суфіксі найменший елемент, що перевищує pk, поміняти його місцями з pk, а потім суфікс "перевернути".

Слайд 15

Ще алгоритм перебору перестановок

Спробуємо перебрати перестановки так, щоб дві послідовні перестановки мало відрізнялися один від одного. Наскільки мало? На одну елементарну транспозицію, в якій змінюються місцями два сусідні елементи. Чи це можливо? Покажемо принципову схему такого алгоритму, нам буде цікавою саме вона. Уявіть собі n-1 елементарних «механізмів», кожен із пересуває свій елемент усередині набору. На кожному кроці механізм робить зсув ліворуч або праворуч. Напрямок змінюється, коли елемент сягає краю. На зміну напрямку витрачається один крок, під час якого крок робить наступний механізм, який теж може змінювати напрямок.

Слайд 16

Ще алгоритм перебору перестановок -2

Подивимося приклад. 1 2 3 4 травня чия игра 1 2 3 4 5 чий хід A B C D E A C D а б е а б а З D Е A C D б а е A B C A D E A C D B E A B B C D а Е З Д Е B A A B C D E A B C D E A B A C B D E A A C D A E B A C B D A E A C A D E B A C B A D е а а г д б у в а б д е а а D C E B A A C B D E B D З е б а а в г б д а д в а е б а в а й б д а д з е о б а

Слайд 17

Перебір перестановок. 1

function ExistsNextPerm(var kCh: integer): Boolean; var iV, iP, iVC, iPC: integer; begin result:= False; for iV:= nV downto 2 do if count

Слайд 18

Завдання про мінімум суми попарних творів

Нехай задані два набори по n чисел, скажімо, (ak|k1:n) та (bk|k1:n) . Ці числа розбиваються на пари (ak, bk) та обчислюється сума їх попарних творів k1:n akbk. Можна змінювати нумерацію (ak) та (bk). Потрібно вибрати таку нумерацію, за якої сума мінімальна. У цьому завдання можна зафіксувати якісь нумерації (ak) і (bk) та шукати перестановку , для якої досягається мінімум суми k1:n akb(k). Ми виберемо нумерації, коли (ak) розташовані за зростанням, а (bk) – за спаданням.

Слайд 19

Теорема про мінімум суми попарних творів

Мінімум суми попарних творів досягається на тривіальній перестановці. Доказ. Припустимо, що є такі два індекси k і r, що ak 0, тобто. ar br+ak bk > ar bk+ak br. У нашій нумерації розташовані за зростанням. Якщо (bk) розташовані за зростанням, то знайдеться така пара k і r, як сказано вище. Переставивши у цієї пари bk і br ми зменшимо значення суми. Отже, оптимальному рішенні (bk) стоять за зростанням. Ця проста теорема кілька разів зустрінеться нам надалі.

Слайд 20

Завдання про максимальну зростаючу підпослідовність

Задано послідовність (ak|k1:n) чисел довжини n. Потрібно знайти її послідовність найбільшої довжини, у якій числа (ak) йшли б у зростаючому порядку. Наприклад, у послідовності 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 максимальною буде підпослідовність 2, 11, 14, 16, 17, 25, 37, 41 З перестановками це завдання пов'язана тим, що вихідна послідовність може бути перестановкою. Ми обмежимося тим, що покажемо, як вирішується це завдання, а формалізації та обґрунтування алгоритму надамо слухачам.

Слайд 21

Знаходження максимальної зростаючої підпослідовності

Будемо по можливості економно розбивати нашу на спадні послідовності (приклад змінений) найвищу з рядків, де вона не порушить порядку. Візьмемо число з нижнього рядка, 21. Чому воно стоїть у 8-му рядку? Йому заважає 19. А числу 19 заважає 17. А йому 16. І т. д. Послідовність 9, 11, 14, 16, 17, 19, 21 зростає і має довжину 7. Будь-яка послідовність більшої довжини містить два числа з одного рядка ( принцип Диріхле) і не може бути зростаючою.

Слайд 22

Завдання про мінімальну кількість інверсій

Задано послідовність (ak|k1:n) чисел довжини n. Інверсією назвемо дзеркальне відображення, що виконується на місці, будь-якої її підстроки – суцільної підпослідовності. Потрібно за мінімальне число інверсій розмістити елементи послідовності за зростанням. Наприклад, перестановку «суцільна» можна перетворювати так (червоні літери переставлені, великі вже стоять на місці)

Слайд 23

Екзаменаційні питання

Перестановки. Їх перебір та нумерація. Завдання про мінімум скалярного твору. Завдання про найбільшу зростаючу підпослідовність.

Слайд 24

1. Двосторонній перехід перестановка  число 2. Знайти перестановку, що віддалена від даної на це число кроків. 3. Перебір перестановок елементарними транспозиціями. 4. Виконати приклад для задачі про мінімум скалярного твору.

Поради як зробити хорошу доповідь презентації чи проекту

1. Постарайтеся залучити аудиторію до розповіді, налаштуйте взаємодію з аудиторією за допомогою навідних питань, ігрової частини, не бійтеся пожартувати та щиро посміхнутися (де це доречно).
2. Намагайтеся пояснювати слайд своїми словами, додавати цікаві факти, не потрібно просто читати інформацію зі слайдів, її аудиторія може прочитати і сама.
3. Не потрібно перевантажувати слайди Вашого проекту текстовими блоками, більше ілюстрацій та мінімум тексту дозволять краще донести інформацію та привернути увагу. На слайді має бути лише ключова інформація, решту краще розповісти слухачам усно.
4. Текст повинен бути добре читаним, інакше аудиторія не зможе побачити інформацію, що подається, буде сильно відволікатися від розповіді, намагаючись хоч щось розібрати, або зовсім втратить весь інтерес. Для цього потрібно правильно підібрати шрифт, враховуючи, де і як відбуватиметься трансляція презентації, а також правильно підібрати поєднання фону та тексту.
5. Важливо провести репетицію Вашої доповіді, продумати, як Ви привітаєтесь з аудиторією, що скажете першим, як закінчите презентацію. Все приходить із досвідом.
6. Правильно підберіть вбрання, т.к. одяг доповідача також грає велику роль у сприйнятті його виступу.
7. Намагайтеся говорити впевнено, плавно та складно.
8. Намагайтеся отримати задоволення від виступу, тоді Ви зможете бути невимушеним і менше хвилюватися.

Презентація «Перестановки» представляє навчальний матеріал для шкільного уроку на цю тему. Презентація містить визначення перестановок, наочні приклади розуміння сенсу цієї операції, опис математичного апарату на вирішення завдань з перестановками, приклади розв'язання задач. Завдання презентації – у зручній, зрозумілій формі донести до учнів навчальний матеріал, сприяти кращому його розумінню та запам'ятовуванню.

У презентації використовуються спеціальні прийоми, які допомагають вчителю пояснити нову тему. Навчальні матеріали заздалегідь структуровані. За допомогою анімаційних ефектів вони представляють приклади та завдання, роблячи акценти на важливі особливості прикладів та завдань під час демонстрації. Важливі поняття виділяються кольором, що полегшує їхнє запам'ятовування.

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

Далі демонструється приклад перестановок на кольорових олівцях, які можна розмістити у різному порядку. Для цього олівці підписуються першою літерою назви їхнього кольору: С, К, Ж. За допомогою анімованого уявлення наочно демонструються варіанти розміщення олівців по порядку. На одному слайді першими розміщуються сині олівці, а поряд з ними два варіанти розміщення – червоний та жовтий, жовтий та червоний. На наступному слайді продемонстровані варіанти розміщення олівців після червоного – синій та жовтий, жовтий та синій. Останні можливі варіанти - після жовтого червоний і синій, синій та червоний. Після наочної демонстрації виконані операції підписуються як перестановки із трьох елементів. Більш точне визначення перестановки трьох елементів дається на окремому слайді 7. У рамці для запам'ятовування виділено текст, що кожне розташування даних елементів у певному порядку буде називатися перестановкою з трьох елементів.

На слайді 8 продемонстровано позначення перестановок n елементів - P n . Вказано, що перестановки з трьох елементів були розглянуті на прикладі олівців, при цьому очевидно, що таких перестановок буде 6. На слайді відзначено математичний запис кількості перестановок: P 3 =6. Далі на екрані наголошується, що для знаходження кількості перестановок із трьох елементів існує комбінаторне правило множення.

На наступному слайді процедура перестановок розкладається на етапи, щоб отримати правило знаходження кількості перестановок. Вказано, що для підрахунку необхідно на перше місце ставити будь-який із трьох елементів. Він має дві можливості вибрати другий елемент. Для вибору третього елемента лишається єдина можливість. Це означає, що кількість перестановок із трьох елементів буде перемножуватися 3.2.1=6. Отримуємо загальну кількість можливих варіантів перестановок. Аналогічно процесу пошуку варіантів перестановок розглядається варіативність для елементів n.

Нехай є кілька n елементів. Для нього на друге місце міститься один з n-1 елементів, на третє місце відповідно міститься один з n-2 елементів і т.д. Отже, можна вивести загальне правило пошуку кількості перестановок з n елементів: P n =n(n-1)(n-2).….3.2.1.

На слайді 11 на екран виведено формулу P n як P n =1.2.3.….(n-2)(n-1)n. Таким чином вводиться поняття факторіалу, позначення якого продемонстровано нижче за формулу: n!. Розглянуто приклади знаходження факторіалу від деякого числа: 3!=1.2.3=6, і навіть 6!=1.2.3.4.5.6=720. Також зазначено, що 1! = 1. Текст загального правила знаходження кількості перестановок як n-факторіалу розташований внизу слайда.

Далі пропонується розглянути кілька завдань перебування кількості перестановок. На слайді 12 пропонується до вирішення завдання знаходження кількості способів розкладання семи куль по семи осередках. Вказано, що способом рішення є обчислення числа перестановок із 7 елементів: P 7 =7!=5040.

На слайді 13 розглядається розв'язання задачі на знаходження кількості чотиризначних чисел, які складені з 0,1,2,3, цифри в одному числі не повторюються. Рішення передбачено в два етапи - спочатку знаходиться число всіх перестановок з 4 елементів, а потім з них віднімається число перестановок, в яких числа з 0 попереду, так числа, що починаються з нуля, не будуть чотиризначними. Отже, рішення зводиться до обчислення P 4 -P 3 =4!-3!=18. Тобто варіантів утворення таких чисел – 18.

На останньому слайді розглядається рішення задачі, в якій пропонується знайти кількість способів, якими можна розставити 9 тарілок, 4 з яких – червоні, так, щоб червоні розташовувалися поруч. Основна складність у вирішенні цього завдання - зрозуміти, що червоні тарілки в даних перестановках необхідно приймати за одну. Отже, рішення зводиться до знаходження твору P 6 .P 4 =6!.4!=17280.

Презентація "Перестановки" призначена для наочного супроводу пояснення вчителя на тему "Перестановки". Детальне зрозуміле уявлення навчального матеріалу може бути корисним при дистанційному навчанні, а розглянуті при цьому завдання допоможуть учню розібратися з рішенням самостійно.

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

Розміщення, перестановки,

поєднання.

Проказниця Мавпа

Віслюк,

Козел,

Так клишоногий Ведмедик

Затіяли грати квартет

Стій, брати стій! -

Кричить Мавпа, - зачекайте!

Як йти музиці?

Адже ви не так сидите.

І так, і так пересідали - знову музика на лад не йде.

Ось ще дужче пішли в них розбори

І суперечки,

Кому і як сидіти.

знати:

• визначення трьох найважливіших понять комбінаторики:
• розміщення з n елементів m;
• поєднання з n елементів m;
• перестановки із n елементів;
• основні комбінаторні формули

вміти:

• відрізняти завдання на "перестановки", "поєднання", "розміщення" один від одного;
• застосовувати основні комбінаторні формули під час вирішення найпростіших комбінаторних завдань.

безліч

Безліч характеризується об'єднанням деяких однорідних об'єктів одне ціле.

Об'єкти, що утворюють безліч, називаються елементами множини.

Безліч будемо записувати, розташовуючи його елементи у фігурних дужках ( a, b, c, … , e, f}.

У багатьох порядок елементів ролі не грає, так ( a, b} = {b, a}.

Безліч, що не містить жодного елемента, називається порожнім безліччюта позначається символом ø.

безліч

Якщо кожен елемент множини Ає елементом безлічі, то кажуть, що безліч Ає підмножиною безлічі Ст.

Безліч ( a, b) є підмножиною множини ( a, b, c, … , e, f}.

позначається

Перерахуйте можливі варіанти підмножини множини ( 3 , 4 , 5 , 7, 9 }.

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

Комбінаторика є важливим розділом математики, який досліджує закономірності розташування, впорядкування, вибору та розподілу елементів із фіксованої множини.

ПРАВИЛО СУМУВАННЯ

Якщо дві взаємовиключні дії можуть бути виконані відповідно kі mспособами, тоді якусь одну з цих дій можна виконати k+mметодами.

Приклад №1

З міста А до міста В можна дістатися 12 поїздами, 3 літаками, 23 автобусами. Скількими способами можна дістатися з міста А?

Рішення

Приклад №2

У ящику є n різнокольорових кульок. Довільним чином виймаємо одну кульку. Скільки способами це можна зробити?

Рішення. Звичайно, nметодами.

Тепер ці n кульок розподілені за двома ящиками: У першому mкульок, у другій k. Довільно з якогось ящика виймаємо одну кульку. Скільки у різний спосіб це можна зробити?

Рішення.

З першого ящика кульку можна витягнути mрізними способами, з другого kрізними способами, всього N = m + kметодами.

ПРАВИЛО ВИРОБНИЦТВА

Нехай дві дії, що виконуються одна за одною, можуть бути здійснені відповідно kі mспособами Тоді обидві вони можуть бути виконані k ∙ mметодами.

Приклад №3

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

Рішення

Приклад №4

Скільки можна записати двоцифрових чисел у десятковій системі числення?

Рішення.Оскільки число двозначне, то число десятків ( m) може набувати одне з дев'яти значень: 1,2,3,4,5,6,7,8,9. Число одиниць ( k) може приймати ті ж значення і може, крім того, бути рівним нулю. Звідси слідує що m= 9, а k= 10. Усього отримаємо двозначних чисел

N = m · k= 9 · 10 = 90.

Приклад №5

У студентській групі 14 дівчат та 6 юнаків. Скількими способами можна вибрати для виконання різних завдань двох студентів однієї статі?

Рішення.За правилом множення двох дівчат можна вибрати 14 · 13 = 182 способами, а двох юнаків 6 · 5 = 30 способами. Слід обрати двох студентів однієї статі: двох студентів чи студенток. Відповідно до правила складання таких способів вибору буде

N = 182 + 30 = 212.

Типи з'єднань

Багато елементів називаються з'єднаннями.

Розрізняють три типи з'єднань:

• перестановки з nелементів;
• розміщення з nелементів по m;
• поєднання з nелементів по m (m < n).

Визначення: Перестановкою з nелементів називається будь-яке впорядковане безліч з nелементів.

Іншими словами, це така множина, для якої зазначено, який елемент знаходиться на першому місці, який – на другому, який-на третьому, …, який – на n-му місці.

ПЕРЕСТАНОВКИ

Перестановки– це такі з'єднання по nелементів з даних елементів, які відрізняються одне від одного порядком елементів.

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

Рn = n · ( n- 1) · ( n– 2) · … · 2 · 1 = n!

Визначення:

Нехай n- натуральне число. Через n! (читається "ен факторіал") позначається число, що дорівнює добутку всіх натуральних чисел 1 від до n:

n! = 1 · 2 · 3 · ... · n.

У разі якщо n= 0, за визначенням належить: 0! = 1.

ФАКТОРІАЛ

Приклад №6

Знайдемо значення наступних виразів: 1! 2! 3!

Приклад №7

Чому одно

а) Р 5 ;

б) Р 3.

Приклад №8

Спростіть

б) 12! · 13 · 14

в) κ ! · ( κ + 1)

Приклад №9

Скільки способами можна розставити 8 учасниць фінального забігу на восьми бігових доріжках?

Рішення.

Р 8 = 8! = 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 40320

РОЗМІЩЕННЯ

Визначення.Розміщенням з n елементів за mназивається будь-яке впорядковане безліч з mелементів, що складається з елементів n елементної множини.

Кількість розміщень з mелементів по nпозначають:

обчислюють за формулою:

Приклад №9

Учні 11 класу вивчають 9 навчальних предметів. У розкладі навчальних занять на один день можна поставити 4 різні предмети. Скільки існує різних способів складання розкладу на день?

Рішення.

Маємо 9-елементне безліч, елементи якого є навчальні предмети. При складанні розкладу ми вибиратимемо 4-елементне підмножина (уроків) і встановлюватимемо в ньому порядок. Число таких способів дорівнює кількості розміщень з дев'яти по чотири ( m=9, n=4)тобто A 94:

Приклад №10

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

Рішення.

Маємо 24-елементну множину, елементи якої учні класу. При виборах старости і помічника старости ми вибиратимемо 2-елементне підмножина (учня) і встановлюватимемо в ньому порядок. Число таких способів дорівнює кількості розміщень з дев'яти по чотири( m=24, n=2), тобто A 242:

ПОЄДНАННЯ

Визначення.Поєднанням без повторень з nелементів по m-називається будь-яке mелементне підмножина n-елементної множини

Число поєднань з n елементів m позначають

та обчислюють за формулою:

Приклад №11

Скількими способами з класу, де навчаються 24 учні, можна обрати двох чергових?

Рішення.

n =24, m=2

ПОЄДНАННЯ

РОЗМІЩЕННЯ

ПЕРЕСТАНОВКИ

Рn = n!

Визначити якого типу відноситься сполук належить завдання.

1. Скільки способами можна скласти розклад одного навчального дня з 5 різних уроків?

2. У 9 «Б» класі 12 учнів. Скільки способів можна сформувати команду з 4 осіб для участі в математичній олімпіаді?

Чи враховується порядок проходження елементів у з'єднанні?

Чи всі елементи входять до з'єднання?

Висновок: перестановка

Чи враховується порядок проходження елементів у з'єднанні?

Чи всі елементи входять до з'єднання?

(на це запитання відповідь не потрібна)

Висновок: поєднання

3. Скільки існує різних двоцифрових чисел, у запису яких можна використовувати цифри 1, 2, 3, 4, 5, 6, якщо цифри в числі мають бути різними?

Чи враховується порядок проходження елементів у з'єднанні?

Чи всі елементи входять до з'єднання?

Висновок: розміщення

Проказниця Мавпа

Так клишоногий Ведмедик

Затіяли грати квартет

Стій, брати стій! -

Кричить Мавпа, - зачекайте!

Як йти музиці?

Адже ви не так сидите.

І так, і так пересідали - знову музика на лад не йде.

Ось ще дужче пішли в них розбори

Кому і як сидіти.

Скільки різних варіантів розташування музикантів можливо?

Рішення.

Чи враховується порядок проходження елементів у з'єднанні?

Чи всі елементи входять до з'єднання?

Висновок: перестановка

Рn = n! =n · ( n- 1) · ( n– 2) · … · 2 · 1

Р4 = 4! = 4 · 3 · 2 · 1 = 24

«Рано чи пізно будь-яка правильна математична ідея знаходить застосування у тому чи іншому деле»?

перестановки

розміщення

поєднання

Результати розв'язання задач

ДОМАШНЄ ЗАВДАННЯ

Вивчити конспект та формули.

С. 321 №1062

Перестановки це комбінації, складені з тих самих елементів і які відрізняються порядком їх проходження. Число всіх можливих перестановок елементів позначається P n і може бути обчислено за формулою: Формула перестановки: Р n =n! При перестановці число об'єктів залишається незмінними, змінюється їх порядок З зростанням кількості об'єктів кількість перестановок дуже швидко зростає і зображати їх наочно стає важко.

Завдання 1. У турнірі беруть участь сім команд. Скільки варіантів розподілу місць між ними можливо? Р 7 =7!=1*2*3*4*5*6*7=5040 Відповідь: 5040 Завдання 2. Скільки способами можуть розміститися за круглим столом 10 чоловік? Р 10 = 10! = = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = Відповідь:

Нехай є n різних об'єктів. Вибиратимемо з них m об'єктів і переставлятимемо всіма можливими способами між собою. Комбінації, що виходять, називаються розміщеннями з n об'єктів по m, а їх число одно: При розміщеннях змінюється і склад обраних об'єктів, і їх порядок. Формула розміщення:

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

Завдання: У цеху працюють 12 осіб: 5 жінок та 7 чоловіків. Скільки способами можна сформувати бригаду з 7 осіб, щоб у ній було 3 жінки? З п'яти жінок необхідно вибирати по три, тому кількість способів відбору. Оскільки потрібно відібрати чотирьох чоловіків із семи, то число способів відбору чоловіків Відповідь: 350