Элементы комбинаторики

Елементи комбінаторики

Приклад 7. Три стрільці повинні влучити по 15 мішеням (кожен по 5). Скількома способами вони можуть розподілити мішені між собою?

Розв’язання. Для першого стрільця існує C155 різних варіантів, другому залишиться 10 мішеней, із яких він може зробити вибір C105 способами, третьому — решта 5.

Усього способів: C155 C105 C55 = 756756 .

Відповідь: 756 756.

Приклад 8. Із 15 працівників фірми директорові необхідно вибрати бухгалтера, його помічника, двох менеджерів і чотирьох кур’єрів. Скількома способами він може це зробити?

Розв’язання

II спосіб: A152 C132 C114 = 5405400 . Відповідь: 5 405 400.

Приклад 9. Є колода з 36 карт. Скількома способами можна витягнути 6 карт так, щоб:

а) був рівно один туз; б) не було жодного туза; в) був хоча б один туз;

г) серед цих шести був рівно один туз і один король; д) серед цих шести були туз і король однієї масті.

Розв’язання

а) Туз із колоди можна вибрати C41 способами. Будемо вибирати решту 5 із 32 карт, тому що тузи нам уже не потрібні. Це можна зробити C325 способами. Тоді маємо:

б) необхідні 6 карт вибиратимемо із колоди без тузів, тобто C326 = 906192 способами;

в) I спосіб: від усіх можливостей вибору по 6 карт, а таких C366 , віднімемо ті варіанти, у яких взагалі немає тузів, тобто C326 , тоді залишаться випадки, де серед шести буде «хоча б один туз»: C366 − C326 = 1041600 ;

34

Елементи комбінаторики

II спосіб: якщо туз один, то виборів буде C41 C325 , якщо два —

г) туз можна вибрати C41 способами, короля — C41 , а решта 4 із колоди без тузів і королів — C284 .

Відповідь:а)805 504;б)906 192;в)1 041 600;г)327 600;д)81 900.

Приклад 10. У лотереї «5 із 36» головний виграш одержить той, хто вгадає всі 5 номерів. Той, хто вгадає 4, 3 або 2, одержує менший виграш. Скільки може бути різних карток, де вгадано:

а) 4 номери; б)   3 номери?

Розв’язання

а) Варіантів угадування «правильних» 4-х номерів існує C54 . До цих 4 приєднаємо ще один «неправильний», який можна вибрати C311 способами. Усього C54 C314 = 155 карток;

Зауваження. C54 = C51 , C53 = C52 .

Відповідь: а) 155; б) 4650.

Приклад 11. Скільки різних дільників має число 2310? Розв’язання. Розкладемо число 2310 на прості множники

і складатимемо їх різні добутки (від 1 до 5 множників), тобто складатимемо різні підмножини. 2310 = 2 3 5 7 11 — усього п’ять

множників. Тоді маємо: C50 + C51 + C52 + C53 + C54 + C55 = 32 . Зверніть увагу, що всі множники числа 2310 різні.

Відповідь: 32.

Приклад 12. Людина має 6 друзів. Щодня вона запрошує до себе трьох із них так, що компанія жодного разу не повторюється. Скільки для цього їй потрібно днів?

Розв’язання. C3 = 6 5 4 = 20 (днів).

6 2 3

Відповідь: 20.

35

Елементи комбінаторики

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

1.Скількома способами можна вибрати трьох чергових із класу, в якому навчається 20 учнів?

2.Скільки можна побудувати трикутників, якщо за їхню вершину брати вершини правильного 12-кутника?

3.Скількома способами можна вибрати з 15 різних слів набір, що складається не більше ніж із 5 слів (зміст не важливий)?

4.У мами 2 яблука і 3 груші. Щодня протягом п’яти днів по­ спіль вона видає по одному фрукту. Скількома способами це може бути зроблено?

5.Як зміниться розв’язання попередньої задачі, якщо до існуючих фруктів додати 4 банани?

6.П’ятеро друзів при святкуванні Нового року завжди обмінюються поцілунками і подарунками.

а) Скільки поцілунків ви зможете нарахувати?

б) Скільки подарунків необхідно для святкування Нового року?

7.У класі навчаються 14 хлопчиків і 10 дівчаток. Для привітання гостей необхідно вибрати чотирьох хлопчиків і трьох дівчаток. Скількома способами це можна зробити?

8.Скількома способами можна:

а) розбити 15 осіб на три команди по 5 осіб у кожній; б) вибрати з 15 осіб дві команди по 5 осіб?

9. Як зміниться розв’язання задачі 7, якщо необхідно вибрати трьох учнів для привітання, серед яких буде:

а) хоча б одна дівчинка; б) представники обох статей?

