Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки (1127096), страница 3
Текст из файла (страница 3)
Следовательно, тут каждый элемент х ен 1(~ имеет бесконечно много про. образов. 5. Пусть 5 — множество трехзначных простых чисел, а Ь вЂ” множество цифр. Отображение ф: В - Ь определим так: поставим в соответствие каждому трехзначному простому числу его вторую цифру. Например: (179)ф = 7, (821)ф = 2, (907)ф = О. Непосредственной проверкой убеждаемся, что ф — сюръскция, т.
е. для каждой цифры найдется трехзначное простое число, в котором эта цифра стоит посередине. Тут множества В и Ь конечны, и для каждого элемента из Ь существует лишь конечное число элементов из 5, которые на него отображаются, в Если множества А и В конечны и ф: А-+ — сюръекция, то в нижнем ряду ее таблицы встречаются все элементы из В.
На каждой горизонтальной прямой графика сюръекцин сбязательно есть обозначенные вершины сетки. На стрелочной схеме сюръекции в каждую точку, которая обозначает элемент множества В, входит по меньшей мере одна стрелка. Сюръекция конечного множества А на множество В существует не всегда. Очевйдно, для этого необходимо, чтобы множество В также было конечно и выполнялось неравенство ( А ('=--) В (. 2. Взаимно однозначное отображение. Отображение ф: А-эВ называется взаимно однозначным или инъекцией, если разные элементы множества А переводятся этим отображением в разные элементы множества В: для каждых х„х, си А из х,чих, вытекает (х,)фчь(х,)ф.
4 Примеры. 6. Отображение ф множества целых чисел Х в множество всех четных чисел 2Х определим так: положим г(ф)=6г для каждого геиХ. Это отображение — инъекция, так как из г,Фг, вытекает 6е,чибисе. 7. Пусть А — множество всевозможных двухэлементных подмножеств множества действительных чисел В,  — мно. жество приведенных квадратных уравнений. Каждому элементу (а, Ь) множества А поставим в соответствие уравнение из В, для которого числа а, Ь являются кор- 13 нами. Каи вытекает из теоремы Виета, такое отображение будет инъективным.
> В нижнем ряду таблицы инъективного отображения ~р: А — В в отличие от таблиц произвольных отображений, каждый элемент множества В встречается лишь один раз. Следовательно, на каждой горизонтальной прямой графика инъекции обозначено не более одной вершины сетки, а при стрелочном изображении инъекции в каждую точку, которой обозначается элемент множества В, входит не более чем одна стрелка. Если множества А и В конечны и существует инъекция множества А в множество В, то, очевидно, должно выполняться неравенство ) А ! ==. ~ В ~.
3. Взаимно однозначное отображение на все множество. Если отображение !р множества А в множество В является одновременно инъективным и сюръектнвным, то оно называется взаимно однозначным отображением множества А на множество В или биекцией А на В. 4 Примеры. 8. Пусть А = В=П вЂ” множество точек плоскости.
Тогда биекцией является каждое из следующих известных из шкзльного курса геометрии отображений множества Л на себя: симметрия относительно фиксированной точки, симметрия относительно фиксированной прямой, параллельный перенос, поворот вокруг фиксированной точки, гомотетия.
9. Отображение !Г: х-+.2х, где хе-=Х, есть, очевидно, биекция множества Х на множество 2Х четных чисел. !ь Если существует бнекция' конечного множества А на конечное множество В, то должны выполняться неравенства (А ~)~ В( н ~ А(.~)В!. Следовательно, для конечных множеств А и В биекция А на В существует тогда и только тогда, когда выполняется равенство ~А ~ =~ В ~. Подсчитаем, сколько существует разных биекций множества А = ~аъ а„..., а ! на множество В = !Ьп Ьм..., Ь ~.
Каждая биекция <р: А — ~В полностью описывается, своей таблицей: а, ь, Верхний ряд таблицы не меняется, а в нижнем ряду могут стоять произвольно размещенные обозначения эле- !4 ментов множества В, причем обязательно разных. Следовательно, первое (например, слева) место нижнего ряда таблицы можно заполнить и разными способами. Если первое место уже заполнено, то независимо от того, каким элементом оно заполнено, на второе место можно поставить обозначение какого угодно нз тех элементов множе.
ства В, которые остались. Аналогично третью клетку, независимо от того, какие элементы поставлены в первые две клетки, можно заполнить и — 2 способами и т. д. Для предпоследнего места остаются лишь две возможности его заполнения, а для последнего — только одна. Г!оскольку каждая клетка заполняется независимо от остальных, существует п(п — 1) (п — 2)...2 1=а! разных способов одновременного заполнения клеток.
Следовательно, можно составйть п! разных таких таблиц, т. е. существует и! разных биекций А на В. Очень часто приходится рассматривать отображения некоторого множества М в себя. Такие отображения называются еще преобразованпялш множества М.
Читателю хорошо известны, например, разные типы геометрических преобразований, которые уже упомвнались в примере 8. Для преобразований произвольного множества также можно рассмотреть введенные выше классы отображений: инъекции, бнекции и сюръекции.
Но для конечных множеств, как легко понять, эти три класса преобразований совпадают, т. е, каждая инъекция конечного множества в себя будет также и сюръекцией, а каждая сюръекция есть одновременно и инъекция. А поэтому для конечных множеств выделяется лишь класс биективных преобразований. Изучая преобразования произвольного конечного множества, удобно придерживаться определенных стандартных обозначений.
Природа элементов множества М при изучении его преобразований несущественна. Следовательно, мы можем занумеровать все элементы множества М и оперировать не с самими элементами, а с их номерамн. Поэтому, рассматривая преобразования конечных множеств, мы будем впредь иметь в виду множество М = (1, 2, 3, ..., п) первых и натуральных чисел. Задавая преобразования таблицами, будем записывать их в таком упрощенном виде: (а, а, а« ... ал) Ясно, 'что такое обозначение однозначно характеризует преобразование и не вызывает недоразумений. Например, если М =11, 2, 3, 4, 5), то а) (2 2 4 2 3) ' б) (3 2 1 3 4) ' ) (б 4 3 2 1) есть таблицы разных преобразований на множестве М, Читать такую таблицу, например а), следует так: «Преобразование «р, заданное таблицей а), 1 переводит в 2, 2 переводит в 2, 3 переводит в 4, 4 переводит в 2, 5 переводит в 5м Порядок записи элементов верхнего ряда такой таблицы не существен.
Например, преобразование, заданное таблицей б), можно обозначить также таблицами: (2 3 1 3 4)' (4 3 3 2 1)' (3 1 2 4 3)' Поскольку каждое преобразование конечного множества полностью описывается своей таблицей, мы часто будем обозначать одинаковыми символами само преобразование и его таблицу. Некоторые преобразования множества М имеют специальные названия. а) Тождественное преобразование.
Толедественное преобразование — это преобразование е„которое все элементы из М оставляет на месте, т. е. (а)в=а для каждого а ен М. Если М вЂ” конечное множество, это преобразование будет иметь таблицу (1 2 3 ... и — 1 п)' б) Постоянное преобразование, Преобразование называется постоянным, если оно каждому элементу из М ставит в соответствие некоторый фиксированный элемент этого множества.
Если М вЂ” конечное множество, 16 постоянное преобразование характеризуется таблицей вида (1 2 3 ... и — 1 и) где аеи М. в) Перестан.овки. Перестановкой будем называть биекцию конечного множества на себя. Следовательно, ф есть перестановка на М тогда и только тогда, когда для произвольных элементов а, Ь ~ М, аФ.Ь, имеем (а)ф Ф (Ь)ф. А это означает, что перестановка определяется таблицей вида ( 2 3 ...
а — 1 и ~ аг аа аа " ап-з, ав/' где аы а„..., а„— разные элементы из М. Упражнения 1. Построить графики и стрелочные схемы для отображений мно., жества (1, 2, 3, 4, 5) в множество (а, Ь, с, г/), заданных такнмн таблицами: ) (а Ь с Ь а) ' ) (с а а с а) ' ) (а Ь а Ь с) 2. Пусть А и В нонечные множества, причем (А ~=ш, 1В1=п. Скальпа существует разных инъекций множества А в множество В? 3. Пользуясь решением предыдущего упражнения, найти, сколько существует ' ш-элементных подмножеств множества из л элементов.
4. Будет лн сюръекцией отображение ф: В- В нз множества В слов русского языка в множество й букв русского алфавита, кото- рое каждому слову ставит в соответствие его первую букву? 6. Какие свойства отличают графики и стрелочные схемы бнек- ций от графиков и стрелочных схем произвольных отображений? 6.
Сколькнмн способами можно расположить и одноцветных ладей на шахматной доске с л' клетками так, чтобы викакие две из ннх не били друг друга? 7. Сколько существует разных перестановок на множестве М= = (1, 2, 3, 4, 5), которые ни один элемент из М не оставляют на месте (т, е, для таких перестановок ф имеем а (ф) Ф а для каждого а еэ М)? 8. Сколькими спосчбами можно расположить на шахматной доске 8 одноцветных ладей так, чтобы никакая из них не стояла на белой диагонали и никакие две не били друг друга? 9.
Сколько можно составить разных шестизначных чисел из цифр О, 1,2„3,4,7,9? 10. Сколько существует разных перестановок ф на множестве (1, 2, 3, ..., и), для которых (1)ф — (2)ф» 1? 11. Доказать, что при п»4 существует перестановка ф множе- ства М=(1, 2, ..., и), для которой при любых и /еэ М выполняется условие ~ (1)ф — 1(ф) ~=!1-! ~ 12. Доказать, что при п»4 существует размещение п одноцвет- ных ферзей на шахматной доске с пз клетками, при котором никакие 2 ферзя не бьют друг друга, 17 13. Сколькими способами можно разместить 3 одноцветных ферзей на шахматной доске так, чтобы никакие 2 нз ннх не били друг друга? й 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
