10.10.2022   група  №14   алгебра і початки аналізу

Тема уроку: Розв'язування задач і вправ з теми" Елементи комбінаторики"

1. Передивіться приклади розв'язання задач

https://www.youtube.com/watch?v=MPSwx1Wr-TQ

2. Законспектуйте і вивчіть. Розгляньте приклади

Поняття факторіалу

Факторіалом числа n, де n — ціле невід’ємне число називають добуток всіх натуральних чисел від 1 до n.

Позначають це так n! Отже, n! = 1 ∙ 2 ∙ 3 ∙...∙ (n - 1) ∙ n. За означенням приймають 0! = 1. Наприклад, 4! = 1 ∙ 2 ∙ 3 ∙ 4 = 24.

Приклад. Спростити вираз 6!/5!.

Розв’язання. Маємо 

Розміщення.

Нехай дано множину X з n елементів х₁,х₂,х _n - 1,х _n.

Розміщенням з n елементів по m (m < n) називають будь-яку впорядковану підмножину У множини X, причому дві такі підмножини вважають різними, якщо вони відрізняються складом або порядком елементів.

Приклад 1. Нехай дано множину Х = {1;2;3}. Тоді по одному можна скласти такі розміщення:

(1), (2), (3) - їх буде 3;

по два можна скласти такі розміщення:

(1;2), (1;3), (2;1), (2;3), (3;1), (3;2) - їх буде 6;

по три можна скласти такі розміщення:

(1;2;3), (1;3;2), (2;1;3), (2;3;1), (3;1;2), (3;2;1) - їх буде 6.

Кількість розміщень з n елементів по m позначають А^m _n. Можна записати 

Формула для обчислення:

Цю формулу можна запам’ятати за допомогою такого правила:

А^m _n є добутком т натуральних чисел, починаючи з n, взятих у порядку спадання.

Наприклад, А⁴ ₇ = 7 ∙ 6 ∙ 5 ∙ 4 = 840.

А^m _n можна обчислювати ще й за такою формулою:

Приклад 2. Розклад на день містить 6 уроків. Визначити кількість всіх можливих розкладів при виборі з 9 предметів, при умові, що жоден предмет не стоїть у розкладі двічі.

Розв’язання. Зрозуміло, що таких розкладів буде

А⁶ ₉ = 9 ∙ 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 = 60480.

Приклад 3. Скільки різних правильних дробів можна скласти з чисел 1; 3; 5; 7; 11; 13; 17; 19, які використовують для запису чисельника і знаменника дробу?

Розв’язання. Дробів, у яких чисельник не дорівнює знаменнику можна скласти А² ₈ штук, але лише половина з них правильні. Отже, шукана кількість дробів 

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

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

Кількість перестановок з п елементів позначають Р _n. З означення випливає, що Р _n = Аⁿ _n. Тоді враховуючи формулу для А^m _n та 0! = 1, маємо  Отже,

Комбінації (сполучення).

Нехай дано множину X з елементів x ₁, x ₂,..., x _п -1, x_n.

Комбінацією (сполученням) з n елементів по m (m ≤ n) називають будь-яку під множину Y множини X; причому дві такі підмножини вважають різними, якщо вони відрізняються складом.

Кількість комбінацій з n елементів по m позначають С^m _n. Для обчислення С^m _n використовують формулу:

Наприклад, 

Приклад. У вазі 6 червоних і 4 білих троянди. Скількома способами з вази можна вибрати: 1) три троянди; 2) дві червоні і одну білу троянду?

Розв’язання. 1) Оскільки порядок вибору не має значення, то вибрати три троянди з 10 можна С³ ₁₀ способами.

2) Дві червоні троянди можна вибрати С² ₆ способами, а одну білу – C¹ ₄ способами. Тому вибрати дві червоні і одну білу троянди можна способами. Маємо

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

якщо порядок має значення, то використовуємо А^m _n, якщо ні — то С^m _n. Пропонується наступна задача-схема.

В класі 20 учнів. Скількома способами з цього класу можна вибрати...

старосту й його заступника	двох чергових
Обов’язки різні! Порядок має значення.	Обов’язки однакові! Порядок не має значення.

Приклад 1. Скількома способами можна розставити на полиці 6 книжок?

Розв’язання. Очевидно, що шукана кількість способів дорівнює кількості перестановок з 6 елементів (книг): Р₆ = 6! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720.

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

Розв’язання. З чотирьох цифр 0; 1; 2; 3 можна утворити Р₄ перестановок. Але ті перестановки, які починаються з нуля не будуть записами чотирицифрових чисел, таких перестановок — Р₃. Отже, шукана кількість чотирицифрових чисел дорівнює Р₄ - Р₃ = 4! - 3! = 3!(4 - 1) = 6 ∙ 3 = 18.