10.В одного учня є 7 книг з історії культури, а в іншого — 5 книг

зфілософії. Скількома способами вони можуть обміняти дві книги одного на дві книги іншого?

11.Є колода із 36 карт. Скількома способами можна витягнути 8 карт так, щоб:

а) було рівно два тузи; б) було хоча б два тузи;

в) не було жодного туза, жодного короля; г) були туз і король різних мастей?

36

Елементи комбінаторики

12.У лотереї «6 із 49» головний приз дістанеться тому, хто вгадав усі шість номерів. Менший виграш одержать ті, хто вгадав 5, 4 або 3 номера.

Скільки може бути різних карток, де вгадані: а) усі 6 номерів; б) 4 номери; в) хоча б 4 номери?

13.Людина має 10 друзів і протягом декількох днів запрошує: а) трьох із них; б) деяких із них так, що компанія жодного разу не повторю­ ­

ється.

Скільки днів вона може так робити?

14.Скільки різних дільників має число 510?

15.Для премій з математичної олімпіади виділено три примірники однієї книги, два примірники другої і один примірник третьої. Скількома способами можуть бути вручені премії, якщо в олімпіаді брало участь 20 чоловік і нікому не дають два примірники однієї книги, але можуть бути вручені дві або три різні книги?

37

Елементи комбінаторики

5. Розміщення з повтореннями

Стислі теоретичні відомості

•• Розміщенням із повтореннями з n різних елементів по m еле-

ментів називається кожна його впорядкована підмножина, що складається з m елементів, у якій елементи можуть повторю­ ватися.

Позначення: Anm = nm .

Приклад. У школу прийшли три нові дев’ятикласники. Скількома способами їх можуть зарахувати до школи, якщо у паралелі 9-х класів 4 класи?

Розв’язання. Коженізучнівможепотрапитиабовперший,або в другий, або в третій, або в четвертий клас. Тобто для кожного учня існує 4 можливості. Разом за правилом добутку маємо 4 4 4 = 43 .

Очевидно, що в задачах на розміщення з повтореннями m може бути більше n.

Класична задача. У кожний із n ящиків може бути поміщений будь-який із m об’єктів. Скільки є варіантів такого розподілу?

Розв’язання. Перший об’єкт може бути поміщений у кожний із n ящиків, тобто існує n способів розподілу. Для другого об’єкта також існує n ящиків — n способів, і так для всіх об’єктів. Усього

за правилом добутку маємо: n n … n = nm способів.

m

Приклади розв’язування задач

Приклад 1. На першому поверсі в ліфт сіло 10 осіб. Ліфт піднімається до 6 поверху, і на кожному поверсі можуть виходити люди. Скількома способами можуть бути розподілені пасажири на 6 поверхах?

Розв’язання. Перший пасажир може вийти на 2, 3, ..., 6-му поверхах. Усього 5 способів. Так само для другого, третього і решти пасажирів є по 5 способів розподілу. Тоді маємо всього 510 спо­ собів.

Уданій задачі поверхи — це «ящики» (див. класичну задачу),

апасажири — «об’єкти», що розкладаються по «ящиках».

Відповідь: 510 .

38

Елементи комбінаторики

Приклад 2. Ліфт, у якому 9 пасажирів, може зупинитися на 10 поверхах. Пасажири виходять групами по дві, три і чотири особи. Скількома способами вони можуть вийти, якщо ліфт не повертається на поверх, на якому вже був?

Розв’язання. Умова цієї задачі відрізняється від попередньої обмеженням на групи, а саме 2, 3 і 4 особи. Складатимемо ці групи. Вийде C92 C73 C44 способів складання груп. Також має значення, на якому поверсі вийде та чи інша група, тобто важливий порядок

Усього 105 =100000 номерів; б) на першому місці може опинитися кожна з 9 цифр, а на ін-

39

Елементи комбінаторики

Приклад 5. Є 5 ручок і 3 олівці. Скільки є комбінацій для вибору кількох предметів так, щоб серед обраних були і ручки, і олівці?

Розв’язання

I спосіб: кожен олівець або входить, або не входить до потрібної комбінації. Тому маємо 23 способів вибору олівців. Оскільки хоча б один олівець має бути обраний, то виключимо той випадок, коли жоден олівець не обраний, одержуємо 8−1=7 .

Аналогічні міркування проводимо для вибору ручок: 31 комбінація.

За правилом добутку маємо 7 31=217 .

II спосіб: складемо різні двох-, трьохелементні множини, пам’ятаючи при цьому, що до кожної множини входить хоча б

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

Розв’язання. Цю задачу доцільно розв’язувати «навпаки», тобто 10 книг можна переплести у 3 кольори 310 способами. Якщо для переплетення книг використовувати 2 кольори, то це буде 3 210 способів (червоний і зелений — 210 , червоний і синій — 210 , зелений і синій — 210 ).

