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

1) объединение всех подмножеств этой системы равно множеству А;

2) никакие два различные подмножества не содержат общих элементов.

Графическое изображение разбиения множества изображено на рисунке 7.

Множество А разбито на пять классов А1, А2, А3, А4, А5.

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

Пример 1. Будем рассматривать множество учеников школы. Школа состоит из классов: 1, 2, 3, …, 11. Совокупность классов является разбиением, так как объединение учеников всех классов дает множество учеников школы, и никакие два класса не пересекаются: один и тот же ученик не может учиться в двух разных классах.

Отметим, что не всякая система подмножеств данного множества представляет собой разбиение этого множества.

Пример 3. Рассмотрим множество параллелограммов и выделим в нём следующие подмножества: а) прямоугольников, б) ромбов, в) параллелограммов с неравными сторонками и непрямыми углами. Будет ли это разбиением? Нет, потому что квадраты попадают в множество а) и в множество б).

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

При помощи одного свойства осуществляется разбиение множества, вообще, на 2 класса, при помощи двух свойств - на 4 класса, при помощи трех свойств - на 8 классов, при помощи свойств - на классов. В частных случаях может получиться меньше классов, так как некоторые из подмножеств оказываются пустыми.

Еще по теме §5. Разбиение множества на классы:

1. 1. Понятие множества. Операции над множествами. Отображения. Характеристическая функция множества
2. 9. Нигде не плотные множества. Понятие категории множеств метрического пространства. Теорема Бэра
3. Соответствие между множеством выделенных значений и множеством акцентов
4. 4.3.4 Контрастирование фрагментов и разбиение номера на сегменты
5. Определение замкнутого множества. Определение компакта. Может ли множество точек на плоскости быть одновременно открытым и замкнутым?

Голосование: 25, 13

Введение

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

Разбиения множества

Разбиение n -элементного множества X на k блоков — это семейство Q = { B 1 , …, B k }, в котором B 1 ∪ … ∪ B k = X , B i ∩ B j = Ø, B i ≠ Ø, для 1 ≤ i < j ≤ k . Обозначим множество всех разбиений множества X на k блоков через Π k (X), а через Π (X) — множество всех разбиений.

Довольно интересным является вопрос генерирования разбиений множества. Рассмотрим идею алгоритма, отвечающего на этот вопрос, описав ее в рекуррентной форме. Сначала сделаем ряд полезных замечаний. Можно показать, что разбиение Q множества {1, …, n } однозначно определяет разбиение Q n −1 множества {1, …, n −1}, которое получается из Q после удаления элемента n (или пустого блока) из соответствующего блока. Также, если имеется разбиение W = { B 1 , …, B k } множества {1, …, n −1}, то можно отыскать все разбиения Q множества {1, …, n }, для которых Q n −1 = W , т. е. такие разбиения:

B 1 ∪ { n }, …, B k ,
…
B 1 , …, B k ∪ { n },
B 1 , …, B k , { n }.

Обозначим такую последовательность через E . Тогда сформулируем несложный метод генерирования разбиений: если у нас есть список L n −1 всех разбиений множества {1, …, n −1}, то список L n разбиений множества {1, …, n } будем создавать, заменяя каждое разбиение Q в списке L n −1 на соответствующую ему последовательность E . Проиллюстрируем построение списка L n для n = 1, 2, 3.

Существует нерекуррентная реализация данного алгоритма (см. визуализатор ).

Числа Стирлинга второго и первого рода

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

S (n , k) = | Π k (X)|,

где множество X состоит из n элементов. Например, S (4, 2) = 7.

Любопытны некоторые тождества, связанные с числами Стирлинга второго рода:

• S (n , n) = 1, для n ≥ 0,
• S (n , 0) = 0, для n > 0,
• S (n , k) = S (n −1, k −1) + k S (n −1, k), для 0 < k < n
• x n = ∑ k =0: n S (n , k)[ x ] k , для n ≥ 0, где [ x ] k = x (x −1)…(x − k +1).

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

Число Белла B n — это число всех разбиений n -элементного множества:

B n = | Π (X)|, где | X | = n .

Рассмотрим несложное рекуррентное соотношение:

B n +1 = ∑ i =0: n C i , n B i

Для доказательства достаточно заметить, что множество всех разбиений множества X = {1, …, n +1} можно разделить на различные классы в зависимости от блока B , который содержит элемент n +1, или в зависимости от множества X \ B . Далее для каждого множества X \ B из {1, …, n } имеется | Π (X \ B)| = B | X \ B | разбиений множества X , которое содержит B в качестве блока. Группируя классы в зависимости от мощности множества X \ B , приходим к требуемому.

