Елементи комбінаторики Перестановки, розміщення, комбінації

Перестановки Проаналізуємо умови задач 2 і Запишіть усі трицифрові числа, які можна утворити за допомогою цифр 1, 2, 3 не повторюючи їх у запису числа. Скільки таких чисел утворилось? 4. Десять друзів зайшли перекусити до кавярні. Вони довго вирішували, яким чином розміститися за стійкою. Хазяїн кавярні запропонував їм угоду, за якою друзі можуть приходити щодня, але сідати кожного разу у різному порядку. Після того, як вони перепробують усі можливі варіанти, їх будуть годувати за рахунок закладу. На який день друзі отримають безкоштовний обід? Що є спільного в задачах?

Перестановки В обох задачах ми мали справу з деякою множиною різних елементів, для яких встановлювали певний порядок. Множину М, яка складається з п елементів ( п N), називають упорядкованою, якщо між нею і множиною перших п натуральних чисел установлено взаємно однозначну відповідність.

Перестановки Отже, в задачах 2 і 4 ми впорядковували елементи кожної із даних множин, отримували вже різні впорядковані множини і фактично відповідали на запитання скількома способами можна впорядкувати елементи множини?. В комбінаториці будь-яка впорядкована множина, що складається з п елементів називається перестановкою. Усі перестановки з п елементів відрізняються одна від одної порядком розміщення цих елементів.

Перестановки Розглянемо, наприклад, таку множину Елементи розміщені у певному порядку – це одна перестановка Змінюючи порядок розміщення елементів отримуємо інші перестановки

Кількість перестановок з п елементів Першим може бути будь-який з п елементів. Другим будь-який з п – 1 елементів. Тоді перші два елементи можна розташувати п · (п – 1) способами. Третім може бути будь-який з п – 2 елементів, що залишилися. Будь-який третій елемент можна поєднати з будь- якою парою з перших двох елементів. Утворених трійок буде п · (п – 1) · (п – 2). Продовжуючи міркування, отримуємо, що п елементів можна впорядкувати п · (п – 1) · (п – 2) · … · 2 · 1 способами.

Кількість перестановок з п елементів Добуток п · (п – 1) · (п – 2) · … · 2 · 1 позначається п! ( п факторіал). Кількість перестановок позначається Рп.Рп. Отже, Р п = п!

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

Розміщення з п елементів по т елементів Знову у задачах ми мали справу з деякою множиною різних елементів. Потім ми впорядковували певну кількість елементів кожної із множин, отримували різні впорядковані підмножини розглядуваних множин і відповідали на запитання скількома способами можна впорядкувати різні підмножини даної множини. В комбінаториці будь-яка впорядкована підмножина з т елементів даної множини, що містить п елементів ( т п ) називається розміщенням з п елементів по т елементів. Усі розміщення з п елементів по т елементів відрізняються одна від одної складом елементів та порядком їх розташування.

Розміщення Розглянемо, наприклад, множину з 8 елементів Утворюючи і впорядковуючи її підмножини, наприклад з 5 елементів, будемо отримувати різні розміщення з 8 по 5 елементів

Кількість розміщень з п елементів по т елементів Першим може бути будь-який з п елементів. Другим будь-який з п – 1 елементів. Тоді перші два елементи можна розташувати п · (п – 1) способами. Третім може бути будь-який з п – 2 елементів, що залишилися. Будь-який третій елемент можна поєднати з будь-якою парою з перших двох елементів. Утворених трійок буде п · (п – 1) · (п – 2). Продовжуючи міркування, отримуємо, що на т -те місце можна вибрати будь-який з п – т + 1 елементів. Тому всіх розміщень з п елементів по т елементів буде п · (п – 1) · (п – 2) · … · (п – т + 1)

Кількість розміщень з п елементів по т елементів Кількість розміщень з п елементів по т елементів позначається Отже,

Комбінації Наостанок проаналізуємо задачі 8 і З тієї самої групи студентів (задача 7) необхідно вибрати трьох для участі у загально університетському заході. Скільки існує варіантів такого вибору? 9. У продавця квітами є троянди 7 кольорів. Скільки можна утворити букетів з 5 різнокольорових троянд? Що є спільного в цих задачах і чим вони відрізняються від попередніх?

Комбінації з п елементів по т елементів І знову у задачах ми мали справу з деякою множиною різних елементів. Потім ми вибирали певну кількість елементів кожної із множин, отримували різні, але вже не впорядковані підмножини розглядуваних множин і відповідали на запитання скількома способами це можна зробити. В комбінаториці будь-яка підмножина з т елементів даної множини, що містить п елементів ( т п ) називається комбінацією з п елементів по т елементів. Усі комбінації з п елементів по т елементів відрізняються одна від одної тільки складом елементів.

Комбінації Розглянемо, наприклад, множину з 8 елементів Утворюючи будь-які її підмножини, наприклад з 5 елементів, будемо отримувати різні комбінації з 8 по 5 елементів

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

Кількість комбінацій з п елементів по т елементів Помножимо чисельник і знаменник дробу на ( п – т )!. Матимемо

Вибір сполуки Чи всі елементи множини задіяні в утворенні сполуки? ні ПерестановкиЧи важливий порядок елементів? такні РозміщенняКомбінації так

