ЗАДАЧІ КОМБІНАТОРИКИ(практична робота)

ЗАДАЧІ КОМБІНАТОРИКИ

Варіант 1

1.    В їдальні маємо  4 перших страви, і 6 других страв. Скількома способами можна скласти  обід із двох страв?

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

3.    У шкільній бібліотеці маємо десять різних книг Тараса Шевченка,  три різні книги Григорія Сковороди, тринадцять різних книг Миколи Гоголя. Скількома способами учень може зробити вибір трьох книг так, що серед них була одна книга будь-якого автора?

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

5.    Скільки чисел серед першої сотні натураль­них чисел не діляться ні на 4, ні на 5, ні на 7?

6.    Для автомобільних номерів використовуються 10 цифр і 28 вісім букв. Кожний номер складається з із трьох букв і чотирьох цифр(окрім номера 00-00). Яке найбільше число машин може отримати номер?

7.    Алфавіт має 33 букви. Скільки можна скласти слів, що містять не більше чотирьох букв, якщо у словах усі букви різні?

8.    В організації ООН визнано п’ять міжнародних мов спілкування. Скільки треба мати двомовних словників в цій організації для перекладу, щоб   перекладати із будь-якої міжнародної мови на будь-яку іншу міжнародну мову.

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

10.    У класі 10 юнаків і 12 дівчат. Для участі в концерті потрібно виділити танцювальний дует (юнак + дівчина), тріо гітаристів(троє дівчат). Скількома способами можна це здійснити?

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

12.    У футбольному чемпіонаті беруть участь 16 команд.  Скільки ігор мають зіграти усі команди, якщо кожна команда грає дві гри, у себе дома і на виїзді? Чи може цей чемпіонат пройти у весняний та осінній періоди, якщо на один день весни або осені припадає тільки одна гра чемпіонату?

13.    Скільки цифр "9" у ряді чисел від 1 до 100?

14.    За кордон поїхала група туристів із 100 чоловік. 10 із них не знали ні німецької, ні  французької мови. 75 знали німецьку мову. 83 людини знали французьку мову. Скільки туристів володіли двома іноземними мовами?

15.    На вершину гори веде 7 доріг. Скількома способами турист може піднятись на гору і спуститись з неї? Дайте відповідь на те ж саме запи­тання, якщо підняття і спуск відбуваються: а) різними шляхами; б) однаковими шляхами.

16.    Скільки різних цілих дільників має число 2²∙4³?

17. Із загону у 50 скаутів,  серед яких є наймолодший скаут Макс визначається караул із 4 чоловік. Скільки різних способів утворити караул?  Допоможіть Максу знайти у скількох випадках він попадає в караул.

18. В класі вивчають 10 предметів. В понеділок 6 уроків, причому всі уроки різні. Скількома способами можна скласти розклад на понеділок, якщо дві математики(алг. та геом.) стоять підряд?

19. 4 хлопчиків і 4 дівчаток сідають в ряд на 8 розташованих поруч стільців, причому хлопчики сідають на місця з непарними номера­ми, а дівчатка – на місця з парними номерами. Скількома способами це можна  зробити?

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

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

22. а)Скількома способами можна вказати на ша­ховій дошці два квадрати – білий та чорний? б) Розв'яжіть цю задачу, якщо немає обмежень на колір квадрата.  в) Розв'яжіть її, якщо потрібно вибрати два білих квадрати.

Задачі комбінаторики

   Варіант  2

1. В магазині "Все до чаю"  є п'ять різних чашок та 3 різних блюдця. Скількома способами можна купити чашку з блюдцем?

2. В магазині "Все до чаю" є п'ять різних чашок та 3 різних блюдця та  4 чайні ложки. Скількома способами можна купити комплект з чашки, блюдця та ложки?

3. В Країні Чудес є три міста: А, Б і В. З міста А в місто Б ведуть 6 доріг, а з міста Б у місто В – 4 дороги . Скількома способами можна проїхати від А до В?

4. Скільки чисел серед першої сотні натураль­них чисел не діляться ні на 2, ні на 3, ні на 5?

6. Назвемо натуральне число "симпатичним", якщо в його запису зустрічаються тільки непарні цифри. Скільки існує 5-цифрових "симпатичних" чисел?