Числа Стирлинга первого рода s (n , k) — это коэффициенты при последовательных степенях переменной x в многочлене [ x ] k:

[ x ] n = ∑ k =0: n s (n , k) x k .

Для них определяются аналогичные рекуррентные соотношения, что и для чисел второго рода:

• s (n , n) = 1, для n ≥ 0,
• s (n , 0) = 0, для n > 0,
• s (n , k) = s (n −1, k −1) + (n −1) s (n −1, k), для 0 < k < n .

Разбиения чисел

Разбиение числа (натурального) n на k слагаемых — это последовательность a 1 , …, a k , такая что

N = a 1 + … + a k , a 1 ≥ … ≥ a k > 0.

Существует довольно простой способ представления разбиения числа — диаграмма Феррерса. Для разбиения a 1 , …, a k она состоит из k строк, которые соответствуют слагаемым разбиения, где i -я строка состоит из a i точек. Сопряженное разбиение — это разбиение, получающееся при перемене ролями строк и столбцов в диаграмме Феррерса.

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

Рассмотрим теперь несложный алгоритм генерирования всех разбиений числа. Обозначим через S , …, S [ d ] само разбиение числа, а через R , …, R [ d ] — информацию о том, сколько раз слагаемое S [ i ] появляется в разбиении.

1 begin 2 S := n ; R := 1; d:= 1; 3 write() ; 4 while S > 1 do 5 begin sum:= 0; 6 if S [ d ] = 1 then 7 begin sum:= sum + R [ d ]; d:= d − 1; 8 end ; 9 sum:= sum + S [ d ]; R [ d ] := R [ d ] − 1; l:= S [ d ] − 1; 10 if R [ d ] > 0 then d:= d + 1; 11 S [ d ] := l ; R [d] := sum div l ; 12 l:= sum mod l ; 13 if l ≠ 0 then 14 begin d:= d + 1; S [ d ] := l ; R [ d ] := 1 15 end ; 16 write() ; 17 end 18 end

Производящие функции

Производящая функция — это функция, которая позволяет определить явный вид общего члена рассматриваемой числовой последовательности. Так, пусть имеется последовательность { a n }, для главного члена a которой нужно найти общую формулу. Тогда введем функцию A (x) = ∑ n a n x n . Если, используя свойства рассматриваемой последовательности, удастся решить составленные для A (x) уравнения, то можно будет получить искомые элементы последовательности.

Один из примеров применения производящих функций относится к числам Фибоначчи. Они являются решением рекуррентного уравнения F n +1 = F n + F n −1 , где F 0 = F 1 = 1.

Рассмотрим производящую функцию F (x) = ∑ n f n x n . Она удовлетворяет уравнению F (x) = 1 + x + ∑ k =2:∞ (F k −2 + F k −1) x k = … = 1 + (x + x 2) F (x). Отсюда получаем, что F (x) = (1 − x − x 2) −1 . Далее находим разложение 1 − x − x 2 = (1 − a x)(1 − b x), где a = (1 + √5) ⁄ 2, b = (1 − √5) ⁄ 2. Далее, используя метод неопределенных коэффициентов, получаем F (x) = ∑ k =0:∞ (a k +1 − b k +1) x k ⁄ (a − b).

Интересно, что предел отношения f n +1 ⁄ f n равен a , т. е. «золотому сечению». Также существует связь между числами Фибоначчи и треугольником Паскаля: можно выбрать линии, пересекающие узлы треугольника, так, чтобы сумма всех чисел на одной линии соответствовала числу Фибоначчи.

Другим примером являются числа Каталана. Они появляются в контексте следующей задачи: нужно найти число различных последовательных действий, чтобы вычислить сумму S 0 , …, S n , складывая любые два рядом стоящих числа и результат помещая на их место. Тогда если обозначить искомое число через с n , то производящая функция будет выглядеть, как С (x) = ∑ n =0:∞ c n x n . Следуя аналогичным рассуждениям, как и в случае с числами Фибоначчи, получим, что С (x) = ∑ n =0:∞ C 2 n , n x n ⁄ (n +1).

Для общего представления приведем иллюстрацию для трех множеств A , B и C:

Теорема

