Материал: discrete_mathematics

менше 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

3.2. Сполуки, перестановки та розміщення

Позначимо через Bk(M) множину всіх k-елементних підмножин даної скінченної множини M, а через C(n, k) – кількість елементів множини Bk(M), де n = | M | і 0 ≤ k ≤ n. Зокрема, B0(M) складається лише з одного елемента – порожньої множини , B1(M) складається з n елементів – одноелементних підмножин множини M, а Bn(M) містить лише один елемент – саму множи-

ну M. Отже, C(n, 0) = C(n, n) = 1 і C(n, 1) = n.

Кількість усіх k-елементних підмножин множини M, яка складається з n елементів, становить

Довільну k-елементну підмножину n-елементної множини називають сполукою (або комбінацією) з n елементів за k. Фор-

мула (3.3) дає змогу обчислити кількість таких сполук.

Для кількості сполук з n по k крім уведеного позначення C(n, k) використовують також позначення Ckn , nCk, (n, k) або kn .

Приклад 3.3. Підрахуємо, скількома способами можна заповнити картку Лото (6 із 49). Очевидно, їхня кількість дорівнює кількості сполук із 49 елементів (чисел) по 6, тобто

Нехай множина M містить n елементів.

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

Послідовно утворюватимемо кортежі довжиною n з елементів множини M (| M | = n). Є n можливостей для вибору першої координати кортежу. Після того, як обрано елемент для першої координати, залишиться n – 1 елемент, з яких можна вибрати другу координату кортежу і т. д. За основним правилом комбінаторики всі n дій разом можна виконати

n(n – 1)(n – 2)…2 1 = n!

147

способами. Отже, є n! кортежів довжиною n, утворених з елементів множини M, і Pn = n!

Приклад 3.4.

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

Існує P5 = 5! перестановок зазначених цифр. Однак частина з цих перестановок матиме на першому місці цифру 0, тобто відповідатиме чотиризначним числам. Кількість чисел вигляду 0abcd, де (a, b, c, d) – перестановка з цифр 1, 2, 3, 4, становить P4 = 4! Отже, шуканим числом є P5 – P4 = 5! – 4! = 96.

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

C(50, 3) + 50C(50, 2). Сума трьох чисел парна, якщо або всі вони парні (кількість таких трійок C(50, 3)), або два з них непарні (таких пар C(50, 2)) і одне парне (що обирається із 50 можливих).

3.Скільки є перестановок цифр 0, 1, 2, …, 9, у яких цифра 3 займає третє місце, а цифра 5 – п'яте?

8! Зафіксуємо в кожній перестановці цифру 3 на третьому місці, а цифру 5 – на п'ятому. На всіх інших восьми позиціях розташуємо всіма можливими способами решту вісім цифр.

4.Скількома способами можна розташувати n нулів і k одиниць так, щоб жодні дві одиниці не стояли поруч?

C(n + 1, k). Запишемо спочатку всі n нулів. Існує n + 1 місце (одне – перед першим нулем, n – 1 – між нулями й одне – після останнього нуля), на які можна записувати по одній одиниці, щоб вони не стояли поруч. Отже, для кожного заданого розташування слід обрати k місць з n + 1 можливих. ◄

Кортеж довжиною k, утворений з елементів множини M (|M| = n), у якому елементи не повторюються, називають розмі

щенням з n по k (0 ≤ k ≤ n). Різні розміщення з n по k відрізняються або складом елементів, або їхнім порядком.

Кількість розміщень із n по k позначають A(n, k) або Ank .

Кількість усіх k-елементних підмножин множини M з n елементів дорівнює C(n, k). Із кожної з цих підмножин можна утворити стільки кортежів, скільки існує різних перестановок її еле-

148

ментів. За попередньою теоремою їхня кількість дорівнює k! Отже, загальна кількість кортежів довжиною k, які можна побудувати з n елементів, дорівнює k!C(n, k).

n!

A(n, k) = k!C(n, k) = (n − k)! ,

тобто A(n, k) = n(n – 1)(n – 2)…(n – k + 1).

Приклад 3.5. Визначити, скільки тризначних чисел можна утворити з цифр 0, 1, 2, 3, 4 за умови, що цифри кожного числа різні.

Існує A(5, 3) кортежів довжиною 3, координати яких обрано із зазначених цифр. Виключимо із них кортежі, перша координата яких дорівнює 0. Таких кортежів – A(4, 2). Отже, шукане число дорівнює A(5, 3) – A(4, 2) = 5 4 3 – 4 3 = 48. ◄

Нехай задано множину M, що складається з n елементів, і такі цілі числа

k1, k2, …, km, що k1 + k2 + … + km = n і ki ≥ 0, i = 1, 2, …, m.

Скільки існує розбиттів {A1, A2, …, Am} множини M (див. п. 2.7) таких, що | Ai | = ki, i = 1, 2, …, m? Позначимо шукане число че-

рез Cn(k1, k2, …, km).

Усі зазначені розбиття множини M на m класів можна дістати таким чином: візьмемо довільну k1-елементну підмножину множини M (це можна зробити C(n, k1) способами); серед n – k1 елементів, що залишилися, візьмемо k2-елементну підмножину (це можна зробити C(n – k1, k2) способами) і т. д. Загальна кількість способів вибору різних множин A1, A2, …, Am за правилом множення становить

C(n,k1) C(n – k1,k2) C(n – k1 – k2,k3)…C(n–k1– k2 – … – km – 1, km) =

Кількість різних перестановок, які можна утворити з n елементів, серед яких є k1 елементів першого типу, k2 елементів другого типу і т. д., km елементів m-го типу, дорівнює

Cn(k1, k2, …, km).

Візьмемо перестановку W – довільну із зазначених перестановок – і замінимо в ній усі k1 однакових елементів першого типу різними елементами. Тоді, виконуючи k1! перестановок нововведених елементів, одержимо k1! відповідних перестановок з n елементів. Потім замінимо в перестановці W усі k2 елементів другого типу різними елементами. Переставляючи ці елементи, одержимо k2! відповідних перестановок і т. д. Отже, за допомогою описаної процедури з кожної перестановки W можна утворити k1!k2! … km! різних перестановок довжиною n. Зробивши так для всіх зазначених перестановок, дістанемо всі n! можливих перестановок з n елементів. Якщо позначимо шукану кількість через L, то з наведених міркувань одержимо

L · k1!k2! … km! = n!

n!

Отже, L = k1!k2!... km! , тобто L = Cn(k1, k2, …, km).

Приклад 3.6.

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

Маємо 10 елементів – м, а, т, е, м, а, т, и, к, а, серед яких є два елементи м (першого типу), три елементи а (другого типу), два елементи т (третього типу) та по одному елементу інших типів – е, и та к. За доведеною теоремою з цих елементів можна утворити

10!

C10(2, 3, 2, 1, 1, 1) = 2!3!2!1!1!1! = 151200

перестановок (або слів).

2. Нехай дано n символів a, m символів b і k символів c. Визначити кількість різних слів,

(а) які можна скласти зі всіх цих символів; (б) які складаються зі всіх цих символів і у яких жодні два

символи c не стоять поруч. (а) (n + m + k)!/(n!m!k!).

(б) Розглянемо довільне слово w, утворене зі всіх символів a та b. Кількість таких слів (n + m)!/(n!m!), а довжина кожного з

150