7.  Монету кидають тричі. Скільки різних послідовностей орлів та решок можна при цьому отримати?

8. Кожну клітинку квадратної таблиці 3x3 можна пофарбу­вати в чорний або білий колір. Скільки існує різних розфарбувань цієї таблиці?

9. Скількома способами можна заповнити одну картку в ло­тереї "Спорт прогноз"? (В цій лотереї треба передбачити підсумок тринадцяти  спортивних матчів. Підсумок кожного матчу – перемога однієї з команд або нічия; рахунок не має значення.)

10. Алфавіт племені Мумбо-Юмбо складається з трьох літер А, Б та В. Слово – будь-яка послідовність, яка складається не більше як з 4 літер. Скільки слів в мові племені Мумбо-Юмбо?

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

12. У футбольному чемпіонаті беруть участь 14 команд.  Скільки ігор мають зіграти усі команди, якщо кожна команда грає дві гри, у себе дома і на виїзді? Чи може цей чемпіонат пройти у весняний та осінній періоди, якщо на один день весни або осені припадає тільки одна гра чемпіонату?

14.  За кордон поїхала група туристів із 120  чоловік. 21 із них не знали ні німецької, ні  французької мови. 85 знали німецьку мову. 93 людини знали французьку мову. Скільки туристів володіли двома іноземними мовами?

15. Є група школярів, серед яких п'ють тільки каву 12, п'ють тільки чай – 10, п'ють тільки йогурт – 8, п'ють тільки каву і чай – 5, п'ють тільки каву і йогурт – 4, п'ють тільки чай і йогурт – 3, усі три напої – 1. Скільки всього школярів у групі?

16. Скільки існує непарних  п’ятицифрових чисел, для запису яких використовуються тільки цифри: а) 6, 2, 3, 4, 7;  б) 0, 4, 1, 6, 5?

17. На вершину гори веде 7 доріг. Скількома способами турист може піднятись на гору і спуститись з неї? Дайте відповідь на те ж саме запи­тання, якщо підняття і спуск відбуваються: а) різними шляхами; б) однаковими шляхами.

18. Скільки різних цілих дільників має число 3³∙5²?

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

20. В класі вивчають 14 предметів. В понеділок 7 уроків, причому всі уроки різні. Скількома способами можна скласти розклад на понеділок?

21. П'ять хлопчиків і 5 дівчаток сідають в ряд на 10 розташованих поруч стільців, причому хлопчики сідають на місця з непарними номера­ми, а дівчатка – на місця з парними номерами. Скількома способами це можна  зробити?

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

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

22. На зборах мають виступити 5 чоловік: А, Б, В, Г, Д. Скількома способами можна їх розташувати у список промовців, якщо: Б не повинен виступати перед А;  якщо Б мусить виступити відразу за А?

23. У спортивному таборі  65  дітей вміють грати в футбол, 70  — у волейбол і  75  — у баскетбол. Всього дітей у таборі 100.  Яка а)найменша ; найбільша кількість дітей, які вміють грати і у футбол, і у баскетбол, і у волейбол?

Задачі комбінаторики

Варіант 3

1.В їдальні маємо  3 перших страви, і 2 других страв. Скількома способами можна скласти  обід із двох страв?

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

3.У шкільній бібліотеці маємо сім різних книг Тараса Шевченка,  дві різні книги Григорія Сковороди, вісім  різних книг Миколи Гоголя. Скількома способами учень може зробити вибір трьох книг так, що серед них була одна книга будь-якого автора?

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

5.  Скільки цифр "2" у ряді чисел від 1 до 100?

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

7 . Скількома способами можуть розташувати­ся у турнірній таблиці 10 футбольних команд, якщо відо­мо, що ніякі дві команди не набрали порівну очок?

8. Скільки чотиризначних чисел можна утво­рити з цифр 0, 1,2, 3, не повторюючи їх?

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

10. Є 8 токарів.  Скількома способами можна доручити трьом із них виготовлення трьох різних деталей по одному виду на кожного.

11.  До профкому обрано 9 чоловік. З них треба обрати голову, його заступника, секретаря та культорга. кількома способами це можна зробити?

12. Скількома способами можна вкинути 5 лист­ів в 11 поштових скриньок, якщо до кожної скриньки вкинути не більше одного листа?

