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

Число Стирлинга второго рода S ( n , k ) определяется как число разбиений n-элементного множества на k блоков:

Очевидно, что 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}

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

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

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

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

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

Определение . Множество А разбито на классы А 1 , А 2 , ..., А п , если:

1) подмножества А 1 , А 2 , ..., А п не пусты;

2) подмножества А 1 , А 2 , ..., А п попарно не пересекаются;

3) объединение подмножеств совпадает с множеством А .

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

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

Если из множества треугольников выделить подмножества равносторонних, равнобедренных и разносторонних треугольников, то разбиения мы не получим, т.к. множество равносторонних треугольников является подмножеством равнобедренных треугольников, т.е. не выполняется второе условие разбиения множества на классы.

Пример 1 . Пусть А – множество двузначных чисел. Рассмотрим на этом множестве свойство «быть четным».

А

А 1 – множество четных чисел,

А 2 – множество нечетных чисел, при этом

А 1 È А 2 = А и А 1 Ç А 2 = Æ.

Т.о. задание одного свойства приводит к разбиению этого множества на 2 класса.

Пример 2. Пусть А – множество треугольников. Рассмотрим на данном множестве два свойства: «быть прямоугольным» и «быть равнобедренным». При помощи этих свойств из множества треугольников можно выделить 2 подмножества: В С – множество равнобедренных треугольников. Эти множества пересекаются, но ни одно из них не является подмножеством другого.

По рисунку видно, что получилось 4 класса:

I – В Ç С – множество равнобедренных прямоугольных треугольников;

II – В Ç – множество прямоугольных, но не равнобедренных треугольников;

III – Ç С – множество равнобедренных, но не прямоугольных треугольников;

IV – Ç – множество не равнобедренных и не прямоугольных треугольников.

Т.о. с помощью двух свойств множество разбилось на 4 класса, таких, что их пересечение пусто, а их объединение составляет множество А .

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

Пример 3 . Пусть А – множество треугольников. Рассмотрим на данном множестве два свойства: «быть прямоугольным» и «быть остроугольным». При помощи этих свойств из множества треугольников можно выделить 2 подмножества: В – множество прямоугольных треугольников и С – множество остроугольных треугольников. Эти множества не пересекаются. По рисунку видно, что при помощи этих свойств множество треугольников разбивается на три класса:

I – множество прямоугольных треугольников;

II – множество остроугольных треугольников;

III – множество не прямоугольных, не остроугольных треугольников.

Контрольные вопросы

1. При каких условиях считают, что множество разбито на классы?

2. Как определить число элементов в объединении двух или трех конечных множеств?

Разбиение конечного множества образует любое семейство непустых и непересекающихся подмножеств его элементов, обычно называемых классами, когда каждый элемент является представителем своего класса. Каждый класс однозначно определяет состав его элементов, а порядок перечисления классов разбиений и элементов классов не имеет значения. Различными считаются разбиения, которые отличаются числом классов или составом хотя бы двух классов. Например, существует всего 5 различных разбиений трехэлементного множества {X,Y,Z} на классы. Эти разбиения перечислены ниже в таком порядке, когда число их классов не убывает:

{ {X,Y,Z} }; { {X,Y}, {Z} }; { {X,Z}, {Y} }; { {X}, {Y,Z} }; { {X}, {Y},{Z} }.

Если зафиксировать количество классов, то в общем случае число разбиений множества из n элементов на m классов при любых n ≥ m ≥ 0 оказывается соответствующим по значениям для чисел Стирлинга второго рода . Формально эти числа определяют коэффициенты разложения степени n произвольной переменной Z по убывающим m -факториалам от Z при всех целых значениях m от 0 до n :

Z n = (Z) 0 + (Z) 1 + ... + (Z) m + ... + (Z) n .

В этом разложении фигурные коэффициенты обозначают числа Стирлинга второго рода, а убывающие факториалы, перед которыми они стоят, определяют следующие произведения:

(Z) m = Z(Z−1)(Z−2) … (Z−m+1).