Якщо ж переплітати книги якимось одним кольором, то таких варіантів буде 3. Тепер віднімемо від загального числа способів переплетення у 3 кольори ті варіанти, коли використовується не більше двох кольорів і один колір: 310 −3 210 −3.

Відповідь: 310 −3 210 −3.

Приклад 7. Групі з 10 туристів (4 дітей і 6 дорослих) запропонували відвідати 5 музеїв, причому до двох із них дітей не пускають. Скільки існує способів розподілу туристів по музеях?

Розв’язання. Діти можуть відвідати тільки 3 музеї із запропонованих, для них існує 34 способів, а дорослі — всі 5, для них — 56 способів. Усього маємо 34 56 способів.

Відповідь: 34 56 .

40

Елементи комбінаторики

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

1.Двох братів привели у Будинок дитячої творчості, де працює 5 різних гуртків. Скільки є варіантів для зарахування хлопців до гуртків, якщо кожен хлопчик може відвідувати тільки один ­гурток?

2.Номери трамвайних маршрутів колись позначали двома кольоровими ліхтарями. Яку кількість різних маршрутів можна по­ значити, якщо використовувати ліхтарі шести кольорів?

3.Два листоноші повинні рознести 8 листів за вісьмома адресами. Скількома способами вони можуть розподілити цю роботу?

4.Поїзд метро робить 10 зупинок, не враховуючи початкової, під час яких виходять усі пасажири і не заходять нові. Скількома способами можуть бути розподілені між цими зупинками 200 пасажирів, які ввійшли у поїзд на початковій зупинці?

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

6.Трамвайні маршрути позначають одним, двома або трьома кольоровими ліхтарями. Яку кількість різних маршрутів можна скласти, якщо використовувати ліхтарі шести кольорів?

7.Є 6 різних троянд і 3 різні гілки папороті. Скільки існує варіантів вибору квітів за умови, що у виборі беруть участь і троянди, і папороть? (Слід врахувати, що одна троянда й одна папороть обов’язково мають бути обрані.) Як зміниться розв’язування задачі, якщо додасться 5 різних ромашок, які також будуть брати участь

увиборі?

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

9.У шаховій зустрічі беруть участь дві команди по 8 членів

укожній. Кожна пара суперників і колір фігур визначаються жеребкуванням. Яка кількість різних результатів жеребкування?

41

Елементи комбінаторики

6. Перестановки з повтореннями

Стислі теоретичні відомості

Нехай є множина, що складається із n елементів, серед яких знайдеться m однакових. Скільки різних перестановок вийде з цих елементів?

Зрозуміло, що деякі з перестановок збігатимуться через повторювані елементи. Шукана кількість перестановок буде меншою за число перестановок із n елементів у стільки разів, скільки перестановок можна зробити з m елементів, тобто у m! разів.

Якщо шукане число перестановок x і воно менше за число всіх перестановок у m! разів, то x m! = n! x = mn!! . Якщо в даній мно-

жині знайдеться інша група однакових елементів кількістю k, то,

Pn1 …nk,n.

Приклад. Скількома способами можна переставити букви слова: а) «телефон», б)   «коробок»?

Розв’язання

а) У слові «телефон» 2 однакові букви («е»). Тоді кількість пе-

рестановок P2,7 = 7!2! = 2520;

б) із семи букв 2 букви «к» і 3 букви «о». P2,3,7 = 27! 3!! = 420.

Приклади розв’язування задач

Приклад 1. П’ятицифровий телефонний номер складається із двох трійок і трьох четвірок, але в якому порядку вони стоять, хлопчик забув. Скільки йому потрібно зробити спроб, щоб напевно додзвонитися своєму другові?

42

Елементи комбінаторики

дасться 4 перетинки, тобто 4 однакових елементи. Кількість перестановок дорівнює P4,24 = 244!! .

Відповідь: 244!! .

Приклад 5. Клоун кидає 10 кілець на 6 стрижнів. Скільки варіантів потрапляння кілець на стрижні може вийти, якщо клоун жодного разу не промахнувся?

Розв’язання. До 10 кілець додається 5 проміжків між кільцями. Тоді маємо P5,15 = 155!! .

Відповідь: 155!! .

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

1.Знайдіть кількість різних чотирицифрових чисел, які можна одержати при перестановці цифр 2, 2, 4, 4.

2.Скільки різних «слів» можна утворити перестановкою букв

слова:

а) «змея»; б)   «змеелов»; в)   «заземление»?

3. Скільки шестицифрових чисел можна скласти із двох «п’ятірок» і чотирьох «сімок»?

43