Разбиение множества на части по указанным признакам. Разбиения конечного множества. Тема: Разбиение множества на классы

Очевидно, что S(n,k)=0 для k>n. Принимают также S(0,0)=1, так как пустое семейство блоков является в соответствии с определением разбиением пустого множества. С числами Стирлинга второго порядка связано много любопытных тождеств:

S(n,k)=S(n-1,k-1)+kS(n-1,k) для 0

S(n,n)=1 для n≥0, (2)

S(n,0)=0 для n>0. (3)

Формулы (2) и (3) очевидны. Для доказательства формулы (1) рассмотрим множество всех разбиений множества {1, …, n} на k блоков. Это множество распадается на два различных класса: тех разбиений, которые содержат одноэлементный блок {n}, и тех разбиений, для которых n является элементом большего (по крайней мере, двухэлементного) блока. Мощность первого класса равна S(n-1,k-1), т. е. такова, каково число разбиений множества {1, …, n-1} на (k-1) блоков. Мощность другого класса составляет kS(n-1,k), так как каждому разбиению множества {1, …, n-1} на k блоков соответствует в этом классе в точности k разбиений, образованных добавлением элемента n поочерёдно к каждому блоку.

Формулы (1)-(3) позволяют легко вычислять значения S(n,k) даже для больших значений n и k.

Вот другая рекуррентная зависимость:

Для доказательства тождества рассмотрим множество всех разбиений S(n,k) множества Х={1, …, n}. Это множество распадается на различные классы, соответствующие разным подмножествам множества Х, которые являются блоками, содержащими элемент n. Отметим, что для каждого b-элементного подмножества

Число Белла

Другими словами,

Докажем рекуррентную зависимость, связанную с числами Белла:

(принимаем

Теперь опишем алгоритм генерирования всех разбиений множества.

Отметим, что каждое разбиение p множества {1,…, n} однозначно определяет разбиение

Если нам дан список

Разбиение множества {1, …, n} мы будем представлять с помощью последовательности блоков, упорядоченной по возрастанию самого маленького элемента в блоке. Этот наименьший элемент блока мы будем называть номером блока. Отметим, что номера соседних блоков, вообще говоря, не являются соседними натуральными числами. В этом алгоритме мы будем использовать переменные pred[і], sled[і], 1≤і≤n, содержащие соответственно номер предыдущего и номер следующего блока с номером і (sled[і]=0, если блок с номером і является последним блоком разбиения). Для каждого элемента і, 1≤і≤n, номер блока, содержащего элемент і, будет храниться в переменной blok[і], направление, в котором «движется» элемент і, будет закодировано в булевской переменной wper[і] (wper[і]=true, если і движется вперёд).

Можно показать, что среднее число шагов, необходимых для построения каждого следующего разбиения, ограничено постоянной, не зависящей от n(конечно, если не учитывать число шагов, необходимых для написания разбиения).

Табл.1. Последовательность разбиений множества {1,2,3,4}

Опишем теперь алгоритм решения задачи о перечислении всех понятий.

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

Идея такова: сохраняем все разбиения меньшей размерности и комбинируем их так, чтобы

Два множества, содержащих одинаковые элементы, называются пересекающимися. В этом случае говорят, что множества пересекаются.

Два множества, нс имеющих общих элементов, называются непересекающимися. В этом случае говорят, что множества не пересекаются.

Пример 6.3.1. Множества {1,2,3,4,5}, {а,б,в,г,д} нс псрссскаются.

Непересекающимися являются множество треугольников и множество параллелограммов.

Также нс псрссскаются множества решений уравнений * 3 =3* 2 и *+3=0.

Пример 6.3.2. Пусть А - множество треугольников, площадь которых равна 6, В - множество прямоугольных треугольников.

А и В - пересекающиеся множества, так как существует треугольник, являющийся одновременно элементом множеств А и В , например треугольник со сторонами 3, 4, 5. Он прямоугольный и имеет площадь.

равную 6 (проверьте эти утверждения). Этот пример нс единственен. Приведите пример еще одного такого треугольника.

Пересекаются также множества решений уравнений х 2 +х=0 и х 2 -х=0, так как оба эти множества содержат число 0.

Заметим, термины «множества пересекаются» и «множества не пересекаются» определены для двух множеств. Если множеств будет больше, то необходимы уточнения. Например, множества могут нс иметь ни одного общего элемента, но некоторые из множеств могут пересекаться.

Пример 6.3.3. Множества {1,2}, {2,3} и {1,3} не пересекаются в совокупности, то есть нет ни одного элемента, который принадлежал бы каждому из множеств. Однако любая пара этих множеств имеет общий элемент.

Пусть дана совокупность множеств. Говорят, что множества этой совокупности попарно не пересекаются , если никакие два (различных) множества совокупности нс псрссскаются.

Пример 6.3.4. Множества {1,2,3}, {5,7}, {4,6,8} и {9} попарно не пересекаются.

Два множества могут находиться в следующих отношениях:

• 1) множества могут быть пересекающимися,
• 2) множества могут быть нспсрссскающимися,
• 3) множества могут быть связаны отношением включения.

