20.4 Контрольні запитання та завдання

1. Що вивчає комбінаторика?

2. Сформулюйте два основних правила (правила суми та добутку).

3. Наведіть приклади застосування правил суми та добутку.

4. Запишіть розкладання цілого позитивного ступеня n біному Ньютона.

5. За якою формулою визначаються біноміальні коефіцієнти?

6. Чи є формула Ньютона для ступеня бінома справедливою для комплексних чисел?

7. Перелічіть властивості біноміальних коефіцієнтів.

20.5 Приклади аудиторних і домашніх задач

1. З міста А до міста B є сім доріг, а з міста В у місто С – три дороги. Скільки маршрутів ведуть з міста А в С через місто В?

2. Кодовий замок має 5 однакових комірок, кожна комірка може бути встановлена в одне з 6 стійких положень. Скільки різних комбінацій потрібно перебрати (максимальна кількість), щоб, не знаючи коду, відчинити замок?

3. Кидають гральну кістку з шістьома гранями та запускають дзиґу, що має вісім граней. Скількома різними способами можуть вони впасти?

4. На вершину гори ведуть п'ять доріг. Скількома способами турист може піднятися на гору й спуститися з неї? Те саме за умови, що спуск і підйом відбувається різними шляхами.

5. На фермі 20 овець і 24 свині. Скількома способами можна вибрати одну вівцю й одну свиню? Якщо такий вибір уже зроблений, скількома способами можна зробити його ще раз?

6. Скількома способами можна вказати на шахівниці білий і чорний квадрати, які не лежать на одній і тій самий горизонталі й вертикалі?

7. З 12 слів чоловічого роду, 9 жіночого й 10 середнього треба вибрати по одному слову кожного роду. Скількома способами може бути зроблений цей вибір?

8. Є 6 пар рукавичок різних розмірів. Скількома способами можна вибрати з них одну рукавичку на ліву руку й одну – на праву так, щоб ці рукавички були різних розмірів?

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

21 Практичне заняття № 19. Формули простого перелічення

21.1 Мета заняття

Ознайомитися з формулами перелічення. Навчитися застосовувати на практиці формули для знаходження перестановок, розміщень і сполучень. Набути навичок застосування рекурентних співвідношень і чисел Фібоначчі.

21.2 Методичні рекомендації до самостійної роботи студентів

Під час підготовки до практичного заняття необхідно вивчити відповідний розділ конспекту лекцій та ознайомитися з матеріалом підручників [1, c. 418-426; 2, c. 418-426; 9, c. 99-116, c. 123-130; 10, c. 31-63; 12, c. 263-266; 17, c. 129-153].

При повторенні матеріалу слід звернути увагу на такі питання:

• перестановки, розміщення, сполучення;

• рекурентні співвідношення;

• числа Фібоначчі.

21.3 Приклади розв’язання типових завдань

1. Скільки можна скласти перестановок з n елементів, у яких дані m елементів не знаходяться поруч у будь-якому порядку.

Всього n! перестановок. Дізнаємося, скільки перестановок містять m елементів, які стоять поруч у довільному порядку. Для цього розглядатимемо m елементів як один елемент, тобто маємо елементів, які можна переставляти один з одним, кількість таких перестановок . Крім того, можна переставляти елементи всередині m елементів, таких перестановок m!. Всього перестановок . Тоді розшукувана кількість перестановок дорівнює

2. Скільки перестановок можна зробити з літер слова «Радіоелектроніка»?

У слові 16 літер, з них літери "р", "а", "і", "о", "к", "е", зустрічаються по 2 рази, 4 інші ("н","т","л","д") – по одному, отже:

.

3. У студента є 3 лабораторні роботи по С++ та 2 – по Java, які необхідно захистити. Протягом 5 днів підряд він захищає по одній лабораторній. Скількома способами він може це зробити?

.

4. Скільки двійкових наборів можна написати для булевих функцій від 6 змінних?

Кількість наборів визначається кількістю розміщень з повтореннями .

5. У буфеті ХНУРЕ продається чотири сорти тістечок: наполеони, еклери, пісочні й листкові. Скількома способами можна купити 7 тістечок?

Необхідно вказати, скільки штук кожного сорту потрібно купити, отже, маємо справу зі сполученнями з повтореннями. Таким чином, 7 тістечок можна купити способами.

6. На конференції 35 учасників. Вони обмінялися візитками. Скільки всього візиток було роздано?

Кожен з учасників одержить 34 візитки. Тому .

7. Пароль на кредитній картці складається з 5 цифр. Скільки невдалих спроб може бути зроблено людиною, яка не знає секретного слова?

Загальне число секретних слів, що складаються з 5 літер, . Отже, невдалих спроб 100000-1 = 99999.

8. Деякі люди вважають шестизначні номери тролейбусних квитків "щасливими", якщо сума перших та останніх 3 цифр співпадає (інші віддають перевагу складанню цифр на парних і непарних місцях). Наприклад, квиток 615372 "щасливий", оскільки 6+1+5=3+7+2=12.

Щоб знайти число щасливих квитків, замінимо останні 3 цифри їхніми доповненнями до 9. Наприклад, замість 615372 візьмемо 615627. Тоді вийде квиток, сума цифр якого дорівнює 27 (наприклад, 6+1+5+6+2+7=27). Виходячи з того, що цифри у квитку набувають значення від 0 до 9, кількість цифр у кожному номері дорівнює 6, а їхня сума – 27, то підрахунок щасливих квитків зводиться до відшукання значення . А це значення можна знайти за формулою:

.