ТЕОРІЯ ЙМОВІРНОСТЕЙ та МАТЕМАТИЧНА СТАТИСТИКА

МЕТОДИЧНІ РЕКОМЕНДАЦІЇ ДЛЯ СТУДЕНТІВ

ІV курсу фізико-математичного факультету

спеціальностей «Математика та основи інформатики»,

«Математика та основи економіки»

Упорядник: Бобир С. Л.

Частина І. Елементи комбінаторики

Тема 1. Правила суми і добутку. Сполуки без повторень

Короткі теоретичні відомості

Комбінаторика – це наука про скінчені множини, яка вивчає кількість підмножин з певними властивостями, впорядкування множин і т. д.

Багато комбінаторних задач можна розв’язати за допомогою правил суми та добутку.

Нехай A і B – деякі множини, , . N(A) та N(B) – кількість їх елементів відповідно. Позначимо N(A)=m і N(B)=n.

Правило суми: якщо елемент a можна вибрати m способами, а елемент b – n способами, причому ніякий спосіб вибору a не співпадає з жодним способом вибору b, то один з двох елементів a або b можна вибрати m+n способами.

Правило добутку: якщо елемент a можна вибрати m способами і при кожному з таких виборів елемент b можна вибрати n способами, тоді число способів вибору впорядкованої пари a і b дорівнює m·n способів.

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

До сполук без повторення належать розміщення, перестановки та комбінації без повторень.

Розміщеннями з n елементів по k називаються впорядковані k-елементні підмножини даної n-елементної множини. Кількість таких розміщень позначається . Справедлива формула: (для довільних натуральних n і k, причому k≤ n).

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

Комбінаціями з n елементів по k називаються k-елементні підмножини даної n-елементної множини. Позначається їх кількість . Справедлива формула: (для довільних натуральних n і k, причому k≤ n).

Задачі для самостійного розв’язування

1. (А) Треба сформувати команду космічного корабля з 3 чоловік: командир (4 кандидати), інженер (3 кандидати), лікар (5 кандидатів). Скільки є всього способів?

2. (Б) Розв’язати попередню задачу, врахувавши психологічну сумісність: К1 сумісний з І1, І3; Л2, Л3. К2 сумісний з І1, І2 і всіма лікарями. К3 сумісний з І1, І2; Л1, Л3. К4 сумісний з усіма інженерами та Л2. Крім того відомо, що І1 не сумісний з Л3, І2 не сумісний з Л1, а І3 не сумісний з Л2.

3. (А) Скільки двоцифрових чисел можна скласти з цифр 1, 2, 3, 4, 5, 6?

4. (А) Щоб дістатися з Києва до Одеси, можна вибрати один з 4 залізничних чи один з 3 автобусних рейсів. Скільки є варіантів здійснити подорож за маршрутом: а) Київ–Одеса–Київ; б) Київ–Одеса–Київ, якщо повертатися з Одеси до Києва поїздом; в) Київ–Одеса–Київ, якщо їхати до Одеси і назад різними рейсами?

5. (А) Дівчина має три костюми по два елементи у кожному. Скільки варіантів одягу вона може утворити, якщо одночасно їй доводиться одягати два елементи одягу?

6. (А) У змаганнях беруть участь 15 чоловік. Скількома способами може бути присуджена золота, срібна, бронзова медалі?

7. (А) Скількома способами можна скласти список з 8 учнів?

8. (А) Будинок фарбують у три різні кольори: одним – стіни, другим – дах, третім – віконні рами й двері. Скількома способами можна пофарбувати будинок, якщо є 5 кольорів фарби?

9. (А) Із 8 троянд і 6 жоржин потрібно скласти букет так, щоб у ньому було 2 троянди і 3 жоржини. Скількома способами це можна зробити?

10. (А) У складі ланки хокейної команди 3 нападники, 2 гравці захисту і воротар. Скільки різних ланок може сформувати тренер, якщо у нього є 6 нападників, 4 гравці захисту і 2 воротарі?

11. (А) Скількома способами 10 чоловік можуть стати в чергу один за одним?