Ясно, что первые два отношения исключают друг друга, то есть каждое из предложений «Множества псрссскаются» и «Множества нс псрссскаются» является отрицанием другого. Пересекающиеся множества, в частности, могут быть связаны отношением включения. На первый взгляд может показаться, что нспсрссскающисся множества не могут находиться в отношении включения. Это так, но только с некоторым исключением.

Пример 6.3.5. Рассмотрим два предложения:

Р = «Множества А и В пересекаются»,

Q = «Множество А содержится в множестве В».

Ясно, что РФ(). Оказывается, обратное утверждение в общем случае тоже неверно, то есть ()ФР. Контрпример: Л=0, В - любое. Как известно, 0сЯ, но это непересекающиеся множества.

Если же исключить случай пустого множества, то Q => Р. Действительно, берем любой элемент а из А. Так как A то аеВ. Значит, а общий элемент множеств А и В.

Теперь введем важное понятие разбиения множества на классы.

Пусть дана система К непустых подмножеств некоторого множества S. Говорят, что множества системы К образуют разбиение множества 5, если выполняются два условия:

• 1) подмножества попарно не пересекаются;
• 2) каждый элемент множества S лежит в некотором подмножестве.

Подмножества системы К называются классами разбиения. Количество классов может быть любым, в том числе бесконечным.

Вначале ограничимся примерами разбиений на конечное число классов

^2» ч А п.