Учитывая выражение для убывающих факториалов, указанное разложение, например при n=3 можно записать следующим образом:

Z 3 = + Z + Z(Z - 1) + Z (Z - 1)(Z - 2).

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

0 ; = 1 ; = 3 ; = 1 ;

В общем случае значения чисел Стирлинга второго рода при любых целых величинах n≥m≥0 можно записать в форме бесконечной нижнетреугольной матрицы, которая называется треугольником Стирлинга второго рода . Его начальный фрагмент, например, при 0≤n,m≤8 можно представить следующей таблицей:

Таблица 1

По своей структуре эта таблица похожа на треугольник Паскаля. Ее внутренние элементы определяются по следующему мнемоническому правилу. Каждое число в любой строке n>0 и столбце m>0 равно сумме числа слева над ним и непосредственно над ним, которое умножено на m . Это правило иллюстрирует следующий пример для n=3 и m=2 :

2 = 1 + 2∙1 = 3 .

В общем случае данное правило формально отражает следующее рекуррентное соотношение, которое справедливо для любых натуральных значений n≥m>0 :

Граничные условия для этого рекуррентного соотношения определяют следующие значения чисел Стирлинга второго рода при m=0 и m=n :

0 ; = 1 ; = 1.

2 = + + 2 = 0 + 1 + 2∙1 = 3 .

N(n - 1)2 и = 2 n-1 - 1 .

Следующий пример показывает, как с их помощью найти значение числа Стирлинга второго рода при n=6 и m=4 более коротким путем, чем по базовому рекуррентному соотношению:

4 = + 3 + 4= (2 4-1 - 1) + 34(4 - 1)2 + 45(5 -1)2 = 65.

Как отмечалось выше, числа Стирлинга второго рода дают мощность множества разбиений n элементов на фиксированное число классов m≤n . Общее число всех разбиений n элементов без ограничения по числу классов определяется числом Белла , значение которого равно следующей сумме чисел Стирлинга второго рода:

B n = + ... + + ... +

Принимая величину B 0 = 1 , для вычисления значений чисел Белла можно использовать также следующую рекуррентную зависимость с биномиальными коэффициентами:

B n = B 0 + B 1 + ... + B k + ... + B n

Результаты рекуррентных вычислений чисел Белла для всех значений n от 0 до 10 приведены в следующей таблице:

Таблица 2

Из таблицы значений чисел Белла следует, что мощность множества разбиений быстро растет с увеличением количества элементов. Поэтому для решения разнообразных практических задач необходимо иметь комбинаторные алгоритмы, которые обеспечивают систематический перебор разбиений конечных множеств элементов любой мощности. По ряду причин перебор разбиений целесообразно производить в порядке минимального изменения состава их классов, когда любые 2 последовательных разбиения отличаются расположением только одного элемента в их классах. Очевидно, такое изменение следует считать минимальным. Например, в следующей последовательности все 5 разбиений множества {X,Y,Z} перечислены в порядке минимального изменения, а элементы, которые при этом переходят в другой класс, выделены подчеркиванием:

{ {X,Y,Z } }; { {X,Y }, {Z} }; { {X}, {Y}, {Z } }; { {X} {Y,Z } }; { {X,Z} {Y} }.

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

{ {1,2,3} }; { {1,2}, {3} }; { {1}, {2}, {3} }; { {1} {2,3} }; { {1,3} {2} }.

