Материал: discrete_mathematics

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

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

Завдання для самостійної роботи

1.Скількома способами можна розподілити k екзаменаційних білетів між n студентами?

2.Скількома способами з 6 інженерів і 14 робітників можна створити бригаду, яка складалася б із 2 інженерів і 5 робітників?

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

(а) була непарною; (б) ділилася на три.

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

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

6.Скількома способами можна посадити за круглий стіл n чоловіків і m жінок так, щоб жодні дві жінки не сиділи поруч?

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

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

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

символи b не стоять поруч.

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

вслові?

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

11.Визначити, скількома способами можна переставити літери наведеного слова так, щоб приголосні йшли за абеткою:

(а) абракадабра; (б) монолог; (в) амальгама.

151