Комбінаторні задачі.
Комбінаторні задачі.
Комбінаторні правила суми і добутку
Комбінаторні правила суми і добутку
Embedded Files
Скількома способами учні вашого класу можуть стати один за одним у черзі до буфету? Скількома способами можна вибрати у вашому класі старосту та його заступника? Скількома способами можуть бути розподілені золоті, срібні та бронзові медалі на чемпіонаті світу з футболу?
Відповідаючи на ці запитання, потрібно підрахувати, скільки різних комбінацій, утворених за певним правилом, можна скласти з елементів заданої скінченної множини.
Галузь математики, яка займається розв’язуванням подібних задач, називають комбінаторикою.
В основі розв’язування більшості комбінаторних задач лежать два правила:
правило суми та правило добутку.
Розглянемо такий приклад.
Туриста зацікавили 5 маршрутів по Наддніпрянщині та 7 маршрутів по Карпатах. З’ясуємо, скількома
способами він може організувати свою відпустку, маючи час лише на один маршрут.
Оскільки всього є 5 + 7 = 12 різних маршрутів, то один із них можна вибрати 12 способами.
Узагальненням цього прикладу є таке правило.
Правило суми можна узагальнити для трьох і більше множин.
Наприклад, якщо множини A, B і C складаються відповідно з m, k
і n елементів, причому жодні дві з цих множин не мають спільних
елементів, то вибір «a або b або c», де a ∈ A, b ∈ B, c ∈ C, можна
здійснити m + k + n способами.
Знову звернемося до прикладу з вибором маршрутів. Якщо турист має час на два маршрути та хоче побувати спочатку на Наддніпрянщині, а потім у Карпатах, то він може організувати свій відпочинок 35 способами.
Справді, якщо вибрати один маршрут по Наддніпрянщині, то парою до нього може бути будь-який із
7 карпатських маршрутів. Оскільки маршрутів по Наддніпрянщині 5, то кількість пар (маршрут по Наддніпрянщині; маршрут по Карпатах) дорівнює 7 + 7 + 7 + 7 + 7 = 7.5 = 35.
Ці міркування ілюструє така таблиця:
Узагальненням цього прикладу є таке правило.
Правило добутку також природно узагальнити. Наприклад, якщо елемент a можна вибрати m способами, після кожного такого вибору елемент b можна вибрати k способами, і після того, як вибрано елементи a і b, елемент c можна вибрати n способами, то вибір «a і b і c» можна здійснити mkn способами.
П р и к л а д 1 Із класу, у якому навчаються 28 учнів, потрібно вибрати трьох чергових по одному на кожний із трьох поверхів школи. Скількома способами можна це зробити?
П р и к л а д 1 Із класу, у якому навчаються 28 учнів, потрібно вибрати трьох чергових по одному на кожний із трьох поверхів школи. Скількома способами можна це зробити?
Розв’язання.
Існує 28 способів вибрати чергового по першому поверху.
Після того як цей вибір буде зроблено, залишиться 27 учнів, кожний з яких може стати черговим по другому поверху.
Після вибору чергових для першого та другого поверхів чергового по третьому поверху можна вибрати 26 способами.
Таким чином, за правилом добутку кількість способів вибору трьох чергових дорівнює:
28*27*26 = 19 656.
Відповідь: 19 656 способами. ◄
П р и к л а д 2 На рисунку 21.1 показано схему шляхів, що прокладено з міста A до міста B. Скількома способами можна проїхати з міста A до міста B?
П р и к л а д 2 На рисунку 21.1 показано схему шляхів, що прокладено з міста A до міста B. Скількома способами можна проїхати з міста A до міста B?
Р о з в’я з а н н я. Скориставшися правилом добутку, доходимо висновку, що з міста A до міста B через місто M можна дістатися 3*2 = 6 способами, а через місто N — 4*3 = 12 способами. Тоді за
правилом суми загальна кількість способі дорівнює: 6 + 12 = 18 способів.
Відповідь: 18 способами. ◄
Письмові вправа
Письмові вправа
21.1.° Підніжжя гори та її вершину сполучають три стежки. Скільки є маршрутів від підніжжя до вершини й потім униз до підніжжя?
21.3.° Тетянка має п’ять суконь і три пари черевичків. Скільки варіантів вибрати вбрання є в Тетянки?
21.5.° Скільки різних трицифрових чисел можна скласти із цифр:
1) 1 і 2; 2) 0 і 1
(цифри можуть повторюватися)?
21.6.° Із міста A до міста B проходять 4 шляхи, а з міста B до міста C проходять 3 шляхи (рис. 21.2). Скількома способами можна проїхати з міста A до міста C?
21.7.° Кафе пропонує меню з 3 перших страв, 6 других страв і 5 третіх страв. Скільки є способів вибрати обід з трьох страв (по одній страві кожного виду)?
21.8.° Будемо розглядати склади з двох букв, перша з яких позначає приголосний звук, а друга — голосний. Скільки таких різних складів можна скласти з букв слова:
1) Полтава; 2) Миколаїв?
21.9.• Скільки чотирицифрових чисел, усі цифри яких різні, можна скласти із цифр 1, 2, 3, 4, якщо ці числа мають починатися:
1) із цифри 4; 2) із запису «23»?
21.10.• Скільки трицифрових чисел можна записати за допомогою цифр 0, 1, 2, 3, 4?
21.11.• Скільки існує двоцифрових чисел, усі цифри яких парні?
21.12.• Скільки існує двоцифрових чисел, усі цифри яких непарні?
21.13.• Монету підкидають 3 рази. Скільки різних послідовностей гербів і цифр можна отримати?
21.14.• Гральний кубик кидають 3 рази. Скільки різних послідовностей очок можна отримати?
21.15.• Кожну клітинку квадрата 2×2 можна пофарбувати в блакитний або червоний колір. Скільки існує способів пофарбувати цей квадрат?
21.16.• Скількома способами можна вибрати на шаховій дошці білу та чорну клітинки, які не лежать на одній і тій самій вертикалі та горизонталі?
21.17.•• Скільки існує парних п’ятицифрових чисел?
21.18.•• Скільки існує п’ятицифрових чисел, які кратні 10?
21.19.•• Один колекціонер має для обміну 11 марок і 8 монет, другий — 9 марок і 7 монет. Скількома способами колекціонери можуть обміняти марку на марку або монету на монету?
21.20.•• Скільки існує п’ятицифрових чисел, усі цифри яких мають однакову парність?
Тренувальні вправи
Тренувальні вправи
1.04.2024-9йклас.pdfЧитати підручник
Читати підручник
Page updated
Google Sites
Report abuse