1. У школі 20 класів і 20 класних керівників. Скількома способами можна розподілити класне керівництво між учителями? ( 25.5, Мерзляк А.Г., Полонський В.Б., Якір М.С. Алгебра: Підручник для 9 класу з поглибленим вивченням математики) Кількість можливих розподілів класного керівництва між 20 учителями – це кількість перестановок з 20 елементів. Р 20 = 20!

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

2. Скільки трицифрових чисел можна записати за допомогою цифр 0, 1, 2, 3, 4, 5? Цифри в запису числа не повторюються. На першому місці можна записати будь-яку з цифр 1, 2, 3, 4, 5 – всього 5 способів. На другому – знову будь-яку з 5 (серед них вже може бути 0). На третьому – будь-яку з 4, що залишилися після запису перших двох цифр числа. За комбінаторним правилом множення різних записів трицифрових чисел буде: 5 · 5 · 4 = 100

3. У шаховому гуртку 5 хлопців і 3 дівчини. Для зустрічі з гросмейстером прийшло 3 запрошення. Скількома способами можна розподілити запрошення так, щоб на зустріч потрапила хоча б одна дівчина ? Хоча б одна дівчина – означає, що їх може бути або одна, або дві, або три. Питання можна поставити так: Скількома способами можна вибрати 3-х осіб з 5 хлопців і 3 дівчат, щоб серед них були або 1, або 2, або 3 дівчини?

3. У шаховому гуртку 5 хлопців і 3 дівчини. Для зустрічі з гросмейстером прийшло 3 запрошення. Скількома способами можна розподілити запрошення так, щоб на зустріч потрапила хоча б одна дівчина? Одну дівчину з 3-х можна вибрати 3 способами. Способів вибору 2-х хлопців з 5-ти: Всього трійок з 1 дівчини і 2 хлопців: Трійок з 2 дівчин і 1 хлопця буде: Три дівчини можна вибрати тільки 1 способом. Загальна кількість способів: = 46

3. У шаховому гуртку 5 хлопців і 3 дівчини. Для зустрічі з гросмейстером прийшло 3 запрошення. Скількома способами можна розподілити запрошення так, щоб на зустріч потрапила хоча б одна дівчина? Усіх довільних трійок можна утворити В усіх інших виборах будуть присутні дівчата. Отже, таких виборів 56 – 10 = 46 Трійок тільки з 3-х хлопців є:

4. З 10 тенісисток і 6 тенісистів складають 4 змішані пари. Скількома способами це можна зробити? 4 змішані пари – це 8 осіб: 4 тенісистки і 4 тенісиста. 4 тенісистки з 10 можна вибрати 210 способами. 4 тенісиста з 6 можна вибрати 15 способами. Тоді 8 осіб для утворення 4 пар можна вибрати = = 3150 способами. З 8 осіб утворити 4 змішані пари можна так: одного з тенісистів поставити у пару з будь-якою з 4 тенісисток, всього 4 способи; другого з них поставити у пару вже з будь-якою з 3 тенісисток, всього 3 способи; третього – з 2 тенісисток, всього 2 способи; для четвертого залишається тільки один спосіб стати у пару. Отже всього = 24 способи утворення 4 пари з 8 осіб. А всіх способів утворити чотири змішані пари є =

4. З 10 тенісисток і 6 тенісистів складають 4 змішані пари. Скількома способами це можна зробити? Всіх змішаних пар з 10 тенісисток і 6 тенісистів можна утворити 10 6 = 60. Проілюструємо це схемою-сіткою. Вузли сітки – це пари. Щоб вибрати 4 пари треба, наприклад, взяти будь-які 4 стовпчики, а потім із кожного стовпчика взяти по одній парі з різних рядків.

4. З 10 тенісисток і 6 тенісистів складають 4 змішані пари. Скількома способами це можна зробити? Способів вибрати 4 стовпчики з 10: Після цього першу пару можна вибрати з будь-яких 6 рядків, всього 6 способів; другу – з 5 рядків, всього 5 способів; третю – з 4 рядків і четверту – з 3 рядків. Тоді всього способів вибрати 4 пари:

5. Скільки різних трицифрових чисел можна записати за допомогою цифр 1, 2, 3, 4, 5, якщо цифри можуть повторюватися у запису числа? На перше місце можна записати будь-яку з 5 цифр – всього 5 варіантів. Оскільки цифри можуть повторюватися, то на друге місце можна також записати будь-яку з 5 цифр – знову 5 варіантів. Отже, на перші два місця дві які-небудь цифри можна записати 5 · 5 способами. На третє місце також можна записати будь-яку з 5 цифр. Тоді всіх можливих трицифрових чисел буде 5 · 5 · 5 = 5 3.

6. Скільки різних натуральних чисел можна записати за допомогою цифр 1, 2, 3, 4, 5, якщо цифри у запису чисел можуть повторюватися і кількість цифр у запису не більше 5 ? Числа можуть бути одно, два, три, чотири або пятицифрові. Одноцифрових чисел можна записати 5 штук. Двоцифрових Трицифрових – 5 3, чотирицифрових – 5 4 і пятицифрових – 5 5. Всього різних чисел Ця сума є сумою 5 перших членів геометричної прогресії, у якої перший член 5 і знаменник 5. За формулою суми n–перших членів геометричної прогресії знаходимо, що всіх чисел є 3905.

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

Дякую за увагу!