Пример 6.3.6. Множества всех четных чисел {л* х2 } = {2п neZ} и всех нечетных чисел {2л+1 | пе ZJ образуют разбиение множества Z на два класса.

Множество всех простых чисел, множество всех составных чисел и множество {1} образуют разбиение множества N на три класса.

Множество всех положительных чисел, множество всех отрицательных чисел и множество {О J разбивают множество R на три класса

Пример 6.3.7. Докажем, что множество всех треугольников можно разбить на три класса:

А - множество остроугольных треугольников (треугольник называется остроугольным, если все его углы острые);

А-у - множество прямоугольных греугольников (треугольник называется прямоугольным, если он имеет прямой угол);

А з множество тупоугольных треугольников (треугольник называется тупоугольным, если он имеет тупой угол).

Действительно, каждый треугольник относится к одному из рассмотренных видов. При этом никакие два класса нс пересекаются. А нс пересекается ни с каким классом по определению. Покажем отсутствие общих элементов у множеств Л 2 и А 3 . Предположим, что в треугольнике есть прямой угол и тупой угол. Тогда их сумма будет больше 180 фадусов, поэтому сумма всех трех углов треугольника будет больше 180 градусов. А эго противоречит теореме о сумме углов rpeyi ольника.

Пример 6.3.8. Разобьем множество всех десятичных цифр {0,1,2,3,4,5,6;7,8,9} на 4 класса. Это можно сделать разными способами.

Первое разбиение: {1,2,3}, {4,5,6}, {7,8,9}, {0}.

Другое разбиение: {0,4,8}, {1,5,9}, {2,6}, {3,7}.

Подсчет числа всех разбиений л-элементного множества на определенное число классов является непростой задачей и решается средствами комбинаторного анализа.

При построении второго разбиения в примере мы использовали следующий принцип: вначале записали все цифры, кратные 4 (это числа вида 4/г), затем все цифры, дающие при делении на 4 остаток I (числа вида 4л+1), далее те цифры, которые дают остаток 2 (числа вида 4л+2) и, наконец, цифры, дающие остаток 3 (числа вида 4л+3).

Указанный принцип позволяет разбить на 4 класса все множество целых или натуральных чисел, при этом классы будут являться бесконечными множествами.

Теперь рассмотрим пример разбиения на бесконечное множество классов.

Пример 6.3.9. Возьмем числовую прямую. Тогда целые числа разделят прямую на промежутки. Однако это еще не совсем разбиение, нужны уточнения. Если рассмотреть отрезки, то, например, и будут иметь общий элемент 3. Не включить целые числа означает разбить не все множество R. Поэтому отнесем целое число к одному из концов промежутка, например к правому. Получим семейство промежутков вида (я;л+1], п - целое число.

Итак, семейство множеств К= {(п; п+] neZ} образует разбиение множества R действительных чисел на классы.

Приведенный пример разбиения множества R на бесконечное число классов не единственен. Например, можно считать множество Z целых чисел отдельным классом, а все другие классы - это интервалы вида (л; п+ 1). Есть и другие примеры разбиений.

Заметим, что любая классификация вещей, процессов или понятий приводит к соответствующим разбиениям.

1. Множества множеств. Мы можем рассматривать множества, состоящие из самых различных элементов. В частности, можем рассматривать множества множеств, т. е. множества, элементы которых сами суть множества. Таково, например, множество всех пар весел, имеющихся на данной лодочной станции. Множеством множеств является также множество всех спортивных команд Москвы (каждая спортивная команда есть множество составляющих ее спортсменов).

Множество всех профессиональных союзов, а также множество всех воинских частей (дивизий, полков, батальонов, рот, взводов и т. д.) данной армии являются множествами множеств. Эти примеры показывают, что множества, являющиеся элементами данного множества множеств, могут в одних случаях пересекаться, в других случаях, наоборот, не иметь общих элементов.

Так, например, множество всех профессиональных союзов СССР есть множество попарно не пересекающихся множеств, так как гражданин СССР не может быть одновременно членом двух профессиональных союзов. С другой стороны, множество всех воинских частей какой-либо армии есть пример множества множеств, некоторые элементы которого являются подмножествами других элементов: так, каждый взвод есть подмножество некоторого полка, полк есть подмножество дивизии и т. д.

Множество спортивных команд данного города состоит, вообще говоря, из пересекающихся множеств, так как одно и то же лицо может входить в несколько спортивных команд (например, в команду пловцов и в команду волейболистов или лыжников).

Замечание. Для облегчения речи иногда вместо выражения «множество множеств» употребляются как совершенно равнозначащие выражения «система множеств» или «совокупность множеств».

2. Разбиение на классы. Очень важный класс систем множеств получаем, если рассматриваем всевозможные разбиения какого-нибудь множества на попарно не пересекающиеся множества. Дано множество X, представленное в виде суммы попарно не пересекающихся подмножеств; множества, слагаемые нашей суммы, и являются элементами данного разбиения множества X.

Пример 1. М есть множество всех учащихся в средних школах Москвы. Множество М можно разбить на попарно не пересекающиеся подмножества, например, следующими двумя способами:

1) мы объединяем в одно слагаемое всех учащихся одной и той же школы (т. е. разбиваем множество всех учащихся по школам);

2) мы объединяем в одно слагаемое всех учащихся одного и того же класса (хотя бы и разных школ).

