Глухов М. М. Алгебра том 1, страница 6

Простейшими комбинациями объектов некоторого множества являются его произвольные подмножества, его системы элементов, расположенных в определенном порядке, разбиения множества и др. При изучении алгебры часто возникает необходимость построения и подсчета числа различных комбинаций элементов, их упорядочиваний и группирований. В связи с этим приведем простейшие сведения комбинаторного характера.

~ 1. Отношения на множествах. Отношения эквивалентности В теории и на практике обычно приходится иметь дело с такими множествами, между элементами которых существуют определенные связи, или отношения. Так можно рассматривать в коллективах людей отношения родства, соседства, старшинства и др., на множестве прямых пространства отношения параллельности, перпендикулярности и др., на множестве целых чисел отношения равенства, делимости и др. Попытаемся, исходя из знакомых примеров, сформулировать строгое определение понятия отношения на множестве.

С этой целью проанализируем один пример подробнее. Рассмотрим отношение "а делит 6" на множестве целых чисел М = (2,3,4,5,6,7,8). Это отношение задается известным правилом, позволяющим выяснить, делится одно целое число на другое, или нет. Пользуясь этим правилом, из всех пар чисел (а, 6) множества М выпишем все те пары, в которых число а делит 6. Получим множество пар: (2, 2),(2, 4),(2, 6),(2, 8),(3, 3),(3, 6), (4, 4),(4, 8),(5, 5),(6, 6),(7, 7),(8, 8).

Аналогично, множеством пар можно задать отношение "больше" на множестве М (перечислив все пары (а, 6), в которых а, 6 б М и а > 6), и другие отношения. Эти примеры делают естественным О п р еде л е н и е 1. Бинарным отношением на множестве А называют любое подмножество р множества А2 (т. е. декартова квадрата множества А).

По аналогии с этим, п-арным отпношением на множестве А называют любое подмножество множества А". Ниже мы будем рассматривать лишь бинарные отношения и потому слово "бинарное" будем опускать. Если р — отношение на А и (а,Ь) б р, то говорят, что элемент а находится в отношении р к элементу 6. Этот факт записывают также в виде ар6 (например, а ( Ь, а > Ь, а ]] Ь, а.16 и т. д.). Отношения на множестве могут обладать различными свойствами. Наиболее важные свойства отношений выделяются следующим определением. О п р е д е л е н и е 2. Отношение р на множестве А называется: 1) рефлексивным, если Ча б А: (ара), 2) симметпричным, если Ча, 6 б А: (ар6 ~ Ьра), 3) транэитивным, если Ча, Ь, с б А: (арЬ, Ьрс ~ арс), 4) антисимметричным, если Ча, Ь Е А: (арЬ, Ьра =~ а = Ь).

Например, отношение делимости и отношение " ( " на множестве 1Ч рефлексивны, антисимметричны и транзитивны. Отношение параллельности прямых симметрично, транзитивно. Отношение перпендикулярности прямых симметрично и не обладает другими свойствами из 1) — 4). Через свойства 1) — 4) определяются важнейшие для всей математики отношения эквивалентности и частичного порядка. О п р е д е л е н и е 3.

Бинарное отношение р на множестве А называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. При этом элементы, находящиеся в отношении р, называют эквивалентными (точнее, р-эквивалентными). Значение отношений эквивалентности на множестве А определяется ) главным образом, тем, что они индуцируют разбиения множества А на непересекающиеся классы эквивалентных элементов. А именно, имеет место Т е о р е м а 1.

Если р — отношение эквиваяентностпи на множестве А, то А распадаетпся на непересекающиеся подмножестпва так, что для любых а,6 е А: а,6 содержатпся в одном подмножестпве в том и тполько том случае, когда ар6. О Обозначим через [а]р подмножество элементов из А, эквивалентных а, т.

е. [а]р — — (х Е А: хра), и докажем что А = Ц [а]р аеА Ча,б Е А: ([а]р Г~ [Ь]р Я или [а]р — [6]р). (2) Так как р — рефлексивно, то а Е [а]р для любого а Е А, и равенство (1) верно. Вместо утверждения (2) докажем эквивалентное ему утвержеде- ние: Ча, 6 б А: ([а] р П [6]р ф Я) =~ [а]р = [6]р хра =~ хр6. Это означает, что [а]р с [6]р. Аналогично получается и обратное включение. Следовательно, [а]р — — [6]р, и утверждение (3) доказано.