В рекурсивном алгоритме минимального изменения такая последовательность, в общем случае, строится по следующему рекуррентному правилу. Пусть уже получен список всех разбиений множества из (n−1) натуральных чисел от 1 до (n−1) , где классы упорядочены по возрастанию своих наименьших элементов, а любые последовательные разбиения минимально различны, в указанном выше смысле. Каждое разбиение этого списка дополняется одноэлементным классом {n} , а его классы дополняются элементом n . Причем указанные дополнения для нечетных по номеру разбиений производятся в порядке возрастания минимальных элементов классов и заканчиваются добавлением одноэлементного класса. Для четных по номеру разбиений такие же дополнения производятся в обратном порядке. В результате этой обработки получается уже список разбиений множества из n натуральных чисел, где все классы по-прежнему остаются упорядоченны по возрастанию своих наименьших элементов, а любые два соседних разбиения отличаются только расположением элемента n и, следовательно, минимально различны. Следующая диаграмма демонстрирует пример рассмотренного рекурсивного процесса, который начинается с одноэлементного множества {1} и завершается списком разбиений множества из трех чисел {1,2,3} . Для наглядности разбиения каждого уровня пронумерованы, а добавленные элементы выделены подчеркиванием, кроме того, стрелки указывают направление добавлений:

Для практической реализации рекурсивного алгоритма минимального изменения удобно задать каждое разбиение вектором наименьших элементов его классов. Тогда в общем случае любое разбиение множества последовательных натуральных чисел от 1 до n представляется вектором E(n) из n значений, где каждое значение E j обозначает наименьший элемент класса, которому принадлежит элемент j . Такое соответствие можно формально задать следующим образом:

E j = min i | E j = E i ; j = 1, ... n .

Для примера в следующей таблице перечислены все 5 последовательных разбиения множества {1,2,3} и соответствующие им векторы наименьших элементов их классов E(3) :

Таблица 3

В соответствие с рекурсивным алгоритмом каждый вектор наименьших элементов E(n) классов разбиения множества из n элементов расширяет соответствующий вектор E(n−1) значением E n для добавленного элемента n . При этом нужно последовательно присвоить E n все различные значения из вектора E(n−1) , которые равны по величине своим индексам (j=E j) и n . Для нечетных по номеру векторов E(n−1) такое присваивание делается в порядке возрастания индексов, что соответствует увеличению значений наименьших элементов классов разбиения, и завершается присваиванием E n = n :

E n = E j | E j = j = 1, … n.

Например, вектор E(3) = (1,2,1) , который соответствует разбиению { {1,3}, {2} } , с нечетным порядковым номером 5 расширяется в следующие различные варианты вектора E(4) , образуя соответствующие им разбиения множества {1,2,3,4} :

E(3) = (1 ̲ 1 2 2 1 3) + (E4 = 1 1) −> (1 1 2 2 1 3 1 4) = E(4) ~ Ё;

E(3) = (1 1 2̲ 2 1 3) + (E4 = 2 2) −> (1 1 2 2 1 3 2 4) = E(4) ~ { {1 3} {2 4} };

E(3) = (1 1 2 2 1 3) + (E4 = 4) −> (1 1 2 2 1 3 4 4) = E(4) ~ { {1 3} {2} {4} }.

Для четных по номеру векторов E(n−1) дополнение производится аналогично, но в порядке уменьшения значений наименьших элементов классов, и начинается присваиванием E n = n :

E n = E j | E j = j = n, … 1.

Например, вектор E(3)=(1,2,2) , который соответствует разбиению { {1}, {2 3} } , с четным порядковым номером 4 расширяется в следующие различные варианты вектора E(4) , образуя соответствующие им разбиения множества {1,2,3,4} :

E(3) = (1 1 2 2 1 3) + (E4 = 1 1) −> (1 1 2 2 1 3 1 4) = E(4) ~ { {1} {2 3} {4} };

E(3) = (1 1 2̲ 2 1 3) + (E4 = 2 2) −> (1 1 2 2 1 3 2 4) = E(4) ~ { {1} {2 3 4} };

E(3) = (1̲ 1 2 2 1 3) + (E4 = 4) −> (1 1 2 2 1 3 4 4) = E(4) ~ { {1 4} {2 3} }.