13. На зборах мають виступити 5 чоловік: А, Б, В, Г, Д. Скількома способами можна їх розташувати у список промовців, якщо:

1)      Б не повинен виступати перед А;

2)      якщо Б мусить виступити відразу за А?

14. Скільки різних натуральних чисел можна утворити з цифр 0, 1, 2, 3, 4, якщо кожне число містить кожну з даних цифр не більше одного разу?

15.У розиграші першості країни з футбола бере участь 16 команд. Скількома способами можуть бути розподілені золота і срібна медалі?

16.В наряд можна послати трьох чоловік, одного із п’яти офіцерів, одного із семи сержантів і одного із 20 солдат. Скількома способами можна скласти наряд?

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

18. Скільки діагоналей у правильному а)шестикутнику; б) семикутнику?

19. 3 хлопчиків і 3 дівчаток сідають в ряд на 6 розташованих поруч стільців, причому хлопчики сідають на місця з непарними номера­ми, а дівчатка – на місця з парними номерами. Скількома способами це можна  зробити?

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

21. Скільки різних дільників має число 8²∙9⁴?

22. Автомобільні номери складаються з однієї, двох або трьох букв і чотирьох цифр. Знайти число таких номерів, використовуючи 30 букви  алфавіту.

23. На танцмайданчику зібралися 8 юнаків та 8 дівчат. Скількома способами вони можуть розбитися на пари для участі в черговому танці?     

24. Чемпіонат України по шахам проводиться в одне коло. Скільки грається партій, якщо участь беруть 18 шахматистів?

25. Скількома способами можна поселити 7 студентів у 3 кімнати: одномісну, двомісну та чотиримісну?     

26. Скільки чисел серед першої сотні натураль­них чисел не діляться ні на 2, ні на 3, ні на 5?

27. У класі з 40 учнів 30 уміють плавати, 27 уміють грати у шахи і тільки 5 не вміють ні того, ні іншого. Скільки учнів уміють плавати і грати у шахи?

28. У групі зі 100 туристів 70 знають ан­глійську мову, 45 - французьку і 23 - знають обидві мови. Скільки туристів у групі не знають ні англійської, ні французької?

ФОРМУЛИ КІЛЬКОСТІ ЕЛЕМЕНТІВ СКІНЧЕНИХ МНОЖИН

ФОРМУЛИ КІЛЬКОСТІ ЕЛЕМЕНТІВ СКІНЧЕНИХ МНОЖИН

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

Кількість елементів об'єднання  п(А+В)  будь-яких двох скін­ченних множин А і В обчислюється за формулою:

п(А+В) = п(А) + п(В) - п(АВ).

Для будь-якої трійки скінченних множин А₁, А₂, А₃ має місце формула кількості елементів множини п(A₁ + А₂ +А₃) , що є об’єднанням трьох множин, тобто 

A₁₊ А₂ +А₃:

п(A₁ + А₂ +А₃) = п(А₁) + п(А₂) + п(А₃) - п(А₁А₂) - п(А₁ А₃) - п(А₂ А₃) + п(А₁А₂ А₃).

Наводимо приклад використання поданих вище формул.

Задача  3. У лабораторії науково-дослідного інституту працює декілька чоловік, причому кожний з них знає хоча б одну іноземну мову, 6 чоловік знають англійську, 6 ‒ німецьку, 7 ‒ французьку, 4 знають англійську і німець­ку, 3 ‒ німецьку і французьку, 2 ‒ французьку і англійсь­ку, один чоловік знає всі три мови. Скільки чоловік пра­цює в лабораторії? Скільки з них знає лише англійську мову? Скільки чоловік знає лише одну мову?

Розв'язання.

Позначимо п(А), п(Н), п(Ф) кількість співробітників у лабораторії, які знають англійську, німецьку та фран­цузьку  мови   відповідно,  а   п(НФ),  п(АН),  п(АФ), п(АНФ) ‒  кількість чоловік, що знають по дві і три мови відповідно. Тоді, за правилом суми, загальне число співробітників у лабораторії дорівнює

m = п(А)+ п(Н) + п(Ф) - п(НФ) - п(АН) - п(АФ) + п(АНФ)  = 6 + 6 + 7 - 3 - 4 - 2 + 1 = 11.

