На головну

Правила суми і твори

  1. Quot; Правила евакуації.
  2. VII. Правила проведення робіт по сертифікації в системі сертифікації в цивільній авіації Російської Федерації
  3. VIII. Правила по проведенню акредитації в системі сертифікації в цивільній авіації Російської Федерації
  4. X. Правила застосування знаків відповідності
  5. А) Дослідження сприйняття і відтворення звуковисотного відносин
  6. Авторські публіцистичні твори
  7. Авторської винагороди за публічне виконання твору?

Рішення більшості комбінаторних задач засновано на правилах, які називають правилами суми і твори.

Розглянемо наступні завдання:

Завдання 1. У магазині «Магніт» є 20 плиток молочного шоколаду з горіхами «ALPEN GOLD» і 14 плиток чорного пористого шоколаду «ПОВІТРЯНИЙ». Скількома способами можна вибрати одну плитку шоколаду?

Завдання 2. У книжковому магазині «Фенікс» є 5 книг про Гаррі Поттера і 3 книги із серії «Володар кілець». Скількома способами можна вибрати одну книгу?

Ці завдання переведемо на мову теорії множин і сформулюємо в загальному вигляді:

Є два кінцевих безлічі А = {а  , а  , ..., А } и В = {b  , b  , ..., B  }, які не мають спільних елементів. Скількома способами можна вибрати об'єкт, що належить або А, або В?

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

Якщо об'єкт а можна вибрати m способами, а об'єкт b можна вибрати k способами, відмінними від способу вибору об'єкта a, то вибір «або a, або b» можна здійснити m + k способами.

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

Ми можемо вирішити раніше запропоновані завдання, використовуючи правило суми.

Завдання 1. Рішення. Так як є 20 видів молочного шоколаду з горіхами «ALPEN GOLD», то існує 20 способів вибрати одну з плиток шоколаду. Аналогічно існує 14 способів вибору однієї плитки шоколаду «ПОВІТРЯНИЙ». Так як потрібно вибрати шоколад «або з горіхами, або пористий», то за правилом суми отримуємо (20 + 14 = 34) тридцять чотири способу вибору однієї плитки шоколаду.

Завдання 2. Рішення. Міркуючи так само, як при виконанні завдання 1, за правилом суми отримаємо 8 способів вибору однієї книги із запропонованих.

Розглянемо наступні завдання.

Завдання 3. До Дня Іменинника, що відзначається в початковій школі, батьки приготували дітям подарунки: 9 книг художньої літератури різних письменників і 5 видов блокнотів. Скількома способами можна вибрати подарунок, який складається з однієї книги і одного блокнота?

Завдання 4. Скількома способами можна скласти команду з одного спортсмена зі стрибків у довжину і одного бігуна, які є претендентами для участі в змаганнях з легкої атлетики, якщо серед претендентів на участь 7 спортсменів зі стрибків у довжину і 4 спортсмена з бігу?

Переведемо ці завдання на мову теорії множин і сформулюємо в загальному вигляді:

Є два кінцевих безлічі А = {а  , а  , ..., А } и В = {b  , b  , ..., B  }. Скількома способами можна вибрати два об'єкти, один з яких належить множині А, А другий - безлічі В?

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

Якщо об'єкт а можна вибрати n способами, а об'єкт b можна вибрати m способами, то вибір «і a, і b» можна здійснити n • m способами.

Правило твори поширюється на випадок вибору кортежу будь-якої довжини.

Використовуючи правило твори, вирішимо завдання, запропоновані раніше.

Завдання 3. Рішення. Так як існує 9 способів вибору книг по художній літературі і 5 способів вибору блокнотів, то за правилом твори «вибір книги і блокнота» ( «і a, і b») Можна здійснити (9 • 5 = 45) сорока п'ятьма способами.

відповідь: 45 способів.

