Різниця множин

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

Різниця множин А і В позначається так: А\В. За допомогою діаграми Ейлера можна зобразити різницю множин А і В (рис. 126).

Розглянемо приклади.

а) Якщо А = { a, b, c, d }, В = { а, с, m, n, p }, то А\В = { b, d }, В\А = { m, п, р }.

б) Якщо А — множина студентів вашого групи, В — множина дівчаток групи, С — множина хлопчиків групи, то А\В = С, А\С = В. У випадку, якщо В — частина множини А (В А), то А\B називається доповненням до В у множині А і позначають С_AВ.

Представникам різних професій доводиться розв'язувати задачі, в яких з деякої множини об'єктів потрібно вибирати елементи, що мають ті або інші властивості, розміщувати ці елементи в певному порядку. Так керівнику цеху потрібно розподілити кілька видів робіт між працівниками, агроному — розмістити посіви сільськогосподарських культур на кількох полях, хіміку — розглянути можливі зв'язки між атомами і молекулами тощо. Оскільки в таких задачах йде мова про комбінування об'єктів, їх називають комбінаторними задачами, а розділ математики, в якому вивчаються питання про те, скільки різних комбінацій, що відповідають тим чи іншим умовам можна скласти із заданих об'єктів, називається комбінаторикою.

В наш час комбінаторні задачі приходиться розв'язувати фізикам, хімікам, біологам, економістам, спеціалістам самих різних професій.

Коли ми говорили про множину, то порядок розміщення елементів в множині не враховувався. Нерідко розглядають і впорядковані множини.

Будь-яка впорядкована множина, яка складається з n елементів, називається перестановкою з n елементів і позначається Р _n.

Таким чином, перестановки з n елементів відрізняються між собою лише порядком елементів.

Два елементи а і b можна упорядкувати двома способами: ab і bа. Це дві перестановки з елементів a і b. Отже, Р₂ = 2.

Щоб утворити перестановки з трьох елементів а, b, с можна третій елемент с помістити попереду пари ab, посередині пари аb та вкінці пари ab:

cab, acb, abc.

Точно так із пари bа можна одержати:

cba, bca, bac.

Отже, для трьох елементів існує 2 · 3 = 6 способів розташування по порядку, число перестановок з трьох елементів дорівнює 6. P₃ = 2 · 3 = 6.

Нехай маємо k елементів, із яких складені всі можливі Р_k перестановки. Візьмемо одну із них: а₁а₂а₃...а_k. Добавимо ще один (k + 1)-й елемент. Його можна помістити:

1) перед першим елементом а ₁;

2) перед другим елементом а₂;

3) перед третім елементом a ₃;

……………………………………

k) перед k -им елементом а _k;

(k + 1) в кінці всіх елементів, тобто, всього k + 1 способом.

Отже, кількість перестановок із k + 1 елементів в (k + 1) раз більша, ніж число перестановок із k елементів, тобто,

.

Отже,

P₁ ⁼ 1;

P₂ = P₁ · 2 = 1 · 2 = 2;

P₃ = P₂ · 3 = 1 · 2 · 3 = 6;

P₄ = Рз · 4 = 1 · 2 · 3 · 4 = 24;

P₅ = P₄ · 5 = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120;

………………………………

P_k = P_k-1 · k = 1-2· 3 · ... · k;

P_k+1 = P_k · (k+ 1 ) = 1 · 2 · 3 ·...· k · (k +l).

Добуток натуральних чисел від 1 до даного натурального числа η називається факторіалом числа n і позначається n! В таблиці 14 наведено значення факторіала для значень п від 1 до 10.

Число перестановок з n елементів дорівнює добутку всіх натуральних чисел від 1 до п, тобто п! (читають: єн факторіалів).

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

P₆ = 6! =l · 2 · 3 · 4 · 5 · 6 = 720.

Будь-яка впорядкована підмножина з т елементів даної множини, яка містить n елементів, де т n називається розміщенням з n елементів по т елементів.

Число розміщень з n елементів по т позначають символом .

Розглянемо множину {а, Ь, с} і випишемо розміщення з елементів даної множини по два: ab, bа, ас, са, be, cb. Отже, = 6.

Знайдемо значення .

Нехай маємо множину, яка містить n елементів. Перший елемент m -елементної підмножини можна вибрати n способами; другий елемент —(n - 1) способами; третій елемент — (n - 2) способами;... m -ий елемент — (п - т + 1) способами.

Отже,

= n · (n – 1) ·(n –2)· ... ·(n - m +1),

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

Якщо п = т, то маємо = Р _n тобто перестановка — окремий випадок розміщення

Нехай дано множину {а, b, с}. З елементів цієї множини можна утворити 6 двохелементних розміщень. ab, ас, bс, bа, са, сb.

Це впорядковані підмножини даної множини. А скільки не-впорядкованих двохелементних підмножин можна скласти з тих самих елементів? Тільки три: {ab}, {ас}, {be}.

Будь-яка підмножина з т елементів даної множини, яка містить n елементів, називається комбінацією з n елементів по т елементів.

Число комбінацій з n елементів по т позначають символом . Наприклад: = 3.

З чотирьох елементів множини {a, b, c, d} можна утворити 6 комбінацій по 2 елементи: {а, b }, { а, с }, { а, d }, {b, с }, { с, а }, { b. d }; 3 комбінації по 3 елементи: { а, b, с }, { а, b, d }, { b, с, d }.

Таким чином, = 6, = 3.

Домовилися вважати, що

= 1, =n, = 1.

Виведемо формулу для знаходження значень , для цього порівняємо числа і при одних і тих же значеннях т і п.

Кожну m -елементну комбінацію можна впорядкувати Р _m способами. У результаті з однієї комбінації утворюється розміщень (упорядкованих підмножин) з тих самих елементів. Отже, число m -елементних комбінацій у Р_m разів менше за число розміщень з тих самих елементів. Тобто = • , звідси

Число комбінацій з n елементів по т дорівнює дробу, чисельник якого е добуток т послідовних натуральних чисел, найбільше з яких n, а знаменник дробу — добуток т послідовних натуральних чисел.

Враховуючи, що можна одержати . Отже,

Приклад. Обчислити a) ; б) .

a) ; б)

Задача. Скількома способами з 25 студентів можна вибрати 3 чергових.