Пример 2. Пусть X есть множество всех точек плоскости; возьмем на этой плоскости какую-нибудь прямую g и разобьем всю плоскость на прямые, параллельные прямой g. Множества точек каждой такой прямой и являются теми подмножествами, на которые мы разбиваем множество X.

Если данное множество X разбито на попарно не пересекающиеся подмножества, дающие в сумме множество М, то для краткости говорят просто о разбиении множества М на классы.

Теорема 3. Пусть дано отображение f множества А на множество В. Полные прообразы всевозможных точек b множества В образуют разбиение множества А на классы. Множество этих классов находится во взаимно однозначном соответствии с множеством В.

Эта теорема, в сущности, очевидна: каждому элементу а множества А соответствует, в силу отображения, один и только один элемент множества В, так что а входит в один полный прообраз . А это и значит, что полные прообразы точек во-первых, дают в сумме все множество А, во-вторых, попарно пересекаются.

Множество классов находится во взаимно однозначном соответствии с множеством В: каждому элементу b множества В соответствует класс и каждому классу соответствует элемент b множества В.

Теорема 4. Пусть дано разбиение множества А на классы. Это разбиение порождает отображение множества А на некоторое множество В, а именно на множество В всех классов данного разбиения. Это отображение получается, если заставить соответствовать каждому элементу множества А тот класс, к которому он принадлежит.

Доказательство теоремы уже заключено в самой ее формулировке.

Пример. Тем самым, что учащиеся Москвы распределены но школам, уже установлено отображение множества А всех учащихся на множество В всех школ: каждому учащемуся соответствует та школа, в которой он учится.

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

3. Отношение эквивалентности. Пусть дано разбиение множества X на классы. Введем следующее определение: назовем два элемента множества X эквивалентными по отношению к данному разбиению множества X на классы, если они принадлежат к одному и тому же классу.

Таким образом, если мы разобьем учащихся Москвы по школам, то двое учащихся будут «эквивалентны», если они учатся в одной и той же школе (хотя бы и в разных классах). Если же мы разобьем учащихся по классам, то двое учащихся будут «эквивалентны», если они учатся в одном и том же классе (хотя бы и различных школ).

Отношение эквивалентности, только что определенное нами, очевидно, обладает следующими свойствами.

Свойство симметрии (или взаимности). Если а и b эквивалентны, то эквивалентны также и а.

Свойство транзитивности (или переходности). Если эквивалентны элементы а и а также b и с, то а и с эквивалентны («два элемента а и с, эквивалентные третьему эквивалентны между собою»).

Наконец, мы считаем каждый элемент эквивалентным самому себе; это свойство отношения эквивалентности называется свойством рефлексивности.

Три условия; рефлексивности, симметрии и транзитивности, которым подчинено отношение эквивалентности, называются условиями или аксиомами эквивалентности (а также аксиомами равенства).

Итак, всякое разбиение данного множества на классы определяет между элементами этого множества некоторое отношение эквивалентности, обладающее свойствами симметрии, транзитивности и рефлексивности.

Предположим теперь, что нам удалось, каким бы то ни было способом, установить некоторый признак, дающий нам возможность о некоторых парах элементов множества X говорить как о парах эквивалентных элементов. При этом мы требуем от этой эквивалентности, только чтобы она обладала свойствами симметрии, транзитивности и рефлексивности.

Докажем, что это отношение эквивалентности определяет разбиение множества X на классы.

В самом деле, обозначим классом данного элемента а множестиа X множество всех элементов, эквивалентных элементу а.

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

Докажем: если два класса пересекаются (т. а. имеют хоть один общий элемент), то они непременно совпадают (т. е. каждый элемент одного класса является в то же время элементом другого).

В самом деле, пусть классы имеют общий элемент с. Записывая эквивалентность двух каких-нибудь элементов х и у так: имеем по определению классов:

