I Морозова В.Д. Введение в анализ (1081368), страница 14
Текст из файла (страница 14)
(2.4) В случае й = и каждое упорядоченное подмножество заданного множества называют перестпановкой из и элеменв' 84 2. ОТОБРАЖЕНИЕ МНОЖЕСТВ. ФУНКЦИИ Р„=1 2" ( - ц = ы = П (2.5) тиж1 Тогда вместо (2.4) можно написать и'. (и — Й)! (2,6) причем (2.6) переходит при я = Й в (2.5), если условно считать, что О! =1.
Каждое подмножество множества из е элементов, содержащее Й элементов, называют сочетпанием из и элементов по Й элементов. Если в каждом сочетании выполнить всевозможные перестановки его элементов (число таких перестановок по Й элементов Рк — — Ы), то получим размещения из я элементов по й. Поэтому А~ =С~Р~, где С~ — число всех сочетаний из и элементов по Й (обозначение по первой букве французского слова сотЪ1пав1оп или английского слова сотЪ1паф1оп — сочетание). Отсюда А~ п~ Р~ И(я — й).' (2.7) Из (2.7) следует, что С„" = С" " и ~с++1 = С~~+ С~'+1. Первое из этих равенств очевидно, так как каждому сочетанию из тов. Число всех таких перестановок обозначают Р„по первой букве французского (и английского) слова реппийай1оп— перестановка.
Ясно, что каждая из перестановок исходного множества упорядочена своим отношением порядка. Поскольку перестановка элементов конечного множестпеа является частным случаем (при Й = и) размещения его элементов, согласно (2.4) число возможных перестановок из и элементов есть произведение всех матрральных чисел от 1 до и включительно, обозначаемое я! (произносят „эн факториал"). Таким образом, 2.6. Упорадоченные множества. Элементы комбинаторики 85 1 элементов конечного множества, содержащему Й элементов, соответствует сочетание, содержащее и — 1с остальных элементов этого множества.
Второе равенство можно истолковать так. Зафиксируем некоторый из и+1 элементов, из которых составляются сочетания по 1+1 элементов. Тогдалюбое сочетание, в которое входит этот элемент, соответствует некоторому сочетанию из оставшихся я элементов по й элементов. Поэтому число всевозможных сочетаний, в которые вошел этот элемент, равно С~~. Сочетания, в которые не входит зафиксированный элемент, образуют всевозможные сочетания по 1+ 1 элементов из оставшихся в элементов. Так как зафиксированный элемент либо входит в сочетание, либо не входит, то общее число сочетаний С„++' получается как сумма всевозможных сочетаний, содержащих этот элемент и не содержащих его. Числа С„" составляют таблицу, называемую тпреуаомькиюом Паскалев, симметричную относительно вертикали, проходящей через его вершину. 1 1 1 2 1 1 3 3 1 1 4 6 4 1 На й-м месте в любой и-й строке таблицы стоит значение С~, причем крайние числа отвечают значениям Со =С„" = 1.
Начиная с третьей строки любой внутренний элемент таблицы Равен сумме двух ближайших к нему элементов предшествующей строки. 2. ОТОБРАЖЕНИЕ МНОЖЕСТВ. ФУНКЦИИ Пример 2.8. Поставим в соответствие каждому элементу числового множества (а1, ар, ..., а;, ..., а„) двучлены (иначе биномы) вида 1+а;х, ~ = 1, а (~ принимает последовательно все значения из множества Я натуральных чисел от 1 до я включительно) и перемножим их: (1+ а1х)(1+ азх) "° (1+ а;х) ° ° ° (1+ а„х) = = 1+Ь1х+Ь2х +...+Ь~х~+...
+Ь„х". Любой из коэффициентов Ь|, 1=1, я при й-й степени числа х есть сумма произведений по Й элементов из и элементов заданного множества, причем в эту сумму входит С~ слагаемых. В случае а1 — — аз —— ...— — а; = ...=а„=1 имеем Ь~ =С„ и (1+х)~ = 1+С1 +С2 2+...+С~х~+...+С~ л. (2.8) Это выражение называют биномом Ниотона, в котором числа С„" являются биномиальными коэффициентами. Используя символ суммы ~; и принятое выше соглашение, что О'.
= 1, вместо (2.8) можем написать и (1+ х1" ='ЯС„'х'. Й=О Пример 2.9. Рассмотрим конечное множество из 2т элементов. Из них, согласно (2.4) и (2.7), можно составить А~~ — — 2т(2т — 1) упорядоченных пар и з (21В)~ 2! (2т — 2)! пар, для которых порядок расположения элементов несуществен (например, С~~ — это число встреч 2т участников спортивного соревнования, проводимого по круговой системе), 87 2.7. Ограниченные множества Найдем число В2 способов, которыми 2т элементов можно разбить на пары.
С участием любого элемента пару можно образовать 2т — 1 способами. Каждый раз после образования одной пары останется 2т — 2 элементов, которые можно разбить на пары В2 2 способами, т.е. В2тп — (2т — 1) В2т 2 ° Такого рода соотношение называют рекуррентпным.
В данном случае оно позволяет последовательно выразить В2 через -число способов разбиения на пары 2т — 2, 2т — 4, ... элементов, пока не останутся лишь 2 элемента, которые образуют пару единственным способом (В2 — — 1). Таким образом, В2 — — (2т — 1)В2 2 = (2т — 1)(2т — 3)В2 4 — ...— =(2т — 1)(2т — 3)" В2 — — (2т — 1)(2т — 3)" 3 1. Произведение всех натуральных чисел, не превосходящих а и имеющих с и одинаковую четность, обозначают п!'. (произносят: „эн два факториала" или „эн двойной факториал").
С учетом этого обозначения число разбиений на пары 2т элементов В2 — (2т — 1) Н. 2.7. Ограниченные множества Определение 2.4. Подмножество А упорядоченного множества Е называют оараниченным сверху, если существует по крайней мере один элемент из Е, следующий за всеми элементами из А. Каждый элемент 6 б Е, ограничивающий подмножество А С Е сверху, называют мажоронтой для А (или верхней ераннцей А). Подмножество А С Е имеет наибольшее значение, если существует мажоранта 6, принадлежащая этому подмножеству. 88 2.
ОТОБРАЖЕНИЕ МНОЖЕСТВ. ФУНКЦИИ Аналогично определяют ограниченное снизу подмножество А С Е, минорантву для А (или нижнюю враницу А), наименьшее значение А. Определение 2.б. Подмножество А упорядоченного множества Е, ограниченное сверху и снизу, называют ограннчеккь44$. На числовой прямой множество А С Ж будет ограниченным снизу, если существует такое число х из Ж, что г не больше х для любого х из А, т.е.
=Ь Е Е: ~Ь Е А х ~ (х. Любое число х из Е,обладающее по отношению к множеству А указанным свойством, является нижней границей А. Если А ограничено сверху, т.е. если Зрей: ЧхЕА у~~х, то множество В = (-х: х б А~ ограничено снизу, поскольку из х < у следует -х ~ ~-у, при этом -у будет нижней границей В. Обратно, если А ограничено снизу, то по тем же соображениям В ограничено сверху, и если г — нижняя граница А, то -х — верхняя граница В. Примерами ограниченных подмножеств на числовой прямой служат отрезки, интервалы и пиюуинтпервалы.
Множество не обязательно имеет наибольшее или наименьшее значение. Если же множество имеет, например, наибольшее значение, то это значение единственно. В самом деле, если 61 и бр — два наибольших значения одного множества А, то одновременно 61 >- бр и бг,' 61, откуда по свойству отношения ~ а ь,=ь,. Если множество мажорант множества А С Е имеет наименьшее значение, то это значение называют твочкой верхней вранью множества А н обозначают аирА илн вверх (пронз- хЕА носят „супремум"). Ясно, что точная верхняя грань множества 2.7. Ограниченные множества является наименьшей из мажорант этого множества.
Множество не обязательно имеет точную верхнюю грань, но если оно ее имеет, то эта грань единственна. Если точная верхняя грань принадлежит самому множеству, то она является наибольшим значением этого множества, и обратно. Аналогично определение для творимой мимсмей орами множества А, которую обозначают ЫА или Ых (произносят еЕА инфимум"). Для ограниченного множества А С Ж числовой прямой Е понятие точной верхней грани отвечает следующим свойствам числа вирА: 1) Чж е А х < Вир А, ибо Впр А — верхняя граница множества А; 2) Че > О Зж' б А: х' > вир А — е, поскольку если бы такого я' не существовало, то число вирА — е являлось бы верхней границей множества А, меньшей чем ВирА, что противоречит определению точной верхней грани. Аналогично, число ЫА есть точная нижняя грань множества АСЖ,если: 1') Чж (= А ж > ЫА; 2) Уя > О Зж, Е А: ж, ( ЫА+ е.
Указанные свойства полезны при доказательстве теорем, связанных с понятиями точных верхней и нижней граней множества. Теорема 2.1. Всякое непустое ограниченное сверху множество А числовой прямой Е имеет единственную точную Верхнюю грань. Ч Пусть ао — любое число из А и бо — любое число, превосходящее все числа из А. Разделим отрезок [ао, Ц пополам. Если его правая половина содержит точки из А, то в качестве отрезка [а1, б1~ выбираем эту половину. Если же она не содержит точек из А, то за отрезок [а1, 6Д берем левую половину отрезка [ао, Ц. Пусть [а2, 62) — правая 90 2. ОТОБРАЖЕНИЕ МНОЖЕСТВ.
ФУНКЦИИ половина [а1, 61), если она содержит точки из А; в противном случае [ая, Ьг) — левая половина отрезка [а1, Ь1). По тому же правилу выбираем [аз, 6з], и, значит, [а„+1, 6„+1) есть правая половина [а„, Ь„), если она содержит точки из А, в противном случае [а +1, Ь„+1] — левая половина [а„, 6„). Итак, построена система вложенных отрезков [а0 Ьо):) [а1, Ь1) Э[а~, Ья) ) ... ) [а„, Ь„) Э ..., каждый из которых содержит хотя бы одну точку из А, но правее его нет точек из А.
Согласно принципу вложенных отрезков существует хотя бы одна точка Ь, принадлежащая всем этим отрезкам. Докажем, что Ь = вирА. В самом деле, докажем сначала, что правее 6 нет точек из А. Пусть 6 < х' Е А. Тогда каждый из отрезков [а„, 6„) наряду с точкой 6 должен содержать и точку х', поскольку х' не может лежать правее [а„, 6„) в силу правила построения системы вложенных отрезков. Отсюда расстояние х' — 6 между точками х' и Ь должно быть меньше длины (Ьо-а0)/2" отрезка [а„, 6„). Ноэтоневозможнопри пЕХ,удовлетворяющем неравенству Ьо — ао < х' — Ь. Поэтому правее Ь точек из А быть не может.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
