Тема 2. Визначники та їх властивості

§ 2.1. Види відображень множин

Поняття множини є одним з головних математичних понять. Коли говорять про множину мають на увазі набір, сукупність або зібрання деяких об’єктів, які мають загальні відмінні характерні ознаки. Наприклад: множина студентів групи, множина дійсних чисел, множина неперервних функцій, тощо. Об’єкти, з яких складається множина, називають елементами множини. Домовимось позначати різні множини великими латинськими літерами А, В, С…, а їх елементи a, b, с … – маленькими.

Означення 2.1.1. Розглянемо дві множини А та В. Будемо казати, що задане відображення за правилом  з множини А у множину В, якщо кожному елементу множини А відповідає деякий елемент з множини В.

Для позначення відображення  з множини А у множину В будемо використовувати символи: , або . Множину А називають початком відображення, а множину В кінцем відображення.

Означення 2.1.2. Нехай а – довільний елемент множини А ( ). Відповідний йому елемент b з множини В будемо називати образом елемента а при відображенні  та позначати . Нехай b – деякий елемент множини В, тоді будь-який елемент а з множини А, для якого b є образом, називається прообразом елемента b та позначається .

Приклад. Визначити образ елемента множини та прообрази елементів а та b з множини , якщо відображення задане таким чином:

Рис 2.1. Відображення

Розв’язання. За означеннями образу та прообразу виходить, що образом елементу є елемент : . А прообрази елементу а – це елементи 1 та 2 з множини А: . Елемент b не має прообразу: .

При відображенні множини А у множину В кожний елемент початку відображення А має точно один образ. Але не у кожного елементу кінця відображення В є прообраз. Може також мати місце випадок, коли деякі елементи кінця відображення мають декілька прообразів. Ті елементи кінця відображення, які мають прообрази, утворюють множину, яка називається образом відображення та позначається символом .

Означення 2.1.3. Відображення будемо називати вкладенням (або ін’єктивним відображенням), якщо кожний елемент кінця відображення – множини В має не більш ніж один прообраз.

Означення 2.1.4. Якщо кожний елемент множини В має хоч один прообраз (тобто один або більше одного), то відображення називається накладенням (або сюр’єктивним відображенням).

Зрозуміло, що у цьому випадку .

Означення 2.1.5. Відображення , яке є одночасно вкладенням та накладенням, називається взаємно-однозначним (бієктивним або бієкцією).

В цьому випадку кожному елементу множини А відповідає лише один елемент множини В та навпаки. Розглянемо приклади ін’єктивного, сюр’єктивного та бієктивного відображень:

Рис 2.2. Ін’єктивне відображення (але не сюр’єктивне)

Рис 2.3. Сюр’єктивне відображення (але не ін’єктивне)

Рис 2.4. Бієктивне відображення

§ 2.2. Підстановки

Означення 2.2.1. Будь-яке взаємно-однозначне відображення  множини перших n натуральних чисел на себе, називається підстановкою n-го степеня. Підстановку записують так:

, (2.1)

де : – одне з чисел , крім того , якщо , тобто всі числа – різні.

Якщо в таблиці (2.1), яка визначає підстановку, переставити декілька стовпчиків, то, очевидно, одержимо новий запис вихідної підстановки, оскільки з нової таблиці як і раніш виходить, що число 1 переходить у число , число 2 – у і т. д. У зв’язку з цим, на подальшому будемо завжди вважати, що числа у першому рядку підстановки (2.1) завжди розташовані у порядку зростання від 1 до n.

Приклад. Чи є підстановкою відображення

?

Розв’язання. Це відображення – не ін’єктивне, оскільки . Воно також не є сюр’єктивним, тому що . Висновок: зазначене відображення – не є підстановкою, оскільки воно не є бієкцією.

Теорема 2.2.1. Число усіх підстановок n-го степеня дорівнює .

 Розглянемо довільну підстановку n-го степеня

,

де : – одне з чисел (нагадаємо, що усі числа другого рядку різні). За можна обрати будь-яке з чисел . Це дає n різних варіантів. Якщо ми вже обрали, то за можна обрати лише одне з натуральних чисел, що залишилися. Внаслідок цього число різних способів вибору чисел та , очевидно, дорівнює добутку , а число способів вибору чисел , , , очевидно, дорівнює . Таким чином, число способів вибору чисел ,  , …,  дорівнює .

Розглянемо поняття перестановки.

Означення 2.2.2. Перестановкою будемо називати n-вимірний рядок , в якому : – приймають значення з множини та усі різні.

Відзначимо, що на підставі теореми 2.2.1 число усіх різних перестановок з n натуральних чисел дорівнює n!.

Означення 2.2.3 Кажуть, що числа та утворюють в перестановці інверсію, якщо , а (тобто та розташовано попереду в перестановці).

Приклад. Визначити число інверсій у перестановці .

Розв’язання. Число 4 утворює 3 інверсії з числами 1, 2, 3, які менші за нього, а розташовані після нього. Кожне з чисел 3 та 5 утворює по 2 інверсії з числами 1, 2 з аналогічних міркувань. Інші числа інверсій не утворюють. Таким чином, загальна кількість інверсій у зазначеній перестановці дорівнює 3+2+2=7.

Означення 2.2.4. Перестановку називають парною, якщо загальне число інверсій у перестановці – парне, у супротивному випадку перестановку називають непарною.

Означення 2.2.5. Якщо, в перестановці змінили місцями два числа, то кажуть, що здійснили транспозицію цих чисел.

Теорема 2.2.2. Парність перестановки змінюється після одної транспозиції двох її чисел.

 Розглянемо спочатку випадок, коли числа i та k, транспозиція яких була здійснена, розташовані поряд у вихідній перестановці: . Де А – група чисел, які попередні до числа i, а В – група чисел, що розташовані після числа k. Після транспозиції чисел i та k одержимо нову перестановку: . Очевидно, що загальне число інверсій, що утворюють числа i та k з числами множин А та В, у новій та вихідній перестановках однакові. Якщо у вихідній перестановці , то у новій перестановці загальна кількість інверсій зменшується на одиницю. Якщо ж у вихідній перестановці , то у новій перестановці число інверсій збільшується на одиницю. Таким чином, після транспозиції двох сусідніх чисел у перестановці, загальна кількість інверсій змінюється на одиницю, тобто парність перестановки змінюється.

Нехай тепер числа i та k у перестановці не є сусідніми, тоді перестановка має вигляд . Послідовно змінюючи місцями число i та числа , отримаємо перестановку . Відзначимо, що під час переходу до нової перестановки було здійснено m транспозицій сусідніх чисел.

Для того, щоб поставити число k поперед числа , потрібно зробити транспозицій числа k з сусідніми числами . Внаслідок цього від вихідної перестановки до перестановки можна перейти за допомогою транспозицій сусідніх чисел. Згідно з доведеним вище після однієї транспозиції парність перестановки змінюється. Звідки виходить, що після транспозицій двох сусідніх чисел парність перестановки також змінюється. 

Означення 2.2.6. Підстановка n-го степеня називається парною, якщо сума інверсій у її верхньому та нижньому рядках є число парне, у супротивному випадку підстановка називається непарною.

Приклад. Визначити парна або непарна підстановка

?

Розв’язання. Число інверсій у першому рядку підстановки дорівнює нулю. Число інверсій у другому рядку дорівнює . Таким чином сума інверсій у двох рядках підстановки дорівнює . Висновок: зазначена підстановка – непарна.

На закінчення параграфу відзначимо, що парність підстановки не змінюється під час транспозиції двох будь-яких її стовпчиків.