Если в правой части равенства (1) оставить лишь все попарно различные множества, то получим искомое разложение множества А в объеденение непустых и попарно непересекающихся подмножеств. О Разложение (1) называют разбиением множества А, индуцированным отношением эквивааентпностпи р. При этом подмножества [а' 'р называют классами эквивалентности отношения р. Легко показать что (3) 1,' 'Г' сра, срЬ, хра.

Отсюда и из свойств симметричности и транзитивности отношения р ,',6,' следует хр6. Таким образом, для любого х б А справедлива имплика- М!„' ция: ~~т 30 31 Ча,б б А: (арб ~ 32 б1: а,б б А). А = (1,2,...,п) =1,п. п1 А„— ( „)~, (4) !Р(1,п)~ = и!, (5) (6) в = (22,2г,...,2т ) 32 33 2.

Заказ М 573. любое разбиение множества индуцируется подходящим отношением эквивалентности. Покажите, что разбиение ( ! А, множества А индуцирузе1 ется следующим отношением эквивалентности р на А: Известными из средней школы примерами отношений эквивалентности являются: отношения равносильности уравнений с одним неизвестным х (ему соответствует разбиение множества всех уравнений от х на классы равносильных уравнений), отношение "параллельны или равны" на множестве прямых пространства (ему соответствует разбиение всех прямых на классы параллельных прямых), отношение подобия треугольников на плоскости (ему соответствует разбиение множества всех треугольников на классы подобных треугольников). О п р е д е л е н и е 4. Бинарное отношение на множестве А называется отношением частичного порядка, если оно рефлексивно, транзитивно и антисимметрично. Множество с заданным на нем отношением частичного порядка называют частично упорядоченным.

Типичными примерами частичного порядка являются отношение теоретико-множественного включения на множестве всех подмножеств некоторого множества, отношение делимости на множестве Я, отношение < на множестве Й и др. 8' 2. Сочетания, размещения и перестановки элементов конечного множества О п р е д е л е н и е 5. Сочетанием из п элементов множества А = (аз,...,а„) по й называется любое й-элементное подмножество множества А.

О п р е д е л е н и е 6. Размещением из п элементов множества А = (аз,..., а„) по й называется любой упорядоченный набор й различных элементов множества А. В частности, любой упорядоченный набор всех п элементов множества А, взятых по одному разу, называется перестановкой элементов множества А. Размещение из элементов множества А по й обычно записывают в виде ( а... а,„..., а,,). В дальнейшем нам наиболее часто придется встречаться с перестановками. В связи с этим для множества всех перестановок из элементов множества А введем специальное обозначение Р(А). Найдем число различных сочетаний, размещений и перестановок из элементов множества А. Так как эти числа, очевидно, не зависят от природы элементов множества А, то можно взять В этом случае говорят просто о сочетаниях и размещениях из п по й.

Введем следующие обозначения: С,'„' или Я) — число различных сочетаний из п по Й, а„или (п)ь — число различных размещений из п по Й, и'. = 1 2 ... п (читается: п-факториал), О! = 1. Т е о р е м а 2. Для любых натуральных чисел й и п > й имеют место равенства: О Сначала индукцией по й докажем утверждение (4) (для любого п > й). При й = 1 оно проверяется непосредственно. Допустим, что оно верно для всех й < т, и докажем его для й = т+ 1. С этой целью укажем метод построения всех размещений из п по т+1, использующий размещения из п по т. Возьмем любое размещение из п по т: и будем поочередно добавлять к нему в конце по одному из оставшихся (т.

е. не вошедших в в) элементов множества 1,п. Получим п — т (8) а) Сй=С„" (7) А„(п — т) 35 34 Различных РазмеЩений виДа (г1, г2,..., гт„, ~) из и по т+1. Если такУю же процедуру провести, начав с другого размещения 8' из п по т, то получим еще п — т различных размещений из п по т+ 1, причем все они будут отличны от ранее полученных, поскольку различны 8 и 8'.

Отсюда видно, что, перебрав все размещения из п по т, получим ровно различных размещений из п по т+ 1. Заметим еще, что среди полученных размещений содержится любое размещение (61,62,..., 6~» 1) из п по т+ 1. Действительно, к размещению (61,62,...,6 ) из п по т мы добавляли в конце каждый из оставшихся элементов, а поэтому должны были добавить и элемент 6„,+1.

Таким образом, (7) есть в точности число всех размещений из п по т+1. Отсюда, используя предположение индукции, получим +1 Ат п ! п. ! А„= А„(п — т) =, (и — т) = что и свидетельствует о справедливости утверждения (4) для й = т+1. Тем самым, по аксиоме полной математической индукции, равенство (4) доказано для любого й и любого п > й, или, что все равно, для любого п и любого й б 1, п. Формула (5) получается из формулы (4) при й = п.