Завдання 4. Рішення. Міркуючи так само як під час розв'язання задачі 4, за правилом твори отримаємо 28 способів скласти команду для участі в змаганнях з легкої атлетики.

відповідь: 28 способів.

Розглянемо ще кілька завдань.

Завдання 5. Визначимо, скількома способами можна вибрати гласну і згідну літери з слова «будинок»? а з слова «мікрон»?

Рішення.У слові «будівля» 3 приголосні і 3 голосні букви. Нам необхідно вибрати і голосну і приголосну літери, тому за правилом твори вибір може бути зроблений 3 • 3 = 9 (способами).

А з слова «мікрон» вибір можна зробити 4 • 2 = 8 (способами).

відповідь: 9 способами, 8 способами.

Завдання 6. У конкурсі беруть участь 20 осіб. Скількома способами можна присудити першу, другу і третю премії?

Рішення.Існує 20 способів вибору одного кандидата на першу премію. Залишається 19 кандидатів, одному з яких присуджують другу премію. Нарешті, одному з вісімнадцяти кандидатів, що залишилися присуджують третю премію. Згідно з правилом твори для цього існує 20 • 19 • 18 = 6840 (способів) присудження першої, другої і третьої премії.

відповідь: 6840 способів.

Завдання 7. Скільки тризначних чисел можна записати, використовуючи цифри 0, 1, 3, 6, 7 і 9?

Рішення. Так як запис числа не може починатися з нуля, то цифру розряду сотень можна вибрати п'ятьма способами; вибір цифри десятків можна здійснити шістьма способами, вибрати цифру одиниць з даних шести також можна шістьма способами. Звідси, за правилом твори, отримуємо, що всього тризначних чисел (з даних шести цифр) можна утворити 5 • 6 • 6 = 300 (чисел).

відповідь: 300 чисел.

Завдання 8. Скільки тризначних чисел можна записати, використовуючи цифри 0, 1, 3, 6, 7 і 9, якщо кожна з них може бути використана в запису числа тільки один раз?

Рішення. Так як запис числа не може починатися з нуля, то цифру розряду сотень можна вибрати п'ятьма способами; вибір цифри десятків можна здійснити також п'ятьма способами, оскільки цифри в запису числа не повинні повторюватися, а одна з шести даних цифр буде вже використана для запису сотень; Після вибору двох цифр (для запису сотень і десятків) вибрати цифру одиниць з даних шести можна чотирма способами. Звідси, за правилом твори, отримуємо, що всього тризначних чисел (з даних шести цифр) можна утворити 100: 5 • 5 • 4 = 100 (чисел).

Відповідь: 100 чисел.

Доведемо теорему 5, використовуючи правило твори.

Теорема 5. Кінцеве безліч, що містить п елементів, має 2п підмножин, тобто якщо Ап = {А1, а2, ..., A  }, то п (М (Ап)) = 2п.

? Перенумеруем елементи безлічі А і для кожного підмножини безлічі А побудуємо послідовність довжини n з нулів і одиниць за наступним правилом: на k - М місці пишемо 1, якщо елемент з номером k входить в підмножина, і 0, якщо елемент з номером k не входить в підмножина. Отже, кожному підмножині відповідає своя послідовність нулів і одиниць. Число всіх можливих послідовностей довжини n, складених з нулів і одиниць, так само, згідно з правилом твори: 2 • 2 • ... • 2 = 2 .

Отже, і число всіх підмножин множини А дорівнює 2  . Теорема доведена.



поняття факторіала | Завдання для самостійного рішення

Приклади розв'язання деяких комбінаторних задач ............ 97 | Поняття комбінаторної задачі | Історія виникнення і розвитку комбінаторики | кінцеві безлічі | Операції над множинами | Декартово твір множин А і В | Завдання для самостійного рішення | Знаходження числа всіх підмножин даної множини | Перестановки без повторень | Завдання для самостійного рішення |

© um.co.ua - учбові матеріали та реферати