Число Стирлинга второго рода 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,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 -элементного множества на m частей, в то время как мультиномиальный коэффициент выражает количество упорядоченных разбиений n -элементного множества на m частей фиксированного размера . Количество всех неупорядоченных разбиений n -элементного множества задается числом Белла .

Примеры

Wikimedia Foundation . 2010 .

• Индикатор (математика)
• Р (кириллица)

Смотреть что такое "Разбиение множества" в других словарях:

Разбиение - В математике Разбиение единицы Разбиение множества Разбиение интервала Разбиение числа … Википедия

Разбиение графа - Пример разбиения параллельной граф схемы алгоритма логического управления. В составе блоков, отмеченных разными цветами, нет параллельных вершин Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется… … Википедия

Разбиение Вороного

Разбиение Дирихле - Диаграмма Вороного случайного множества точек на плоскости Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к… … Википедия

РАЗБИЕНИЕ - 1) Р. представление заданного множества в виде объединения системы множеств, не имеющих попарно общих точек. В дискретной геометрии часто рассматривают Р. нек рого пространства на замкнутые области, к рые покрывают все пространство и попарно не… … Математическая энциклопедия

Разбиение числа - n это представление n в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается (в отличие от композиций), то есть разбиения, отличающиеся только порядком частей, считаются равными. В… … Википедия

Мера множества - У этого термина существуют и другие значения, см. Мера. Мера множества неотрицательная величина, интуитивно интерпретируемая как размер (объем) множества. Собственно, мера это некоторая числовая функция, ставящая в соответствие каждому… … Википедия

Двоичное разбиение пространства - BSP дерево это структура данных, используемая в трехмерной графике. Аббревиатура BSP означает Binary Space Partition двоичное разбиение пространства. BSP дерево используется для эффективного выполнения следующих операций: Сортировки… … Википедия

ИЗМЕРИМОЕ РАЗБИЕНИЕ - пространства с мерой (М,m) разбиение x. этого пространства на непересекающиеся подмножества (именуемые элементами разбиения), к рое можно получить как разбиение на множества уровня нек рой измеримой функции (с числовыми значениями) на М. Это… … Математическая энциклопедия

НЕПРЕРЫВНОЕ РАЗБИЕНИЕ - топологического пространствах покрытие пространства Xпопарно непересекающимися непустыми множествами, удовлетворяющее условию: каковы бы ни были и окрестность Uмножества Fв X, найдется окрестность Vмножества Fв X, содержащаяся в Uи являющаяся… … Математическая энциклопедия

Книги

• Windows IT Pro/RE№ 06/2018 , Открытые системы. Windows IT Pro/RE– профессиональное издание на русском языке, целиком и полностью посвященное вопросам работы с продуктами семейства Windows и технологиям компании Microsoft. Журнал… Купить за 1176 руб электронная книга
• Минимакс и восстановление по вектору в графах , Мокряков Алексей Викторович, Селин Павел Сергеевич, Цурков Владимир Иванович. В предлагаемой книге развивается теория минимакса при транспортных ограничениях. Представлена основная постановка о поиске минимума максимального элемента матрицы с неотрицательными…