|∪ i =1: n A i | = ∑ i =1: n | A i | − ∑ 1≤ i < j ≤ n | A i ∩ A j | + ∑ 1≤ i < j < k ≤ n | A i ∩ A j ∩ A k | − … + (−1) n −1 | A 1 ∩ … ∩ A n |.

Доказательство. Будем доказывать теорему по индукции. База индукции очевидно верна. Тогда пусть для A 1 , …, A n −1 выполняется |∪ i =1: n −1 A i | = ∑ i =1: n −1 | A i | − ∑ 1≤ i < j ≤ n −1 | A i ∪ A j | + ∑ 1≤ i < j < k ≤ n −1 | A i ∩ A j ∩ A k | − … + (−1) n −2 | A 1 ∩ … ∩ A n −1 |. Если мы применим эту формулу к сумме (A 1 ∪ … ∪ A n −1) ∩ A n = ∪ i =1: n −1 (A i ∩ A n), то получим |∪ i =1: n −1 A i ∩ A n | = ∑ i =1: n −1 | A i ∩ A n | − ∑ 1≤ i < j ≤ n −1 | A i ∩ A j ∩ A n | + ∑ 1≤ i < j < k ≤ n −1 | A i ∩ A j ∩ A k ∩ A n | − … + (−1) n −2 | A 1 ∩ … ∩ A n −1 ∩ A n |. Отсюда уже получаем |∪ i =1: n A i | = |(∪ i =1: n −1 A i) ∪ A n | = |∪ i =1: n −1 A i | + | A n | − |∪ i =1: n −1 A i ∩ A n | = ∑ i =1: n | A i | − ∑ 1≤ i < j ≤ n | A i ∩ A j | + ∑ 1≤ i < j < k ≤ n | A i ∩ A j ∩ A k | − … + (−1) n −1 | A 1 ∩ … ∩ A n |.

Литература

1. Липский В. Комбинаторика для программистов. — М.: Мир, 1988.

Визуализаторы

1. Белешко Д. Перебор разбиений (2003)

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

Классификацию мы выполняем достаточно часто. Так, натуральные числа представляем как два класса - четные и нечетные. Углы на плоскости разбиваем на три класса: прямые, острые и тупые.

Любая классификация связана с разбиением некоторого множества объектов на подмножества. При этом считают, что множество X разбито на классы X 1 , Х 2 ,..., Х n ..., если:

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

2) объединение подмножеств X 1 , Х 2 , ..., Х n , ... совпадает с множеством X. |

Если не выполнено хотя бы одно из условий, классификацию считают неправильной. Например, если из множества X треугольников выделить подмножества равнобедренных, равно-сторонних и разносторонних треугольников, то разбиения мы не получим, поскольку подмно-жества равнобедренных и равносторонних треугольников пересекаются (все равносторонние треугольники являются равнобедренными). В данном случае не выполнено первое условие разбиения множества на классы.

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

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

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

Рис. 12	Рис. 13

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

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

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

Упражнения

1 . Из множества X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} выделили подмножества X, Х 2 и Х 3 . В каком из следующих случаев множество Х оказалось разбитым на классы:

а) Х 1 = {1, 3, 5, 7, 11}, Х 2 = {2, 4, 6, 8, 10, 12}, Х 3 = {9};

б) Х 1 = {1,3,5,7,9,11},Х 1 = {2,4,6,8, 10,12},Х 1 = {10, 11,12};

в) Х 1 = {3,6, 9, 12}, Х 2 = {1,5,7, 11},Х 3 = {2, 10}?

2. Из множества Х= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} выделим подмножества:

а) А - четных чисел, В - нечетных чисел;

б) А - чисел, кратных 2; В - чисел, кратных 3; С- чисел, кратных 4;

в) А - нечетных однозначных чисел; В - четных двузначных чисел. В каком случае произошло разбиение множества Х на классы?

3 . Из множества треугольников выделили подмножества треугольников:

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

б) остроугольные, тупоугольные, прямоугольные;

в) равносторонние, прямоугольные, тупоугольные.

В каком случае произошло разбиение множества треугольников на классы?

4.На какие классы разбивается множество точек плоскости при помощи:

а) окружности;

в) прямой?

5.Перечертите комбинации фигур, приведенные на рисунке 15, и на каждой из них выделите (различными видами штриховки) непересекающиеся области.

6. На множестве натуральных чисел рассматривается свойство «быть кратным 7». Сколько классов разбиения множества N оно определяет? Назовите по два элемента из каждого класса.