Тільки англійську та німецьку мови знають

п_АН = п(АН) ‒ п(АНФ) = 4-1= 3 чоловіка, тільки англійську і французьку

п_АФ = п(АФ) - п( АНФ) = 2-1= 1 чоловік. Тоді тільки англійську мову знає

п_А = п(А) - п_АН  – п_АФ - п( АНФ) =  6-3 -1-1 =1 чоловік. Тільки німецьку і французьку знають

п_НФ = п(НФ) - п(АНФ) = 3 ‒ 1 = 2 чоловіки. Тоді більше однієї мови знають

k = п(АНФ) + п_АН + п_АФ + п_НФ = 1 +3+1+2 =7 чоловік, її тільки одну мову  p = п - т = 11- 7 = 4 чоловіка.

Двома основними правилами комбінаторики є:

Принцип суми. Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то об’єднання двох множин AÅB містить m+n елементів.

Принцип добутку. Якщо множина A містить m елементів, а множина B – n елементів, то добуток двох множин AÄB містить m∙n елементів, тобто пар.

Приклад. При A={a, b, c} розміщення з повтореннями по два елементи – це пари (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c). Або, принцип добутку: 3∙3 = 9 пар.

Приклад. В одному з відділів магазину покупці зазвичай купляють або один торт, або коробку цу­керок. Одного дня було продано 57 тортів та 36 коробок цукерок. Скільки було покупців, якщо 12 з них придбали і торт, і коробку цукерок? Використаємо принцип суми: 57 + 36 - 12 = 81.

Задача для самостійного опрацювання.

1.Скільки чисел серед першої сотні натураль­них чисел не діляться ні на 4, ні на 5, ні на 7?

2. У спортивному таборі  65  дітей вміють грати в футбол, 70  — у волейбол і  75  — у баскетбол. Всього дітей у таборі 100.  Яка а)найменша; б)найбільша кількість дітей, які вміють грати і у футбол, і у баскетбол, і у волейбол?

Поняття факторіалу. Розміщення. Перестановки.

Поняття факторіалу.

Факторіалом числа n, де n — ціле невід’ємне число називають добуток всіх натуральних чисел від 1 до n.

Позначають це так n! Отже, n! = 1 ∙ 2 ∙ 3 ∙...∙ (n - 1) ∙ n. За означенням приймають 0! = 1. Наприклад, 4! = 1 ∙ 2 ∙ 3 ∙ 4 = 24.

Приклад. Спростити вираз 6!/5!.

Розв’язання. Маємо 

Розміщення.

Нехай дано множину X з n елементів х₁,х₂,х_n-1,х_n.

Розміщенням з n елементів по m (m < n) називають будь-яку впорядковану підмножину У множини X, причому дві такі підмножини вважають різними, якщо вони відрізняються складом або порядком елементів.

Приклад 1. Нехай дано множину Х = {1;2;3}. Тоді по одному можна скласти такі розміщення:

(1), (2), (3) - їх буде 3;

по два можна скласти такі розміщення:

(1;2), (1;3), (2;1), (2;3), (3;1), (3;2) - їх буде 6;

по три можна скласти такі розміщення:

(1;2;3), (1;3;2), (2;1;3), (2;3;1), (3;1;2), (3;2;1) - їх буде 6.

Кількість розміщень з n елементів по m позначають А^m_n. Можна записати 

Формула для обчислення:

Цю формулу можна запам’ятати за допомогою такого правила:

А^m_n є добутком т натуральних чисел, починаючи з n, взятих у порядку спадання.

Наприклад, А⁴₇ = 7 ∙ 6 ∙ 5 ∙ 4 = 840.

А^m_n можна обчислювати ще й за такою формулою:

Приклад 2. Розклад на день містить 6 уроків. Визначити кількість всіх можливих розкладів при виборі з 9 предметів, при умові, що жоден предмет не стоїть у розкладі двічі.

Розв’язання. Зрозуміло, що таких розкладів буде

А⁶₉ = 9 ∙ 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 = 60480.

Приклад 3. Скільки різних правильних дробів можна скласти з чисел 1; 3; 5; 7; 11; 13; 17; 19, які використовують для запису чисельника і знаменника дробу?

