ВИДЕО УРОК
Традиційне рішення комбінаторних завдань зводиться
до визначення виду поєднання, про яке йде мова в завданні, і застосування
відповідної формули для обчислення кількості цих поєднань.
Тут основна трудність – визначення виду поєднань: перестановки,
розміщення,
комбінації.
Перестановки.
Нехай є n різних об'єктів. Переставлятимемо їх усіма
можливими способами (число і склад об'єктів залишається незмінним, міняється тільки їх порядок). Комбінації, що
вийшли, називаються перестановками.
Перестановками
називають комбінації, що складаються з одних і тих же n різних об'єктів і відрізняються тільки
порядком їх розташування.
Або
Перестановками
називаються такі вибірки елементів, які відрізняються тільки порядком
розташування елементів, але не самими елементами.
Відмітною особливістю перестановок є те, в кожній з
них бере участь уся множина, тобто, все
n об'єктів.
Формула
для числа перестановок.
Якщо перестановки робляться на множині з n елементів, їх число визначається по формулі:
n! – позначення, яке використовується для короткого
запису добутку усіх натуральних чисел від
1 до n включно і
називають
"n,
– факторіал".
За визначенням, вважають,
що
0! = 1, 1! = 1.
Схема для вирішення комбінаторних
завдань.
Перед рішенням задачі
на обчислення різних видів поєднань пропонується схема сприяючи правильному
виявленню виду поєднання згідно з умовою завдання. При цьому враховуються
характеристичні властивості кожного виду поєднань.
Як видно з схеми, вибір формули залежить від того,
чи будуть усі елементи використовуватися у формуванні поєднань або ні, і чи
важливий їх порядок. Застосовуючи таку схему, завжди можна проаналізувати умову
завдання і відповісти на ці два головні питання.
ЗАДАЧА:
Скількома
способами можна розсадити 5
чоловік за столом ?
РОЗВ'ЯЗАННЯ:
Використовуємо
формулу кількості перестановок.
Р5 = 5! =
120.
ВІДПОВІДЬ:
120 способами.
ЗАДАЧА:
На книжковій
полиці поміщається 30
томів. Скількома способами їх можна розставити, щоб при цьому 1-й і 2-й томи не стояли
поряд ?
РОЗВ'ЯЗАННЯ:
Визначимо
загальне число перестановок з 30
елементів по формулі
Р30 = 30!
Щоб вичислити
число "зайвих" перестановок, спочатку визначимо, скільки варіантів, в
якому 2-й том знаходиться
поряд з 1-м праворуч від нього. У таких перестановках 1-й том може займати місця з першого по 29-і, а 2-й
з другого по 30-і – всього 29 місць для цієї пари
книг. І при кожному такому положенні перших двох томів інші 28 книг можуть займати
інші 28 місць в довільному
порядку. Варіантів перестановки 28 книг.
Р28 = 28!
Всього
"зайвих" варіантів при розташуванні
2-го тому
праворуч від 1-го
вийде
29×28! = 29!
Аналогічно
розглянемо випадок, коли 2-й том розташований поряд з першим,
але зліва від нього. Виходить таке ж число варіантів
29×28! = 29!
Означає усього
"зайвих" перестановок
2×29!,
а потрібних
способів розставляння
30! – 2×29
Вичислимо це
значення
30! – 2×29! = 29!×30 – 2×29!
= 29!×(30 – 2) = 29!×28.
Итак, нам треба
перемножити усі натуральні числа від 1
до 29 і ще раз помножити
на 28.
ВІДПОВІДЬ:
2,4757335×1032.
ЗАДАЧА:
Скільки
чотиризначних чисел можна скласти з чотирьох карток з цифрами
0, 5, 7, 9 ?
РОЗВ'ЯЗАННЯ:
Для того, щоб
скласти чотиризначне число треба задіяти усі чотири картки (цифри на яких різні), і це дуже важлива передумова для
застосування формули Рn =
n! Очевидно, що, переставляючи картки, ми отримуватимемо різні
чотиризначні числа, але коли картка з нулем розташовується на 1-м місці, те число
стає тризначним, тому ці комбінації слід виключити.
Спочатку
знайдемо кількість усіх можливих перестановок
4 карток
Р4 = 4! = 24.
Нехай нуль
знаходиться на 1-м
місці, тоді решта 3
цифри в молодших розрядах можна переставити
Р3 = 3! = 6 способами.
Оскільки карток
трохи, то тут нескладно перерахувати усі такі варіанти
0579, 0597, 0759, 0795, 0957, 0975.
Таким чином, із
запропонованого набору можна скласти
24 – 6 = 18 чотиризначних
чисел.
ВІДПОВІДЬ: 18.
Перестановки
з повтореннями.
Для
випадку, коли серед вибираних n елементів однакові (вибірка з поверненням), завдання про число перестановок з
повтореннями можна виразити питанням:
Скількома способами
можна переставити n предметів,
розташованих на n різних місцях, якщо
серед n предметів є k різних типів (k
< n), т. е. однакові предмети.
Формула
для числа перестановок з повтореннями.
Для
перестановок n – кількість елементів, що
переставляються,
n
1,
n2, … nk
– число повторень.
Схема
для вирішення комбінаторних завдань.
ПРИКЛАД:
У
слові "темперамент" 11
букв (n = 11),
буква "т"
повторюється двічі (n1 = 2), буква "е" – тричі (n2 = 3) і буква "м" – двічі (n3 = 2).
Число можливих перестановок букв в цьому слові:
У перестановках з повтореннями, як і в звичайних
перестановках, бере участь відразу уся безліч об'єктів, але є
одно але: в цій множині один або більша кількість елементів (об'єктів)
повторюється.
ЗАДАЧА:
Скільки
різних букв поєднань можна отримати перестановкою карток з наступними буквами:
К, О, Л, О, К, О,
Л, Ь, Ч, И, К ?
РОЗВ’ЯЗАННЯ:
У
тому випадку, якщо б усі букви були різні, то слід було б застосувати
тривіальну формулу Рn, проте абсолютно зрозуміло, що для
запропонованого набору карток деякі маніпуляції спрацьовуватимуть
<<вхолосту>>, так, наприклад, якщо поміняти місцями будь-які дві
картки з буквами <<К>>
у будь-якому слові, то вийде то ж саме слово. Причому, фізично картки
можуть сильно відрізнятися: одна бути круглою з надрукованою буквою <<К>>, інша – квадратною з намальованою
буквою <<К>>. Але по сенсу завдання навіть такі
картки вважаються однаковими, оскільки в умові питається про букво поєднання.
Все
гранично просто – всього 11 карток, серед яких буква
К
– повторюється 3 рази.
О
– повторюється 3 рази.
Л
– повторюється 2 рази.
Ь
– повторюється 1 раз.
Ч
– повторюється 1 раз.
И
– повторюється 1 раз.
Перевірка:
3 + 3 + 2 + 1 + 1 + 1,
Що
і вимагалося перевірити.
По
формулі кількості перестановок з повтореннями:
Різних
букво поєднань можна отримати – 554400.
На
практиці цілком допустимо не записувати загальну формулу і, крім того, опускати
одиничні факторіали:
ВІДПОВІДЬ: 554400.
ЗАДАЧА:
Олексій
займається спортом, причому 4
дні в тиждень – легкою атлетикою, 2
дні – силовими
вправами і один день відпочиває. Скількома способами він може скласти собі
розкладів зайняття на тиждень ?
РОЗВ'ЯЗАННЯ:
Формула Р7 = 7!
тут не годиться, оскільки враховує співпадаючі перестановки (наприклад, коли міняються місцями силові
вправи в середу з силовими вправами в четвер).
По
формулі кількості перестановок з повтореннями:
105 способами
можна скласти розклад зайняття на тиждень.
ВІДПОВІДЬ: 105.
Перестановки
і теорія вірогідності.
Часто необхідність підрахунку числа варіантів
виникає в теорії вірогідності.
ЗАДАЧА:
На
книжковій полиці стояло 30
томів. Дитина впустила книги з полиці, а потім розставив їх у
випадковому порядку. Яка вірогідність того, що він не поставив 1-й і 2-й
томи поруч ?
РОЗВ'ЯЗАННЯ:
Спочатку
визначимо вірогідність подія А, що полягає в тому, що дитина
поставила 1-й
і 2-й томи поруч. Елементарна подія – деяке
розставляння книг на полиці. Зрозуміло, що загальне число усіх елементарних
подій дорівнюватиме загальному числу усіх можливих перестановок
Р30 =
30!.
Число
елементарних подій, що сприяють події А, дорівнює числу перестановок, в
яких 1-й і 2-й
томи знаходяться поруч, воно рівне
2×29!.
Вірогідність
визначаємо діленням числа сприяючих елементарних подій на число усіх можливих
елементарних подій.
Подія В – дитина не поставила 1-й і 2-й
томи поруч – протилежно події А, означає його вірогідність:
Р(В) = 1 – Р(А) =
1 – 1/15 = 14/15
=
0,9333.
ВІДПОВІДЬ: 0,9333.
У відповіді вийшло число близьке до одиниці, це означає, що при такій кількості книг випадково поставити два задані томи поруч складніше, ніж не поставити.
Завдання до уроку 3
Комментариев нет:
Отправить комментарий