Следовательно, в силу симметрии с силу транзитивности.

Таким образом, два класса имеющие общий элемент с, действительно совпадают между собой.

Мы доказали, что различные классы образуют систему попарно не пересекающихся подмножеств множества X. Далее, классы в сумме дают все множество X, так как каждый элемент множества X принадлежит к своему классу.

Повторим еще раз доказанные выше результаты, объединив их в следующее предложение.

Теорема 5. Каждое разбиение на классы какого-нибудь множества X определяет между элементами множества некоторое отношение эквивалентности, обладающее свойствами симметрии, транзитивности и рефлексивности. Обратно: каждое отношение эквивалентности, установленное между элементами множества X и обладающее свойствами симметрии, транзитивности и рефлексивности, определяет разбиение множества X на классы попарно эквивалентных между собой элементов.

Понятие множества и операций над множествами позволяют уточнить представление о классификации.

Классификация - это действие распределения объектов по классам на основании сходств внутри класса и их отличия от других объектов. Классификация широко применяется в математике.

Например, натуральные числа делятся на четные и нечетные; углы бывают острые, тупые и прямые и т.д.

Любая классификация связана с разбиением некоторого множества объектов на подмножества.

Считают, что множество Х разбито на классы Х , Х ,…, Х , если:

1) подмножества Х , Х,…, Х попарно не пересекаются;

2) объединение этих подмножеств совпадает с множеством Х.

Если не выполнено хотя бы одно из этих условий, классификацию считают неправильной.

Например: а) Множество треугольников Х разбито на три класса: остроугольные, прямоугольные и тупоугольные. Действительно, выделенные подмножества попарно не пересекаются, а их объединение совпадает с множеством Х; b) Из множества треугольников Х выделили подмножества равнобедренных, равносторонних и разносторонних треугольников. Так как множества равнобедренных и равносторонних треугольников пересекаются, значит, не выполнено первое условие классификации, и разбиения множества Х на классы мы не получили.

Так как разбиение множества на классы связано с выделением его подмножеств, то классификацию можно выполнять при помощи свойств элементов множеств.

Рассмотрим, например, множество натуральных чисел. Его элементы обладают различными свойствами. Нас интересуют числа со свойством «быть кратным 3 ». Это свойство позволяет выделить из множества N подмножество, состоящее из чисел, кратных 3 . Тогда про остальные натуральные числа можно сказать, что они не кратны 3 , т.е. получаем еще одно подмножество множества N . Так как выделенные подмножества не пересекаются, а их объединение совпадает с множеством N , то имеем разбиение данного множества на два класса.

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

Рассмотрим ситуацию, когда для элементов множества заданы два свойства. Например, свойства натуральных чисел: «быть кратным 3» и «быть кратным 5». При помощи этих свойств из множества N можно выделить два подмножества: А - множество чисел, кратных 3 и В - множество чисел, кратных 5. Эти множества пересекаются, но ни одно из них не является подмножеством другого (рис. 13). Разбиения на подмножества А и В в данном случае на произошло. Но круг, изображающий множество N , можно рассматривать как состоящий из четырех непересекающихся областей. Каждая область изображает некоторое подмножество множество N . Множество I состоит из чисел, кратных 3 и 5, множество I - из чисел, кратных 3 и не кратных 5, множество III - из чисел, кратных 5 и не кратных 3, множество IV - из чисел, не кратных 3 и не кратных 5. Объединение этих четырех множеств есть множество N.

Таким образом, выделение двух свойств привело к разбиению множества N натуральных чисел на четыре класса.

Не следует думать, что задание двух свойств элементов множества всегда приводит к разбиению этого множества на четыре класса. Например, при помощи таких двух свойств «быть кратным 3» и «быть кратным 6» множество натуральных чисел разбивается

на три класса (рис. 14): I - класс чисел, кратных 6; II - класс чисел, кратных 3, но не кратных 6; III - класс чисел, не кратных 3.