12. (А) З 10 членів правління АТ „ZIMALETTO” потрібно вибрати трьох на посади голови, його заступника та секретаря. Скількома способами це можна зробити?

13. (А) Чотири види молекул – А, В, С, D – можуть з’єднуватися по три молекули в ряд, тобто утворювати упорядковані трійки, причому в трійці всі молекули різні. Скільки різних трійок може утворитися за цих умов?

14. (А) Скільки „слів” з 7 букв можна скласти із букв слова „вибірка”?

15. (Б) Рота складається з 3 офіцерів, 6 сержантів, 60 рядових. Скількома способами можна виділити з них загін з 1 офіцера, 2 сержантів і 20 рядових? Розв’язати задачу за умови, що в загін входить командир роти і старший із сержантів.

16. (Б) Скількома способами можна групу з 15 учнів поділити на дві так, щоб в одній було 11, в другій 4 учні?

17. (Б) Скількома способами можна 15 шахістів поділити на 3 групи по 5 чоловік?

18. (Б) Скільки 4-значних чисел можна скласти із цифр числа 3694, щоб кожну цифру використовувати 1 раз? А парних чисел?

19. (Б) 5 дівчат і 3 хлопців треба розбити на 2 команди по 4 чоловіки, щоб в кожній був хоча б 1 хлопець. Скількома способами це можна зробити?

20. (Б) З повного шахового набору взяли 4 фігури або пішки. В скількох випадках серед них буде: а) два слона? б) не менше двох слонів?

21. (Б) З 4 чашок, 5 блюдець і 6 чайних ложок (всі різні) треба накрити на стіл для 3 чоловік. Скількома способами це можна зробити?

22. (Б) 10 друзів зайшли в кафе відсвяткувати успішне складання іспитів. Власник кафе сказав: «Приходьте щодня, сідайте за той самий стіл тільки в іншому порядку. Після цього я пригощатиму вас безкоштовно». Чи варто погодитись друзям на його пропозицію?

23. (Б) Скільки натуральних чисел, менших за 1000, можна скласти з цифр 3, 5 і 7?

24. (Б) Скількома способами можна зробити трьохколірний прапорець з горизонтальними смужками однакової ширини, якщо є тканина шести різних кольорів? Розв’язати задачу за умови, що один колір має бути червоним.

25. (Б) З 52 делегатів конференції треба вибрати президію з 5 чоловік і делегацію з 3 чоловік. Скількома способами можна здійснити вибір, якщо: а) члени президії можуть входити до складу делегації; б) члени президії не повинні входити до складу делегації.

26. (Б) Із 12 книг — 9 різних авторів і трьохтомник. Усі вони розміщені на книжковій полиці. Скількома способами їх можна розмістити на полиці так, щоб книги автора трьохтомника стояли поруч?

27. (Б) Скільки різних шестизначних чисел можна скласти із цифр 1, 2, 3, 4, 5, 6 і 7, щоб цифри не повторювалися і крайні цифри були парними?

28. (Б) У Ніни є сім різних книг з математики, а у Слави – дев’ять різних книг з філософії. Скількома способами вони можуть обмінятися один з одним п’ятьма книгами?

29. (В) Дано натуральні числа від 1 до 30. Скількома способами можна вибрати три числа так, щоб їх сума була парною?

30. (В) У шаховому турнірі зіграно 210 партій, причому кожен гравець зіграв із кожним з решти по одній партії. Скільки спортсменів брало участь у турнірі?

31. (В) У школі навчається 1200 учнів. Довести, що принаймні двоє з них мають однакові ініціали (імені і по батькові).

32. (В) В класі 30 учнів. Кожного дня чергують двоє. Чи можна скласти графік чергувань так, щоб ніякі два учні не чергували разом двічі протягом року?

33. (В) Із цифр 1, 2, 3, 4 і 5 складають різні п’ятицифрові числа, які не містять однакових цифр. З’ясувати, скільки серед цих чисел таких, які: а) починаються з цифри 3; б) не починаються цифрою 5; в) починаються із числа 54; г) не починаються з числа 54; д) є парними; е) діляться на 4.