9.4. Сур’єктивні аплікації

Означення. Аплікація f: A(B називається сур’єктивною якщо множина образів співпадає з множиною В.

Замість вживання незрозумілого іноземного слова surjection можна просто говорити про аплікацію В на А. З означення сур’єкції випливає, що для будь якого y ( B рівняння

повинно мати по крайній мірі один розв’язок.

Приклад 1.

Нехай A = R\{-1} і f: A (R визначено як Довести, що f не є сур’єктивна.

Доведення. Припустимо, що y ( R. Для того щоб функція була сур’єктивна, будь який y(R повинен бути образом деякого a (A, тобто, рівняння

повинно мати по крайній мірі один розв’язок для будь якого y ( R. Але при y = 2, як видно з попередньої формули, такого розв’язку не існує, тобто, y = 2 не є образом жодного a (A. Це значить, що область значень функції f не співпадає з R, тому f не є

Приклад 2.

Довести, що f: A ( B визначена як f(х) = I х I , A = R, B = R⁺₀ є сур’єктивною.

Доведення. . Нехай y ( R⁺₀ і розглянемо рівняння y = I х I. Для будь якого невід’ємного y це рівняння має корені х = ( y. Отже, кожен у( R⁰ є образом якогось х і згідно означення f є сур’єктивною.

9.5. Бієктивні аплікації

Як вказує сама назва, аплікація є бієктивна, якщо вона одночасно і ін’єктивна і сур’єктивна. Бієкція по своїй суті є взаємно однозначна відповідність між множинами А і В, на яких вона визначена. Бієкція визначена на скінченій множині А називається перестановкою.

Приклад.

Нехай A = R\{1} e f: A (A визначена як Показати, що f є бієкція.

Доведення.

Ін’єктивність.

Нехай a₁ ( a₂ , a₁(A, a₂ (A.

Сур’єктивність.

Нехай y ( A. Щоб функція була сур’єктивною, довільний y(A повинен бути образом деякого

a (A:

.

Отже, f є бієктивна.

9.6. Композиція аплікацій

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

Приклад.

Нехай функції f: R ( R і g: R ( R визначені як f(x) = 2x + 1 і g(x) = x² – 2. Визначити складні (скомпоновані) функції g(f e f(g.

Розв’язок.

g(f(x) = (2x + 1)² – 2; f(g(x) = 2(x² – 2) + 1.

9.7. Обернена функція

Формально обернена функція визначається так само як і обернене бінарне відношення. Але в той час як обенене бінарне відношення існує завжди, про обернену функцію цього сказати не можна. Складене формально на базі аплікації обернене бінарне відношення може не задовольняти критеріям, згідно яких його також можна назвати аплікацією. Та коли функція f є бієктивною, обернене відношення f ^-1 теж є функція. Отже,

функція f ^-1: B ( A обернена до f: A ( B існує лише у випадку коли f є бієктивна.

Тільки в цьому випадку для кожного y ( B можемо знайти єдиний образ x в A. Очевидно. що

f ^-1 ( f = f ( f ^-1 = I_A.

Те ж саме можна записати як

.

Приклад.

Нехай A = R\{2} і f є функція з областю визначення A задана формулою . Показати, що f бієктивна на A в деяку область B ( R. Знайти множину B і обернену функцію f^-1. Перевірити результат тотожністю f ^-1 (f = f( f^-1 = I_A.

Ін’єктивність. Розглянемо рівняння Його розв’язок, як можна перевірити, є єдинийдля будь якого y ( 3. Отже, функція є ін’єктивною.

Сур’єктивність. Розв’зок попереднього рівняння показує, що єдиним елементом R, який не є образом жодного елемента A є y = 3. Отже, функція f : A ( B буде сур’єктивною якщо B = R\{3} і

.

Перевірка результату тотожністю:

.

Образ

Нехай f: A ( B e X ( A. Тоді, образ X відповідний функції f є множина f(X) визначена як

.

Якщо Y ( B, тоді образ Y відповідний функції f ^-1 є множина f ^-1(Y) визначена як

Приклад.

Нехай f: R⁺₀ (R⁺₀ визначеняа як f(x) = x² e X = {x ( R⁺₀ : 0 ( x < 2}. Тоді,

= {x² : 0 ( x < 2} = [0, 4).

Тепер, нехай Y = {y ( R: 0 ( y < 4} і обчислимо f ^-1(Y). Згідно означенню

= { x ( R⁺₀ : 0 ( x² < 4} = [0, 2).

Вправи на закріплення

Нехай X = {1, 2, 3, 4}. Чи є наступні бінарні відношення функціями X ( X.

R₁ = {(2, 3), (1, 4), (2, 1), (3, 2), (4, 4)};

R₂ = {(3, 1), (4, 2), (1, 1)};

R₃ = {(2, 1), (3, 4), (1, 4), (2, 1), (4, 4)}.

Нехай X = {1, 2, 3}, Y = {4, 5, 6}. Чи є наступні бінарні відношення функціями X ( У.

R₁ = {(1, 5), (2, 4), (3, 5)};

R₂ = {(1, 5), (2, 4), (1, 6)};

Нехай X ={1, 2, 3}, Y ={4}. Чи є R = {(1, 4), (2, 4), (3, 4)} функція X ( У.

Нехай X = {1}, Y ={2, 3, 4}. Чи є R = {(1, 4), (1, 2), (1, 3)} функція X ( У.

Нехай A = {1, 2, 3} і B = P(A), а F: B ( B функція визначена за формулою

F(X) = A \ X.

Чому дорівнює F({1, 3})? Якого типу є ця функція?

Нехай C є множина всіх міст світу, а P множина всіх країн світу і

R = {(c, p) ( (C P): місто c знаходиться в країні р}.

Чи є R функцією C ( P?

Нехай G множина всіх людей і

R = {(p, f) (G G): p є батько або мати f}.

Чи є R функцією G ( G?

Нехай I_A = {(a, a): a ( A} є тотожне відношення на A. Чи є I_A функція A ( A?

Нехай R = {(x, y) ( R R: y = x² }. Чи є R функція R ( R?

10. Які з функцій визначених наступними графами є ін’єктивні, сур’єктивні, бієктивні?

f X Y	g X Y
h X Y	s X Y

11. Нехай функції f: A ( B і g: B ( C бієктивні. Перевірити чи функція g ( f: A ( C є бієктивна.

12. Нехай A = [-1, 1], g: A ( A і h: A ( A визначені як f(x) = sen x, g(x) = sen (x,

h(x) = sen((/2)x. Чи кожна з цих функцій є:

a) ін’єктивна;

b) сур’єктивна;

c) бієктивна

13. Нехай f: A ( B. Чи кожна з наступних функцій є:

a) ін’єктивна;

b) сур’єктивна;

c) бієктивна

f(a) = na, n ( N	a) A = N, B = Z, n ( N,
b) A = B = N; d).	c) A = R, B = R, e).
f) A = R^+, B = R, f(a) = ( a;

g) A є множина непустих підмножин B = {1, 2, 3, 4}. f(a) є найменше з чисел множини a.

Нехай f: R ( R визначена як Довести, що f є бієктивна і знайти формулу для f^-1.

15. Нехай f: R⁺ ( R⁺ визначена як f(x) = x² . Знайти:

a) f({1, 2, 4});

b) f({1, 2});

c) f^-1({4, 9});

d) ) f^-1({1, 4});

e) f^-1(f ({1, 2});

16. Нехай f: X ( Y . Довести, що для будь яких A ( X, B ( X :

a) f(A(B) = f(A) ( f(B) ;	b) f(A ( B) ( f(A) ( f(B);
c) f(A\ B) = f(A) \ f(B) ;	d) A ( B ( f(A) ( f(B) ;
e) f^-1(A(B) = f^-1(A) ( f^-1(B) ;	f) f^-1(A ( B) ( f^-1(A) ( f^-1(B);
g) f^-1(A\ B) = f^-1(A) \ f^-1(B) ;	h) A ( B ( f^-1(A) ( f^-1(B) ;

Відповідь.

R₁ не є функція, тому що дві різні пари (2, 3) e (2, 1) мають один і той же аргумент;

R₂ не є функція, тому що елемент 2 ( X не має образу;

R₃ є функція, пара (2, 1) повторена два рази, є один і той же елемент множини

2. R₁ є функція, R₂ – не є. 3. Є. 4. Не є. 5. {2}. 6. Є. 7. Не є. 8. Є. 9. Є.

10. g і f sao injectivas, h e s sao sobrejectivas, s e bijectiva.

11. Seja a₁ ( a₂ , a₁(A, a₂ (A, entao b₁ = f(a₁ ) ( b₂ = f(a₂ ).

Por mesma razao c₁ = f(b₁ ) ( c₂ = f(b₂ ), entгo g(f : A (C й injectiva. Por outro lado, se g й sobrejectiva, para qualquer que seja c ( C existe b ( B tal que c = g(b). Porque f tambйm й sobrejectiva, existe a (A tal que b = f(a). Entгo, para qualquer que seja c( C existe a (A tal que c = g(f(a). Isto significa que g(f й sobrejectiva.

13. a) bijectiva; b) nгo injectiva, nгo sobrejectiva; c) injectiva, mas nгo sobrejectiva; d) bijectiva; e) injectiva, mas nгo sobrejectiva; f) nгo injectiva, mas sobrejectiva; g) nгo injectiva, mas sobrejectiva.

14. .

15. a) {1, 4, 16}; b) {1, 4}; c) {2, 3}; d) {1, 2}; e) {1, 2}.

16. a) Seja y (f(A(B), entгo existe x (A(B tal que f(x) = y. Se x( A, entгo

y (f(A) e , por consequкncia, y (f(A)(f(B). . Se x( B, entгo y (f(B) e , por

consequкncia, y (f(A) ( f(B). Logo, f(A(B) ( f(A) (f(B).

b) Seja y (f(A), entгo existe x (A tal que f(x) = y. Mas neste caso x ( A(B e,

por consequкncia, y (f(A(B). Ao mesmo resultado chegamos supondo x (B.

Entгo, f(A) (f(B) ( f(A(B). Daqui resulta f(A(B) = f(A) (f(B).

O mesmo esquema de prova aplica-se para as restantes relaзхes.

12. Melhor й investigar aqui a natureza das funзхes a partir dos seus grбficos:

f(x) = sen x y 1 -1 O 1 -1 Injectiva Sobrejectiva Bijectiva

g(x) = sen (x y 1 -1 O 1 -1 Nao injectiva Sobrejectiva Nao bijectiva

h(x) = sen((/2)x y 1 -1 O 1 -1 a) Injectiva b) Sobrejectiva c) Bijectiva

Текст 4.

Елементи комбінаторики

Постановка задачі

Для того щоб викладена далі матерія була зрозумілішою, почнемо з наочного прикладу. Маємо n голубів (курей, кролів і т. і) і m ящиків (n ( m – жодного голуба без ящика, причому, не виключається можливість помістити в один ящик всі n голубів!) . Скількома способами можна розмістити голубів по ящиках. Цей приклад став таким популярним, що в англійській літературі дістав назву pigeon principle і жоден автор підручника по дискретній математиці не обминає його.

Змоделюємо математично цю проблему. Розглянемо функцію

F: X ( Y, де X = {1, 2, … , n}, Y = {1, 2, … , m}.

Множина значень функції буде

F = {F(1), F(2), … , F(n)}, 1 ( F(i) ( m

Розміщення

Тепер залишимо голубів і поставимо проблему таким чином: скільки функцій F існує? Число таких функцій природно назвати числом розміщень і позначити як U(m, n). Не забувайте, що n це число голубів, а m – число ящиків. Легко пересвідчитися, що

U(m, n) = mⁿ

Дійсно, кожен з n голубів може бути поміщений в один з m ящиків. Іншими словами, існує m способів посадити в ящик першого голуба. Комбінуючи кожен з цих способів з таким же числом m способів помістити другого голуба в ящик, одержимо m(m = m² . Продовжуючи цей процес до останнього n-го голуба, одержимо вказану вище формулу.

Доведення стане зрозумілішим, якщо проілюструємо його прикладом двох голубів і трьох ящиків. Перший елемент це голуб, а другий елемент – ящик.

F₁ = {(1,1), (2,1) } – обидва голуби в першому ящику;

F₂ = {(1,1), (2,2) }

F₃ = {(1,1), (2,3) }

F₄ = {(1,2), (2,1) }

F₅ = {(1,2), (2,2) } – обидва голуби в другому ящику (1)

F₆ = {(1,2), (2,3) }

F₇ = {(1,3), (2,1) }

F₈ = {(1,3), (2,2) }

F₉ = {(1,3), (2,3) } – обидва голуби в третьому ящику

Таким чином, U(3, 2) = 3² = 9.

Замість того, щоб виписувати повністю всі можливі функції, можна перечислити зайняті голубами ящики

Голуби	Ящики
1		1	1	1	2	2	2	3	3		3
2		1	2	3	1	2	3	1	2		3

Якщо порівняємо цю таблицю з функціями, то помітимо, що в стовпцях знаходяться значення кожної з шести функцій. Подібним же способом моделюється кидання двох гральних кубиків (лото, нарди і т. п.). Уявимо собі 6 ящичків, на кришці кожного з яких написані цифри від 1 до 6. І два гральні кубики. Якщо на них появляються різні числа очок, поміщаємо їх у ящики з відповідними номерами. Якщо однакове число очок, то поміщаємо обидва у відповідний ящик. Отже, сказати, що на кожному кубику може випасти 6 різних чисел, це все рівно що сказати “кожен з двох голубів може бути поміщений в один з шести ящиків”. Після цього вже легко прийти до висновку, що число розміщень

U(6, 2) = 6² = 36.

Всі можливі випадки:

Розміщення без повторень

А тепер введемо обмеження – кожному голубу власний ящик. З математичної точки зору кожне таке розміщення без повторень буде ін’єктивною функцією (згадаємо означення ін’єктивної функції – різним значенням х відповідають різні значення функції). Число розміщень без повторення обчислюється за формулою

A(m, n) = m(m – 1)(m – 2)…(m – n + 1)

Дійсно, першого голуба можна помістити в будь який з m ящиків; другого голуба можна помістити в будь який з решти m – 1 ящиків. Це дасть уже m(m – 1) спосіб розмістити двох голубів. Продовжуючи цей процес дійдемо до n-го голуба, його можна помістити в один з решти m – (n – 1) ящик, що й приводить до вище наведеної формули. В разі двох голубів і трьох ящиків відповідні ін’єктивні функції одержимо з (1) відкинувши випадки розміщення двох голубів в одному ящику

F₂ = {(1,1), (2,2) }

F₃ = {(1,1), (2,3) }

F₄ = {(1,2), (2,1) } (2)

F₆ = {(1,2), (2,3) }

F₇ = {(1,3), (2,1) }

F₈ = {(1,3), (2,2) }

Як бачимо, таких функцій буде 6 = 3 ( 2 .

Простенький приклад на розміщення без повторень. З групи 30 студентів треба вибрати старосту і організаторів спортивних змагань та культурного відпочинку. Скількома способами це можна зробити? Якщо зрозуміло, що кожний спосіб це розміщення без повторень, то можна зразу ж скористатися формулою

A(30, 3) = 30(30-1)(30-2) = 30(29(28

Якщо ж це важко збагнути, то слід розмірковувати наступним чином. На місце старости можна поставити будь кого з 30 студентів, значить існує 30 способів вибрати старосту. Кожен з них комбінується з 29 способами вибору спорт організатора. Це дасть 30(29 способів заповнити дві перші посади. Кожен з них комбінується з 28 способами заповнити третю посаду. Знову ж таки, без ніякої формули приходимо до того ж результату 30(29(28.

Перестановки

Функція F: X ( Х називається перестановкою. Формулу числа перестановок з n елементів легко одержати з формули розміщень без повторень взявши m = n.

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

Комбінації

Строго монотонна функція F: X ( Y називається комбінацією. Нагадаємо, що функція називається монотонно зростаючою, якщо більшому значенню аргументу відповідає більше значення функції. Цій вимозі в (1) задовольняють всього три функції

F₂ = {(1,1), (2,2) }

F₃ = {(1,1), (2,3) }

F₆ = {(1,2), (2,3) },

або, виписуючи тільки пари значень функцій 1 1, 1 3, 2 3. Якраз з такими комбінаціями ми звикли мати справу. В такій формі втрачається зв’язок комбінацій з функціями, часто на практиці це й не потрібно. Але в більш складних випадках нам не обійтися від трактування комбінацій як монотонних функцій на дискретній множині.

Число комбінацій обчислюється по формулі

Справедливість цієї формули випливає з наступного. Серед всіх розміщень, що містять одні й ті ж самі n елементів, а їх буде рівно n!, буде всього одна комбінація, тому що лише одним способом їх можна розмістити в монотонну послідовність. Тепер зрозуміло, що число комбінацій C(m, n) дорівнює числу розміщень A(m, n) поділеному на n! = P(n).

Nota. Формули для числа розміщень без повторень і числа комбінацій можна модифікувати наступним чином.

Комбінації з повтореннями

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

З функцій (1) таким умовам відповідають

F₁ = {(1,1), (2,1) }

F₂ = {(1,1), (2,2) }

F₃ = {(1,1), (2,3) }

F₅ = {(1,2), (2,2) }

F₆ = {(1,2), (2,3) }

F₉ = {(1,3), (2,3) }

До трьох звичайних комбінацій 1 2, 1 3, 2 3 додаються ще три 1 1 , 2 2, 3 3. Звідси й походить термін комбінації з повтореннями. Позначимо в загальному випадку число комбінацій з повтореннями V(m, n) і без доведення приймемо формулу

V(m, n) = C(m + n – 1, n).

Доведення передбачає ретельний аналіз співвідношення між монотонними і строго монотонними функціями і ми вважаємо зайвим втрачати на це час. Обмежимося перевіркою справедливості цієї формули у нашому випадку m = 3, n = 2.

Формула Стірлінга

Функція n! є дуже швидко зростаючою, швидше за експоненту. В цьому легко впевнитися використовуючи формулу Стірлінга для оцінки факторіалу

або більш точно

Підстановки

Підстановка і перестановка це одне й те саме – бієктивна функція F: X ( X. Термін підстановка вживається у випадку представлення F у вигляді таблиці, перша строчка якої є значення аргументу, а друга – відповідні значення функції. Наприклад,

В такій формі легко знаходити суперпозицію функцій, наприклад

Тотожна підстановка – це підстановка І, в якій І(х) = х, у нашому прикладі

Обернена підстановка F^-1 існує, так як підстановка є функція бієктивна і знаходиться як у випадку довільного бінарного відношення. Наприклад,

Якщо домовитись завжди значення аргументу писати в порядку зростання, то першу строчку таблиці можна опускати і, таким чином, матимемо звичайну перестановку.

Цикл

Циклом називається послідовність елементів х₀, х₁,..., х_к така, що

Цикл довжиною 2 називається транспозицією. Представлення підстановки у вигляді графа добре ілюструє поняття циклу і транспозиції. Проілюструємо перше підстановкою F_1.

1 5

3

2 4

Ця підстановка містить один цикл довжини 3 і два цикли довжиною 1 ().

Завдання на розуміння. Придумайте підстановку з транспозицією і зобразіть її за допомогою графу.

Інверсії

Якщо в перестановці для елементівмає місце нерівність

при , то параназивається інверсією.

Теорема. Довільну підстановку можна представити у вигляді суперпозиції транспозицій сусідніх елементів.

Доведення.

Нехай . Переставимо 1 на першу позицію міняючи її крок за кроком місцями з сусідніми елементами зліва. Позначимо послідовність таких транспозицій t_1. При цьому всі інверсії, що містять 1 пропадуть. Потім переставимо 2 на друге місце і т. д. Таким чином,

Наслідок. Всяке сортування може бути виконане перестановкою сусідніх елементів.

Метод сортування, що базується на доведеній теоремі, називається методом бульбашки. Це не самий ефективний алгоритм сортування, але його варто розглянути для кращого розуміння алгоритмів взагалі.

Input: A: array[1..n] of B (B – тип елементів масиву, елементи розташовані довільно)

For i = 1 to n – 1

m = i (індекс кандидата в мінімальні елементи)

For j = i + 1 to n

If A(j) < A(m) then m = j (новий кандидат в мінімальні)

Next j

Next i(

A(i) ( A(m) (ставимо мінімальний елемент на місце)

Output: A: array[1..n] of B (елементи розташовані в порядку зростання)

Генерація перестановок

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

Аналогічно, говорять, що перестановка анти лексикографічно передує перестановці якщо

Приклад перестановок в лексикографічному порядку.

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

Приклад перестановок в анти лексикографічному порядку

(1, 2, 3), (2, 1, 3), (1, 3, 2), (3, 1, 2), (2, 3, 1), (3, 2, 1)

Так як не будь які дві перестановки можна порівняти, то встановлений таким чином порядок являється частковим.

Алгоритм генерації перестановок.

Input. n – число елементів

For i = 1 to n

P(i) = i - ініціалізація першої (тотожної) перестановки

Next i

Antilex(n) – виклик рекурсивної процедури

Остання процедура і виконує основну роботу. Наводимо її алгоритм.

Input: m – параметр процедури, рівний кількості перших елементів масиву P для якого генеруються перестановки

If m = 1 then P {чергова перестановка сформована}

Else

Antilex(m – 1) {рекурсивний виклик}

If i < m then

P(i) ( P(m) {перестановка місцями і – го і m – го елементів }

Якщо перестановки треба сформувати в анти лексикографічному порядку, то треба додати процедуру Reverse заміни порядку елементів масиву.

Input: к – номер елемента, що задає відрізок масиву Р, який треба переставити в зворотному порядку.

j = 1 (нижня границя відрізка)

While j < k

P(j) ( P(k)

j = j + 1

k = k – 1

Wend

Output: перші к елементів масиву Р в зворотному порядку

Output: Послідовність перестановок в анти лексикографічному порядку

Генерація всіх підмножин даної множини

Input: n ( 0 – число елементів множини

Output: послідовність кодів підмножин і

For i = 1 to 2ⁿ – 1

i

Next i

Недоліком цього коду є відсутність порядку в послідовності елементів множини

Алгоритм Грея побудови бінарного коду

В цьому алгоритмі підмножини появляються одна з одної заміною одного елементу.

Input: n ( 0 – число елементів множини

Output: послідовність кодів підмножин В