Розв’язання. Дробів, у яких чисельник не дорівнює знаменнику можна скласти А²₈ штук, але лише половина з них правильні. Отже, шукана кількість дробів 

Перестановки.

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

Кількість перестановок з п елементів позначають Р_n. З означення випливає, що Р_n = Аⁿ_n. Тоді враховуючи формулу для А^m_n та 0! = 1, маємо  Отже,

Приклад 1. Скількома способами можна розставити на полиці 6 книжок?

Розв’язання. Очевидно, що шукана кількість способів дорівнює кількості перестановок з 6 елементів (книг): Р₆ = 6! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720.

Приклад 2. Скільки різних чотирицифрових чисел можна скласти з цифр 0; 1; 2; 3, якщо в кожному числі жодна з цифр не повторюється?

Розв’язання. З чотирьох цифр 0; 1; 2; 3 можна утворити Р₄ перестановок. Але ті перестановки, які починаються з нуля не будуть записами чотирицифрових чисел, таких перестановок — Р₃. Отже, шукана кількість чотирицифрових чисел дорівнює Р₄ - Р₃ = 4! - 3! = 3!(4 - 1) = 6 ∙ 3 = 18.





Комбінаторика. Правило суми і правило добутку

Комбінаторика у класичному розумінні (сучасна назва — комбінаторний аналіз) — це розділ математики, присвяче­ний розв'язанню задач про вибір та розміщення елементів скінченної множини згідно із заданими правилами. Ці правила визначають спосіб побудови деякої конструкції — ком­бінаторної сполуки (конфігурації). Вивчати властивості цих сполук та підраховувати кількість різних способів їх побу­дови зручно у такій послідовності:

а)  спочатку формулюється класична (ключова) задача, яка приводить до комбінаторної конфігурації, що вивча­ється;

б) потім наводиться розв'язання цієї задачі та виведення основної формули;

в)  після цього будується математична модель комбіна­торної сполуки і мовою теорії множин дається її точне означення.

Множина та її елементи. 

Числові множини

Операції над множинами

На основі поняття сукупностей, які утворені з обмеженої кількості об’єктів, об’єднаних деякою спільною ознакою, виникло поняття множини.

Об’єкти, з яких складається множина, є елементами множини. Множина однозначно визначається її елементами.

Для позначення множин використовують великі латинські літери А, В, С…

Для позначення елементів множин використовують маленькі латинські літериа, b, c, …

Якщо множина має скінченну кількість елементів, то вона називаєтьсяскінченною множиною

Якщо множина має нескінченну кількість елементів, то вона називаєтьсянескінченною множиною

Множина А вважається підмножиною множини В, якщо кожен елемент множини А є й елементом множини В.

Множина, яка не містить жодного елемента, є порожньою множиною.

Порожня множина є підмножиною будь-якої множини.

Множини А і В називаються рівними, якщо вони містять одні і ті ж самі елементи.

У математиці велику роль відіграють такі числові множини:

Натуральними називаються числа, якими можна рахувати: 1, 2, 3, …

Множина N натуральних чисел – нескінченна множина, до якої належить число 1 і всі наступні числа, кожне з яких на 1 більше від попереднього.

Цілими є числа натуральні, протилежні їм і число 0.

Множина Z цілих чисел – нескінченна множина, до якої належить число 0, множина натуральних чисел і всі числа, протилежні натуральним.

Раціональними називаються числа, які можна представити у вигляді дробуm/n, де m – ціле число і n – натуральне число.

Множина Q раціональних чисел – нескінченна множина, до якої належать усі числа, які можна записати у вигляді відношення цілого числа до натурального числа.

Зверніть увагу! Будь-яке раціональне число можна представити у вигляді або скінченого десяткового дробу, або нескінченного періодичного десяткового дробу.

Ірраціональними називаються числа, які не можна представити у вигляді дробу m/n, де m – ціле число і n – натуральні числа.

Зверніть увагу! Будь-яке ірраціональне число можна представити у вигляді нескінченного неперіодичного десяткового дробу.

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

Дійсними є числа раціональні та ірраціональні. Множина R дійсних чисел – нескінченна множина, до якої належать усі раціональні та ірраціональні числа.

 Поняття множини. Операції над множинами

