16.04.202       група №9                математика   (факультатив)

Тема уроку: Комбінаторне правило множення і додавання. Перестановки, розміщення сполучення.

Комбінаторне правило множення і додавання 

Це потрібно знати! 

 Скількома способами учні вашого класу можуть стати один за одним у черзі до буфету? Скількома способами можна обрати у вашому класі старосту та його заступника? Відповідаючи на ці запитання, слід підрахувати, скільки різних комбінацій, утворених за певним правилом, можна скласти з елементів заданої скінченної множини. Область математики, яка займається подібними задачами, називають комбінаторикою. В основі розв'язування більшості комбінаторних задач лежать два правила: правило суми і правило добутку. Правило суми. Якщо елемент а можна вибрати m способами, а елемент b можна вибрати k способами, то вибір «a або b» можна здійснити m + k способами. Правило добутку. Якщо елемент а можна вибрати m способами і після кожного такого вибору елемент b можна вибрати k способами, то вибір «a і b» в вказаному порядку, тобто вибір упорядкованої пари (a;b), можна зробити mk способами. Іншими словами: 

 якщо в умові задачі звучить «і», то вибираємо правило множення;

 якщо в умові задачі звучить «або», то вибираємо правило додавання. 

Це потрібно вміти ! 

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

 Відповідь:7 варіантів

 Задача 2. Цех по виготовленню головних уборів почав випуск трьох нових моделей, для яких був закуплений фетр чотирьох різних кольорів. Скільки видів різних капелюхів може виготовити цех? 

Розв’язання: Для кожної з трьох моделей можна використати кожний з чотирьох кольорів. По правилу добутку кількість різних видів буде 3. 4=12 

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

 б) цифри в коді не повторюються?

в) код починається з цифри “3”? 

г) код є парним числом? 

д) код — парне число, цифри якого не повторюються? Розв’язання: а) Якщо цифри у коді можуть повторюватися, то на кожній позиції у коді може стояти будьяка з 5 цифр, тобто загальна кількість варіантів 5555=625.

б) На першому місці може стояти будь-яка з 5 цифр, на другому — 4 (оскільки одна вже стоїть на першому місці), на третьому — 3, на четвертому — 2 цифри. Загальна кількість варіантів підраховується за основним правилом комбінаторики: 5432=120. 

в) На першому місці стоїть цифра “3”, на інших місцях можуть стояти будь-які з 5 цифр. Загальна кількість варіантів 555=125. 

г) Код є парним числом, якщо на останньому місці стоїть парна цифра, тобто або 2, або 4. На інших місцях можуть стояти будь-які цифри: 5552=250. 

д) Якщо цифри не можуть повторюватися, то на останньому місці стоїть парна цифра, тоді на передостанньому місці може стояти лише чотири цифри, на другому — 3, на першому — 2 цифри. Загальна кількість варіантів 2342=48. 

Спробуй виконати самостійно 

1. З міста А в місто В можна добратися 4 потягами, 2 літаками, 6 автобусами. Скількома способами можна добратися з міста А в місто В? Відповідь: 12 способів 

2. У чемпіонаті країни з футболу беруть участь 16 команд. Скількома способами можуть бути розподілені золота, срібна і бронзова медалі? Відповідь: 3360 способами 

3. Скільки сигналів можна подати з корабля за допомогою чотирьох прапорів різного кольору, розміщуючи їх на щоглі, якщо використовувати різну кількість прапорів? Відповідь:60 способами.

Передивіться відеоуроки за посиланнями:

https://www.youtube.com/watch?v=aAxGy-o46sg

https://www.youtube.com/watch?v=M5_JF7PkbYY

Перестановки, розміщення сполучення.

Комбінаторика      (the combinatorics)  це розділ елементарної алгебри, в якому вивчаються деякі операції над скінченними множинами і розв'язуються задачі, пов'язані з цими операціями.

Слово «комбінаторика» вперше зустрічається в «Міркуваннях про комбінаторне мистецтво»  роботі двадцятирічного Лейбніца (1666 р.), яка стала початком цього розділу математики як самостійної науки.

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

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

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

Нехай є множина М, яка складається із n елементів: а_1, a₂, а₃,…, а_n. Якщо переставляти ці елементи можливими способами, залишаючи незмінним їх загальне число, одержуємо декілька послідовностей: а₁, а₂, а₃,…,а_n,…,а_n-1,а_n-2,…, а₁ і т. д. Кожна з таких послідовностей є перестановкою із даних 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 карти різної масті. Як співвідносяться їх шанси?

https://www.youtube.com/watch?v=yNiRehePYec