Несмотря на простоту, рассмотренный рекурсивный алгоритм нельзя признать экономичным, так как приходится последовательно порождать разбиения всех множеств с мощностями от 1 до n , хотя требуется получить разбиение только множества из n элементов. В этом отношении более привлекательным представляется итерационный алгоритм минимального изменения разбиений, который реализует систематический переход элементов между классами. При этом на каждой итерации очередное разбиение образуется из предыдущего переходом одного элемента в соседний класс слева или справа, если считать, что классы упорядочены по возрастанию значений своих наименьших элементов. Такой переход может изменять состав классов при сохранении их числа и приводить к удалению или образованию одноэлементного класса. В любом случае разбиения двух соседних итераций отличаются расположением только одного элемента в своих классах и, следовательно, минимально различны. В частности, следующая последовательность переходов элементов обеспечивает перечисление разбиений множества {1,2,3} в порядке минимального изменения, а стрелки указывают направление перехода элементов между классами:

{ { 1 2 ->3} }; { { 1 ->2}, { 3 } }; { {1}, { ->2}, {3} }; { {1} { 2 <-3 } }; { {1 3} {2} }.

В общем случае для систематической организации итерационного процесса важно установить правила перехода. Они должны обеспечивать выбор направления, элемента и классов перехода на каждой итерации при генерации разбиений любого множества последовательных чисел от 1 до n. Для формального описания этих правил удобно, как и раньше, задавать каждое разбиение вектором (E 1 ,…E j, …,E n) наименьших элементов его классов, где:

E j = min i | E j = E i .

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

m = max j | (E ←j > 1 или E →j < j).

Для удобства практической реализации этого правила целесообразно ввести знаковую функцию d(j) кодирования направления перехода каждого элемента j . Она должна принимать значение +1 или −1 при переходе элемента j вправо или влево, соответственно. Тогда в правиле выбора переходного элемента m можно исключить альтернативную проверку направления перехода и записать его следующим образом:

Em должно быть выполнено следующее соотношение:

t < E m ≤ m.

Если для выбранного элемента m установлено направление перехода вправо, то возможны два случая. В одном случае элемент m переходит в соседний справа класс, где наименьший элемент меньше, чем m . В другом случае, когда наименьший элемент соседнего справа класса больше, чем m , или элемент m принадлежит крайнему правому классу разбиения, из m должен быть образован одноэлементный класс {m} .

Оба указанных случая учитывает следующее формальное правило, которое идентифицирует наименьший элемент t класса, куда попадет элемент m после перехода вправо:

t = min { m; E (j > m) | E j > E m }.

Очевидно, что при переходе элемента m вправо, между значениями t , m и E m должно быть выполнено следующее соотношение:

E m < t ≤ m.

Оба правила идентификации класса для перехода выбранного элемента m влево или вправо можно формально объединить, используя числовой код d(m) направления перехода элемента m . Такое комплексное правило автоматически учитывает направление перехода элемента m и идентифицирует наименьший элемент t класса для его перехода следующим образом:

t = min { m; E j | d(m)∙E j > d(m)∙E m }.

Независимо от способа идентификации формальный переход выбранного элемента m в класс с наименьшим элементом t обеспечивает следующее присваивание:

E m <− t .

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

d(→j)∙E j = j или d(←j)∙E j = −1 при j = 1, …, n .

Выполнение итераций рассмотренного итерационного алгоритма иллюстрируется в следующей таблице, где последовательные разбиения множества чисел {1,2,3} записаны в традиционном и векторном формате, а стрелки и знаки индексов обозначают направления перехода элементов:

Таблица 4

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

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

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

Считается, что множество X разбито на классы X 1 , X 2 ,..., Х n , если:

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

2) объединение подмножеств Х 1 , Х 2 , ..., Х n совпадает с множеством X.
Если не выполнено хотя бы одно из этих условий, классификацию считают

неправильной.

Так, множество X треугольников можно разбить на три класса: остроугольные, тупоугольные и прямоугольные. Выделенные подмножества попарно не пересекаются и их объединение совпадает с подмножеством X.

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

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

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

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

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

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

Выделение двух свойств натуральных чисел привело к изменению множества натуральных чисел на 4 класса: класс чисел, кратных 3 и 5; класс чисел, кратных 3 и не кратных 5; класс чисел, кратных 5 и не кратных 3;.класс чисел, не кратных 3 и не кратных 5.

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