Поняття множини належить до первісних понять математики, якому не дається означення Множину можна уявити собі як су­купність деяких предметів, об'єднаних за довільною характерис­тичною ознакою

 Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному колосі, множина букв українського алфавіту, множина точок на прямій

Предмети, з яких складається множина, називаються її елементами і позначаються малими буквами латинського алфавіту. Наприклад, а = 5 - елемент множини цифр десяткової нумерації Для позначення множин використовують великі букви латинсь­кого алфавіту або фігурні дужки, всередині яких записуються елементи множини При цьому порядок запису елементів не має значення Наприклад, множину цифр десяткової нумерації мож­на позначити буквою М (чи будь-якою великою буквою латин­ського алфавіту) або записати так {1, 3, 5, 2, 4, 6, 8, 7, 9, 0}

Належність предмета даній множині позначається символом , а неналежність - символом (інколи ) Наприклад, число 7 А, де А - множина чисел першого десятка, а число 12 A.

Множини бувають скінченні і нескінченні. У скінченній множині міститься певна кількість елементів, тобто кількість елементів скінченної множини виражається натуральним чис­лом Наприклад, множина М цифр десяткової нумерації скінчен­на і містить десять елементів. У нескінченній множині - нескін­ченна кількість елементів. Наприклад, множина натуральних чисел, множина точок прямої - нескінченні множини.

Множина, в якій немає жодного елемента, називається порож­ньою і позначається символом . Наприклад, множина точок перетину двох паралельних прямих - порожня множина

Якщо множина В складається з деяких елементів даної мно­жини А (і тільки з них), то множина В називається підмножиною множини А. У такому разі співвідношення між множинами А і В позначається так В А (читається "В міститься в А" або "В — підмножина А"). Якщо В може й дорівнювати А, то вживається символ В А. Знак називається знаком нестрогого включення, а знак - знаком строгого включення.

Порожня множина є підмножиною будь-якої множини, тобто А.

Саму множину А можна розглядати як підмножину А, тобто А А.

Множину задають двома основними способами:

1) переліченням всіх її елементів;

2) описанням характеристичної властивості її елементів. Наприклад: а) В = {o,,¡} - множина, задана переліченням елементів; б) X - множина коренів квадратного рівняння х2 = 25. Множина X задана характеристичною властивістю елементів - бути коренем рівняння х2 = 25". Цю саму множину можна зада­ти і переліченням її елементів: X = {-5; 5}.

Дві множини називаються рівними, якщо вони складаються з тих самих елементів. Наприклад, множини коренів рівняння х2 = 25 і |x| = 5 рівні між собою. Справді, X = {-5; 5} і Y = {-5; 5}, де Y - множина розв'язків рівняння |x|-5. Отже, X = Y.

Над множинами виконуються певні операції (дії). Зазначимо три з них.

Переріз множин. 

Перерізом множин А і В називається множина С, яка складається з усіх тих і тільки тих елемен­тів, які належать коленій з даних множин А і В.

Приклад 1. Нехай А - множина всіх дільників числа 32, тобто А = {І, 2, 4, 8, 16, 32), а В - множина всіх дільників чис­ла 24, тобто В = {1, 2, 3, 4, 6, 8, 12, 24}. Тоді перерізом множин А і В є множина С = {1, 2, 4, 8}, яка складається зі спільних дільників чисел 32 і 24.

Схематично переріз множин А і В можна зобразити за допо­могою фігур. Символічно позначається так: С = А В і читається: "С є перерізом А і В".

Приклад 2. Нехай М - множина прямокутників, N - множина ромбів, тоді Р = МN - множина квадратів.

Об'єднання множин. 

Об'єднанням (або сумою) двох мно­жин А і В називається така множина С, яка складається з усіх елементів множин А і В, і тільки з них.

Позначається це так: С = А +В і читається: "С є об'єднанням А і В".

Якщо множини А і В мають спільні елементи, тобто А +В , то кожний з цих спільних елементів береться в множину С тільки один раз.

Приклад 3. А ={1,2, 3,4}, В = {3, 4, 5, 6}, тоді С = {1,2,3,4,5,6}.