7. Из множества четырехугольников выделили подмножество фигур с попарно параллельными сторонами. На какие классы разбивается множество четырехугольников с помощью свойства «иметь попарно параллельные стороны»? Начертите по два четырехугольника из каждого класса.

8 . Изобразите при помощи кругов Эйлера множество N натуральных чисел и его подмножества: четных чисел и чисел, кратных 7. Можно ли утверждать, что множество N разбито:

а) на два класса: четных чисел и чисел, кратных 7;

б) на четыре класса: четных чисел, кратных 7; четных чисел, не кратных 7; нечетных чисел, кратных 7; нечетных чисел, не кратных 7?

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

10 . Изменится ли ответ в упражнении 9, если на множестве четырехугольников рассмотреть свойства:

а) «быть прямоугольником» и «быть ромбом»;

б) «быть прямоугольником» и «быть трапецией»?

11. На рисунке 16 изображены множество X- студентов группы, А - множество спортсменов этой группы, В - множество отличников этой группы.

а) Укажите классы разбиения множества X, полученные с помощью свойств «быть спортсменом» и «быть отличником», и охарактеризуйте каждый из них.

б) Сколько получилось бы классов разбиения, если бы ни один отличник группы не был спортсменом?

Выполните соответствующий рисунок и назовите классы разбиения.

12 . Покажите, что решение нижеприведенных задач связано с разбиением заданного множества на классы:

а) 18 редисок связали в пучки по 6 редисок в каждом. Сколько получилось пучков?

б) 18 карандашей раздали 6 ученикам поровну. Сколько карандашей у каждого?

13. О каких множествах и операциях над ними идет речь в задачах:

а) С одной грядки сняли 25 кочанов капусты, а с другой - 15 кочанов. Всю эту капусту разложили в корзины, по 8 кочанов в каждую. Сколько потребовалось корзин?

б) Для школьного сада привезли 24 саженца яблонь. На одном участке посадили 6 саженцев, а на другом - остальные, в 3 ряда поровну. Сколько саженцев посадили в каждом ряду?

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

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

Как правило, целью классификации является систематизация наших знаний. Например, в биологии имеется классификация жи­вотных, охватывающая до 1,5 млн. различных видов животных, в ботанике - классификация растений, включающая 500 тыс. видов растений. Классификация дает возможность рассмотреть это много­образие в определенной системе, выделить интересующие нас виды растений или животных.

Широко применяется классификация в математике. Например, натуральные числа делятся на четные и нечетные; углы (меньше развернутого) бывают острые, прямые и тупые.

Каким условиям должна удовлетворять правильно выполненная классификация?

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

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

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

2) объединение подмножеств Х1, Х2, ..., Хn совпадает с множеcтвом Х

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

Так, множество Х треугольников можно разбить на три класса: остроугольные, прямоугольные и тупоугольные. Действительно, вы­деленные подмножества попарно не пересекаются (среди остроуголь­ных треугольников нет прямоугольных и тупоугольных, среди пря­моугольных - тупоугольных) и их объединение совпадает с мно­жеством X.

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

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

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

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

10. Определите классы разбиения множества X четырехуголь­ников, если оно осуществляется при помощи:

1) свойства «быть прямоугольником»;

2) свойств «быть прямоугольником» и «быть ромбом»;

3) свойств «быть прямоугольником» и «быть квадратом»;

4) свойств «быть прямоугольником» и «быть трапецией».

11. Покажите, что решение задач связано с разбиением задан­ного множества на попарно непересекающиеся подмножества:

1) 12 флажков пионеры раздали октябрятам, по 2 флажка каждому. Сколько октябрят получили флажки?

2) Для игры в волейбол 12 ребят разбились на 2 команды поровну. Сколько ребят стало в каждой команде?

12. О каких множествах и операциях над ними идет речь в задачах:

1) С одной грядки сняли 25 кочанов капусты, а с другой-15 кочанов. Всю эту капусту разложили в корзины, по 8 кочанов в каждую. Сколько потребовалось корзин?

2) Для школьного сада привезли 24 саженца яблонь. На одном участке пионеры посадили 6 саженцев, а на другом - остальные, в 3 ряда поровну. Сколько саженцев посадили в каждом ряду?

3) Для детского сада купили 9 коробок цветных карандашей, по 6 штук в каждой, и 46 черных карандашей. Сколько всего карандашей купили?

4) Марки, собранные для коллекции, Толя разместил на 3 листа альбома, по 6 штук на каждом листе. 4 из них Толя подарил другу. Сколько марок у него осталось?