Материал: discrete_mathematics

вибір другої літери слова і т. д., 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 способами.

Отже, існує 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. Довести нерівності:

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

менше 85 % – з програмування. Яка мінімальна кількість студентів, що склали одночасно всі чотири іспити?

9.Номер автомашини складається із трьох літер українського алфавіту (що містить 33 літери) і чотирьох цифр. Скільки можна скласти різних номерів автомашин?

10.Скількома способами можна розмістити на шахівниці

розміром m n дві різнокольорові тури так, щоб вони не били одна одну?

11.Скільки існує n-значних десяткових чисел, (а) які починаються із двох однакових цифр; (б) у яких сусідні цифри різні; (в) усі цифри яких непарні;

(г) у запису яких є принаймні одна непарна цифра; (д) у запису яких немає цифри 9; (е) у запису яких обов'язково є цифра 3?

12.Скількома способами в множині A з n елементів можна вибрати дві підмножини, що не перетинаються?

13.Визначити, скільки різних натуральних дільників має число: (а) 32015 52016 112017; (б) 24482124; (в) 31244004; (г) 92162331.

14.На одній прямій дано n точок, а на іншій, паралельній першій, – m точок. Скільки існує трикутників, вершинами яких є ці точки?

15.Нехай множина A містить n елементів, а множина B – m елементів. Визначити кількість:

(а) сюр'єктивних відповідностей; (б) ін'єктивних відповідностей; (в) бієктивних відповідностей

між множинами A та B.

16.Нехай множина M міститьn елементів. Визначити кількість: (а) неантирефлексивних відношень; (б) несиметричних відношень; (в) неантисиметричних відношень;

(г) рефлексивних і симетричних відношень; (д) рефлексивних і антисиметричних відношень; (е) антирефлексивних і симетричних відношень;

(є) антирефлексивних і несиметричних відношень; (ж) антирефлексивних і антисиметричних відношень на множині M.

146