Позначимо через A, B, C множини студентів, які знають англійську, французьку та німецьку мову. Тоді кількість студентів, які знають принаймні одну мову, згідно з (3.1) становить
| A B C | = | A | + | B | + | C | –
–(| A ∩ B | + | A ∩ C | + | B ∩ C |) + | A ∩ B ∩ C | =
=61 + 43 + 26 – (25 + 17 + 14) + 8 = 92.
Отже, шукана кількість дорівнює 100 – 92 = 8.
2. Знайти кількість натуральних чисел, що не перевищують 1000 і не діляться ні на 3, ні на 5, ні на 7.
Позначимо через Ak множину натуральних чисел, що не перевищують 1000 і діляться на k. Множиною натуральних чисел, що не перевищують 1000 і діляться або на 3, або на 5, або на 7, є множина
A3 A5 A7,
а шуканою множиною є
E \ (A3 A5 A7),
де множина-універсум E – всі натуральні числа від1 до 1000. Тоді
| E \ (A3 A5 A7) | = | E | – | E ∩ (A3 A5 A7) | =
= | E | – | A3 A5 A7 |
(див. співвідношення (2.3)).
| E | = 1000, а вираз | A3 A5 A7 | обчислюють за (3.1). Крім того, | Ak | = [1000/k] і Ak ∩ Al = Am, де m – найменше спільне кратне чисел k і l (через [x/y] позначено цілу частину від ділення x на y). ◄ Нарешті, розглянемо останню теоретико-множинну операцію –
прямий добуток. Якщо A1, A2, …, An – скінченні множини, то |
(3.2) |
|A1 A2 … An| = |A1| |A2| … |An|. |
Формулу (3.2) часто називають основним правилом комбіна торики (або правилом множення).
Нехай потрібно виконати одну за одною n дій. Якщо першу дію можна виконати k1 способами, другу – k2 способами і т. д., а n-ту – kn способами, то всі n дій разом можна виконати k1k2…kn способами.
Приклад 3.2.
1. Кількість слів довжиною m в алфавіті A (|A| = n) становить |Am| = |A|m = nm. Цей результат випливає також із того, що побудову одного зі слів довжиною m можна розкласти на m кроків (або дій): перший крок – вибір першої літери слова, другий –
141
вибір другої літери слова і т. д., m-й – вибір останньої літери. Кожну з цих дій можна виконати n способами.
2. З'ясуємо, скількома способами можна розподілити k різних предметів серед n осіб.
Нехай A – множина осіб, серед яких розподіляють предмети. Кожному варіанту розподілу поставимо у відповідність кортеж (ai1, ai2, …, aik), де aij – особа, яка одержала j-й предмет. Установ-
лена відповідність взаємно однозначна, отже, множина варіантів розподілу містить таку саму кількість елементів, що й множина всіх кортежів довжиною k, утворених з елементів множини A. Тому шукане число становить |Ak| = |A|k = nk.
3. Нехай A та B – скінченні множини, |A| = n, |B| = m. Обчислимо кількість усіх можливих відображень множини A в множину B. Кожне відображення ϕ: A → B можна повністю задати його табл. 3.1, де a1, a2, …, an – елементи множини A, а ϕ(a1), ϕ(a2), …, ϕ(an) – відповідні образи. Кожен з образів можна обрати m способами.
a1 |
|
… |
an – 1 |
an |
Таблиця 3.1 |
ϕ(a1) |
ϕ(a2) |
… |
ϕ(an – 1) |
ϕ(an) |
|
Отже, існує mn способів утворення рядка значень для відо-
браження ϕ у табл. 3.1, тому кількість відображень типу A → B становить |BA| = mn = |B||A|.
4.Скількома способами можна розмістити на шахівниці 8 тур так, щоб вони не били одна одну?
8! Є вісім способів розташувати першу туру на першій вертикалі шахівниці, сім способів розташувати другу туру на другій вертикалі і т.д., один спосіб розташувати восьму туру на останній вертикалі.
5.Скільки існує n-значних десяткових чисел,
(а) усі цифри яких парні; (б) у запису яких є принаймні одна парна цифра;
(в) у запису яких немає цифри 7; (г) у запису яких обов'язково є цифра 5?
(а) 4 5n – 1. Першу цифру такого числа можна обрати чотирма способами (2, 4, 6 або 8), а кожну наступну – п'ятьма.
142
(б) 9 10n – 1 – 5n. Від кількості всіх n-значних десяткових чисел
слід відняти кількість n-значних чисел, усі цифри яких непарні. (в) 8 9n – 1.
(г) 9 10n – 1 – 8 9n – 1 (див. (б) і (в)).
6. Визначити, скільки різних натуральних дільників має число:
(а) 21001 32015 72002; (б) 40042124.
(а) Довільний дільник даного числа має вигляд 2n 3m 7k, де n може набувати значення в діапазоні від 0 до 1001 (тобто є 1002 варіанти обрати n), m – від 0 до 2015, а k – від 0 до 2002. Отже, шукана кількість дільників дорівнює 1002 2016 2003.
(б) Слід розкласти число 4004 на прості множники й застосувати міркування, наведені в попередньому пункті.
7. Нехай множина A містить n елементів, а множина B – m елементів. Визначити кількість:
(а) відповідностей; (б) усюди визначених відповідностей; (в) функціональних відповідностей між множинами A та B. (а) Оскільки відповідність C між A та B – це довільна підмножина декартового добутку A B, то кількість таких відповідностей дорівнює кількості елементів булеана множини A B, яка містить nm елементів. Це число дорівнює 2nm, оскільки для будь-якої підмножини M A B і для довільного елемента a A B (nm варіантів вибору) можливі лише дві ситуації: або елемент a належить множині M, або елемент a не належить
множині M.
(б) Будь-яка відповідність C між A та B однозначно задається множиною образів C(a), a A. Для всюди визначеної відповідності C кожна з цих множин (що є підмножиною множини B) має бути непорожньою. Кількість непорожніх підмножин множини B дорівнює 2m – 1. За правилом множення кількість усюди визначених відповідностей дорівнюватиме (2m – 1)n.
(в) Множиною образів f(a) функціональної відповідності f між A та B для кожного a A може бути або деяка одноелементна підмножина множини B, або порожня множина. Отже, є m + 1 варіант обрати образ для кожного з n елементів множини A, тому кількість функціональних відповідностей дорівнює (m + 1)n.
8. Нехай множина M містить n елементів. Визначити кількість: (а) відношень; (б) рефлексивних відношень;
143
(в) нерефлексивних відношень; (г) антирефлексивних відношень; (д) симетричних відношень; (е) антисиметричних відношень;
(є) рефлексивних і антисиметричних відношень;
(ж) рефлексивних і несиметричних відношень на множині M.
Нехай m = n2, k = n2 – n, l = k/2.
(а) 2m. Кількість відношень на множині M дорівнює кількості елементів булеана множини M × M, яка містить m = n2 елементів.
(б) 2k. Будь-яке рефлексивне відношення R на множині M можна подати у вигляді R = iM R′, де R′ – множина недіагональних елементів із M × M. Кількість варіантів обрати R′ дорівнює кількості елементів булеана множини (M × M) \ iM, що містить k = n2 – n елементів.
(в) Ця кількість дорівнює різниці кількостей усіх відношень і
рефлексивних відношень на M, тобто 2m – 2k. (г) 2k (див. (б)).
(д) Будь-яке симетричне відношення на M однозначно задається вибором довільної підмножини діагоналі iM та довільної підмножини з елементів, розташованих над (або під) діагоналлю. Кількість елементів, з яких здійснюється вибір, становить n + l = n(n + 1)/2, тому кількість симетричних відношень
2n + l = 2n(n + 1)/2.
(е) Для того щоб утворити антисиметричне відношення R, слід узяти довільну підмножину діагоналі iM (2n способів) і додати до неї деяку множину недіагональних елементів, ураховуючи те, що з пари (a, b) і (b, a) симетричних недіагональних елементів до R може входити або лише один із цих елементів, або жоден (3l способів, оскільки кількість таких пар дорівнює l). Отже, існує 2n 3l = 2n 3n(n – 1)/2 антисиметричних відношень на множині M.
(є) 3n(n – 1)/2 (див. попередній пункт).
(ж) Нехай Р – множина рефлексивних відношень, а С – множина симетричних відношень на множині M. Тоді множина рефлексивних і несиметричних відношень на множині M – це
Р \ С. | Р \ С| = | P | – | Р ∩ С| = 2k – 2l (див. п. (б) і (д)). ◄
144
Завдання для самостійної роботи
1. Нехай M – скінченна множина і A, B M. Розташуйте у порядку неспадання такі величини:
(а) | B |, | A B |, | |, | A ∩ B |, | M |;
(б) | A\B |, | A | + | B |, | A B |, | |, | A B |.
2. Довести нерівності:
(а) | A B | ≤ | A | + | B |; |
(б) | A\B | ≤ | A |; |
(в) | A B | ≤ | A | + | B |; |
(г) | A\B | ≥ | A | – | B |; |
(д) | A B | ≤ | A B |; |
(е) | A | < | β(A) |; |
(є) | A ∩ B | ≤ | A |; |
(ж) | A ∩ B | ≤ | A B |. |
3.Нехай A – скінченна множина, a – елемент, а B – підмножина множини A. Яких підмножин множини A більше:
(а) тих, що містять елемент a, чи тих, що немістять елемента a; (б) тих, що містять множину B, чи тих, що не перетинаються
із множиною B;
(в) тих, що включають множину B, чи тих, що не включають множину B?
4.У групі 27 студентів. Із них 16 відвідують семінар А, 12 – семінар Б, а 7 студентів не відвідують жодного семінару.
(а) Скільки студентів відвідують семінари А та Б? (б) Скільки студентів відвідують лише семінар А?
5.Обстеження читацьких смаків студентів показало, що 60 % студентів читають журнал А, 50 % – журнал Б, 50 % – журнал В, 30 % – журнали А та Б, 20 % – журнали Б і В, 40 % – журнали А та В, 10 % – журнали А, Б і В. Скільки відсотків студентів:
(а) читають принаймні один журнал; (б) не читають жодного з журналів; (в) читають точно два журнали; (г) читають не менше двох журналів?
6.Знайти кількість і суму чотиризначних натуральних чисел, що не діляться на жодне з таких чисел:
(а) 2, 5, 11; (б) 6, 10, 18.
7.Знайти кількість простих чисел, що не перевищують 120.
8.Під час екзаменаційної сесії з чотирьох іспитів не менше 70 % студентів склали іспит з дискретної математики, не менше 75 % – з математичного аналізу, не менше 80 % – з алгебри й не
145