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

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

Как правило, целью классификации является систематизация наших знаний. Например, в биологии имеется классификация жи­вотных, охватывающая до 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 из них Толя подарил другу. Сколько марок у него осталось?

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

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

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

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

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

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.

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

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

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

Считается, что множество 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 класса. Так бывает не всегда. Например, при помощи двух свойств «быть прямоугольным» и «быть тупоугольным» множество треугольников разбивается на три класса: класс прямоугольных треугольников; класс тупоугольных треугольников; класс треугольников, не являющихся ни прямоугольными, ни тупоугольными треугольниками.

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

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

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

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

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

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

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

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

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

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

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

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

Голосование: 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)