Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 14
Текст из файла (страница 14)
6. Показать, что результат задачи 5 имеет место и для бесковечных множеств. 7. Пусть множество (О, ()" представляет собой последовательность а<, ап аз, ..., а„, ..., где а« и (О, (). Доказать, что !(О, <)' ~) 1<!1. 8. Доказать (построением подходящих биекций и рассуждений по индукции), что если Ап ..., А„— конечные множества, то !А, Х... Х А„! - !А, ! °... ° 1А„!. $4. Некоторые специальные классы функций В атом параграфе мы несколько отойдем от основной темы обсуждения для того, чтобы кратко рассмотреть следующие четыре важных класса функций: подстаповки, последовательности, функционалы н отображения, сохраняющие аквпвалентность.
Эти функции часто используются; особо отметим их прплоя'епня к теории графов, к трассировке вычислений, к определению языков программирования н переводу, к машинной графике. Определение. Подстановкой множества А называется бвекция на А. У Подсталовкп конечных множеств представляют особый интерес в вычислениях. )(огда А конечно, мы в состоянпн вычислить чксло разлвчяыт подстановок А. Пусть !А! = л ю Х.
Обо<пач«м через „Р„число таких подстаков<яс Эначенсе „Р„легко вычислить. 8(о'кпо рассматрлвать задачу построения бпеьцкн па Л как задачу Р 83 заполнения ящиков, пронумерованных от 1 до л (рис. З.б), объектами аь ..., а„. Порядок, в котором заполняются ящики, несуществен (любой другой порядок можно получить перемешиванием ящиков). Поэтому будем заполнять их слева направо. Первый ящик может быть заполнен и способами, тзк как мы имеем свооодкый выбор из всего множества А. Убирая выбранный «-! и Рва. 3.6 элемент из А, получим множество из л — 1 элементов. Следовательно, второй ящик может быть заполнен п — ! способами, третий ящик — л — 2 способами и т.
д. Продолжая этот процесс, получим, что (и — 1) й ящик может быть заполнен двумя способами, а ягппк с номером и — единствевным оставшимся элементом из А. Следовательно, число различных подстановок пз А равно я «(и — 1) «(и — 2) «... » 2» 2 «1. Это произведение называется 4бакториалом и (обозкачается и!). Следовательно, „Р„= л!. Так как А - Х„, то можно свести наше рассмотрение к Х„. Любая подстановка на г(„должна определять образ каждого элемента в Х, (который, конечно, должен быть единственпым и отличным от других).
Пусть ~р— подстановка ва Х.. Тогда ф можно определить как мпожество из я пар следующим образам: Ф = ((1~ х!)е (2, х2)~ ° ° » (л, хл))э где (хь ..., х«) - Х„. Не обязательно, конечно, должно быть х~ = 1 и т. д. Можно также представлть ~3 следующим образом; ( ! 3 3 ... е ) Пример 4.1. Пусть о — подстановка ка Х». (1 2 3 4 3 В) ~3 3 3 1 4 2/ Тогда о(1) 5, о(3) = 3 и т. д. з 64 Достоинством етого обозначения является простота, с которой могут быть вычислены слоя<ные подстановки.
Предположим, что лу — подстановка на )л(„, определенная выше, а т — другая подстановка иа том же самом множестве. Тогда подстановка т может быть ааписана как совокуппость пар в порядке, определяемом хь хх, ..., х.. Если две последовательности записать одну над другой (первая применяемая подстановка должна быть аапягана первой), то верхиян и нижняя строки дадут результирующую подстановку. П р и м е р 4.2. Пусть о — подстановка па примора 4.1 и (3 2 8 1 4 5)' Можно переписать р в виде (4 5 6 3 1 2)' Поэтому р ° о может быть вычислено следующим образом: о=~ — 'лб б 3 1 4 2)~— Юдинаковые 3 1 2) 4 5 8) 5 6 3 — 4 5 б 2 3 — э(4 5 Следовательно, например, р ° о(2)(=р(о(2))=р(б)) 5 и т.
д. Ф Отсюда следует, что представление обратной (конечной) подстановки получаетсл перестановкой строк, представляющих исходную подстановку. Хотя такое представление полезно в вычислениях, оно требует ллного лишнего ллеста, особенно в тех случаях, когда многие элементы не меаяются в процессе подстановки. Существует болев простое обозначение, которое может употребляться непосредственно для некоторых простых подстановок и косвенно длн всех конечных. Определение.
Пусть А (аь ..., а„). Подстановку р называют йиклоги (л4иялической подстановкой),если П редположим, что А <и В и В колечко. Расширяя р па все В,можво определить подстановку о так, что р(х), если хеи А, о: х х, если хек В'~А. В этом случае о ведет себя подобво р во всех случаях, когда элемевты В пе остаются ва месте. Применение о к А передвигает элементы по кругу циклическим обра- зом, и, если известна область А, мы можем обозвачить подставовку как (аь аь ..., а„). Эта подставовка вазы- вается циклом длинь< и. Х Пример 4.3, Рассмотрим опять подстановку ~1 2 8 4 8 6) <3 2 6 ! 4 3/' Подстановка является циклом длины 5 и может быть за- писала как (1,3,6,5,4).
в Не все подставовкв являются циклами, Например, подстаиовка о в примере 4.1 ве является циклом, Напомиим, что о выела вид ~3 6 3 1 4 2)' Поэтому о(1) 5, о(5)= 4, о(4) 1, откуда следует, что о содержит цикл (1, 5, 4). Начиная с 2, получаем другой цикл — (2, 6). Таким образом, имеем о (1, 5, 4) ° (2, 6) и о — (2, 6) (1, 5, 4). В депствительвости любая ковечвая подстановка может быть представлена как произведение циклов, при этом циклы могут располагаться в любом порядке. Из построения следует, что одив элемент ве может встретиться более чем в одном цикле, т. е.
циклы не пересекаются. Теорема. Каждая подстановка р на конечном множестве А выражается в виде произведения непересекаю<цихся циклов. Доказательство. Поскольку (А) *певХ, то А - <ч.. Поэтому без потери общвоств мы моя<ем огра- кичиться рассмотрением подстановки р иа 6<„. В теореме утверм<дается, что р = о< ° оз °... ° о„где каждое о; является циклом и циклы ке пересекаются. Для доказательства теоремы построим требуемые циклы.
Сначала найдем каимеиьшпй злсмеит х< <и Х„такой, что 66 р(х~)чь х~ и р(х) = х для всех х, 1 < х < х,. Если такого х~ не существует, то р -1 (т. е. р является тривиальным пустым произведением циклов). В противном случае вычислим хь р(х~), р'(х~), р'(х~) и т. д. Все вти влементы находятся в Х„. Поатому элементы в втой лоследовательности должны содержать повторения. Предположим, что р'(х~) — первый такой влемент (который уже повторялся в лоследовательности). Покажем, что р'(х,) хь Предположим, что вто соотношение не выполняется. Тогда р'(х~) р'(х~) для некоторого 1, О < <1< Й.
Следовательно, рьо(х~) р ' ° р'(х~) р ' ~ р'(х~) р" '(х~) и т. д. Повтому рьл(х~) р' '(х~), т, е. р" '(х~) рс(х~) ° хь что противоречит минвмальности й (так как й — 1< ?с). Таким обрааом, р'(х~) хь и подстановка а~ (хь р(х~), р'(х~), ..., р' '(х~)) надает цикл внутри р. Если все элементы х ю Х„ такие, что р(х)»ь х (будем называть такие элементы несгалиокарлыми), содержатся в Ьь то р о~ — единственный цикл (который, естест« ванно, не пересекается).
В противном случае найдем следующий наименьший элемент хр ш Х„такой, что р(хг)»ь хс я хс не встречается в оь Из хг строим множество различных степеней р: оа (хи р(хе), р~(хр), ..., р (ха)), Это цикл длины не менее 2, н он не пересекается с пп (Доказательство оставляем в качестве упражнения.) Если все нестационарные влементы исчерпаны, то р ° а~ о~ оз ° оь Очевидно, что множество нестациоиарныл элементов, не входящих в вти циклы, можно умень. шить, и в конце концов придем к Я~, Следовательно, р а~ ° аг ° аз °... ° и, для некоторого гю Х.
г" Рассмотрим теперь несколько иную ситуацию. Возьмем множества А: 1А! я и ВшА, ~В! г~п. Возникает вопрос: сколько биектнвныл функций существует пэ А в В? Или, что вквивалентно, сколько существует пнъективныл отображений из В в А? Числа перестановок (бее повторений) из л элементов по г обозначается „Р, и вычисляется так же, как и „Р„, аа исключением того факта, что процесс прекращается после ааполнения г ящнков, Таким обраэом, Р, я ° (я — Ц» „, ° (я г+ 1), Легко видеть, что, продолжая процесс заполнения ящиков, оставшиеся к — г элементов можно разместить по последним п — г ящикам .,Р., способами. Поэтому и ь!~ ьРт „Р„, (л г)! Прн вычислении „Р, мы находки число бнектнвных функций пз А в В.
Подсчвтаем числа таких функций. О п р е д е л е н и е. Пусть А — конечное множество н ВшА, 1А! п*вг !В!. Множество В называется сочетанием (беэ вовторенвй) вз и элементов по г. Число таких сочетаний обозначается через С,". У Вычисление С', производится следующим образом, Положим !А! в. Возьмем произвольное подмножество В ыА такое, что !В~ г. Тогда В является образом подстановки из к элементов по г. Число инъективных функций па А, имеющих В своим образом, есть „Р,. Если г' является такой функцией и л — другая такая функция, имеющая ту же самую область значений, то а связано с г' соотношением а !р ° г', где ~р — подстановка на В. Функции б и ~ определяют одну и ту же комбинаци!о, и в действительности число функций, определяющих зту комбинацию, равно числу подстановок у на В.
Следовательно, откуда «Р. к! С,=— Р г! ! — г)!' Поскольку относительные дополнения единственны и ~А~В! и — г, то отсюда следует, что С', = С" ". Вернемся теперь к математическим объектам, которые должны быть знакомы читателю, но которые, вероятно, не рассматривалвсь как функции. О пр е де лен не.
Послвдоватвлькосгью на множестве Я называют отображение Х - Я. Если с: г! - Я = заданная последовательность к о(п) в„, то обычно обозначают последовательность не с, а (в„) илн (вв зз, ..., в„, ...). В этом случае в„ называют я-м членом последовательности. У Часто при изучении свойств последовательностей возникает понятие «расстояние» между соседними злементами последовательности (скажем, в„и в„+1) и между элементами в„при л > пз (где кс — некоторый фиксированный зчемент Х) и фиксированным элементом из В, 88 Иы вернемся к зтнм вопросам несколько позже, поскольку в настоящяй момент у нас в оощем случае нет понятия расстояния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