Приклад 4. Q - множина раціональних чисел, І - мно­жина ірраціональних чисел. Тоді множиною R всіх дійсних чисел буде об'єднання множин Q і І, тобто R = Q+ І.

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

Віднімання множин.

Доповнення множини. Різницею двох множин А і В називається така множина С, яка складається з усіх елементів множини А, що не належать множині В.

Позначається це так: С = А \ В і читається: "С є різницею А і В".

Приклад 5. а) А= {5,6, 8, 12}, В= {5, 6}, тобто В А, тоді С = А \ В= {8, 12};

б) А = {5, 6, 8, 12}, В = {8, 12, 1, 2}, тоді С = А\ В = {5, 6};

в) А = {5, 6, 12}, В = {1, 2}, тоді С = А \ В = {5, 6, 12};

г) А= {5, 6}, В= {5,6, 12}, тобто В А, тоді С = А\ В = .

У випадку, коли А В, то різниця С = А \ В називається доповненням множини В відносно множини А і позначаєть­ся С (АВ).

В основі класичної комбінаторики лежать правило суми та правило добутку.

Правило суми і правило добутку

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

Спочатку розглянемо правило суми:

якщо деякий елемент А можна вибрати m способами, а елемент В — r способами (причому будь-який вибір елемента А відрізняється від вибору елемента В), то вибрати А або В можна m +r способами.

Приклад 1. В ящику знаходиться 7 білих і 4 чорних кульки. Тоді вибрати одну кульку: білу або чорну можна 7 + 4 = 11 способами.

Зрозуміло, що правило суми можна розповсюдити на три і більше елементів.

Сформулюємо правило добутку:

якщо деякий елемент А можна вибрати m способами, а після кожного такого вибору інший елемент В можна вибрати (незалежно від вибору елемента А) — r способами, то пару об’єктів А і В можна вибрати mr способами.

Приклад 2. У шкільній їдальні є вибір з 3 перших і 5 других блюд. Тоді обід з першого і другого блюда можна обрати 3 ∙ 5 = 15 способами.

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

Приклад 3. Скільки трицифрових чисел можна скласти з цифр 1; 2; 3; 4; 5, якщо в числі: 1) цифри не повторюються; 2) цифри повторюються.

Розв’язання.

1) Маємо 5 способів для сотень числа (мал. 129). Після того, як місце сотень заповнене (наприклад, цифрою 1), для десятків залишається 4 способи. Міркуючи далі, для одиниць - 3 способи. Отже, маємо: «5 способів, і після кожного з них — 4, і після кожного з них — 3 способи». За правилом добутку маємо 5 ∙ 4 ∙ 3 = 60 чисел.

2) Якщо цифри у числі повторюються, то на кожне з трьох місць є по 5 варіантів заповнення(мал. 130), і тоді всіх чисел буде 5 ∙ 5 ∙ 5 = 125.

Приклад 4. Скільки парних чотирицифрових чисел можна скласти з цифр 6; 7; 8; 9, якщо в числі цифри не повторюються?

Розв’язання. Парне чотирицифрове число можна отримати, якщо останньою цифрою буде 6 або 8. Чисел, у яких остання цифра 6 буде З ∙ 2 ∙ 1 = 6 (мал. 131), чисел, у яких остання цифра 8 буде також 6. За правилом суми всього парних чисел, що задовольняють умові, буде 6 + 6 = 12.



Правило добутку застосовується при розв'язуванні такої класичної задачі:

а)Елемент а можна вибрати т способами. Після кожного такого вибору елемент b можна вибрати к способами. Скількома способами можна здійснити вибір пари елементів (а, b) у вказаному порядку?

б)  Очевидно, що вибір впорядкованої пари (а, b) можна здійснити тк способами. Це твердження складає зміст правила добутку у класичному розумінні.

Зауваження 1. Також тк способами можна вибрати пару (b, а) у зворотньому порядку. Однак для більшості комбіна­торних задач, при розв'язанні яких застосовується правило добутку, порядок вибору елементів пари не має значення. Тому при підрахунку кількості способів вибору пари еле­ментів найчастіше враховується лише один з двох можли­dі їх порядків вибору.

Усна задача. Є 5 видів конвертів без марок та 4 види марок. Скількома способами можна вибрати конверт і мар­ку для листа?