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

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

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

Любая классификация связана с разбиением некоторого множества объектов на подмножества. При этом считают, что множество 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 ряда поровну. Сколько саженцев посадили в каждом ряду?

Развитие представлений о числе составляет важную часть нашей истории. Оно является одним из основных математических понятий, которое позволяет выразить результаты измерения или счета. Исходным для множества математических теорий служит понятие числа. Оно применяется также в механике, физике, химии, астрономии и множестве других наук. Кроме того, в повседневной жизни мы постоянно пользуемся числами.

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

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

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

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

Знание математики Древнего Египта основано сегодня на двух папирусах, которые датируются приблизительно 1700 годом до н. э.

Письменность в Древнем Египте была основана на иероглифах. Пользовались египтяне непозиционной десятичной системой, в которой количеством вертикальных черт обозначались числа от 1 до 9. Индивидуальные символы вводились для степеней десяти. История развития числа в Древнем Египте продолжилась следующим образом. С возникновением папируса было введено иератическое письмо (то есть скоропись). Специальный символ использовался в нем для обозначения чисел от 1 до 9, а также кратных 10, 100 и т. д. Развитие рациональных чисел в то время происходило медленно. Они записывались, как сумма дробей с равным единице числителем.

На использовании различных букв алфавита была основана греческая система счисления. История натуральных чисел в этой стране отмечена тем, что употреблявшаяся с 6-3 веков до н. э. аттическая система для обозначения единицы применяла вертикальную черту, а 5, 10, 100 и т. д. писались с помощью начальных букв их названий на греческом языке. В ионической системе, более поздней, использовались для обозначения чисел 24 действующие буквы алфавита, а также 3 архаические. Как первые 9 чисел (от 1 до 9) обозначались кратные 1000 до 9000, однако перед буквой ставилась при этом вертикальная черта. "М" обозначались десятки тысяч (от греческого слова "мириои"). После нее следовало число, на которое следовало умножить 10000.

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

История счисления в Индии

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

Современные цифры произошли от индийских значков, начертание которых использовалось еще в 1 веке н. э. Изначально индийская нумерация была изысканной. Средства для записи чисел до десяти в пятидесятой степени применялись в санскрите. Сначала для цифр использовалась так называемая "сиро-финикийская" система, а с 6 века до н. э. - "брахми", с отдельными знаками для них. Эти значки, несколько видоизменившись, стали современными цифрами, называемыми сегодня арабскими.

Возникновение понятия натурального числа.

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

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

1. 
   Виды письменной нумерации.

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

Счет стал развиваться быстрее с того времени, когда люди догадались обратиться к своим пальцам. Именно они стали тем простым и в то же время уникальным «аппаратом», который положил дальнейшее начало развитию нумерации письменной.

Существовал, конечно, и словесный счет, но он стал активен только после того, как развилось сельское хозяйство.

Со временем многие народы стали придумывать наименованиям различные слова, которые и закрепились за числами. Например, если необходимо было обозначить число один, то его обозначали как «нос». «рот», «голова» (тем, что имеется у человека в одном количестве). Соответственно, за числом два закрепились слова «глаза», «руки», «ноги» и т. д.

Пальцевой счет постепенно привел к тому, что счет стал упорядочиваться, а человек, соответственно словесно упрощал числа. Допустим, выражение, которое соответствовало числу 13 – «десять пальцев на обеих ногах и три пальца на одной руке» - упрощалось в «палец на руке»; для выражения числа 26 вместо слов «десять пальцев на обеих ногах, десять пальцев на обеих руках и три пальца на ноге другого человека» говорилось иначе: «три пальца другого человека».

Первым русским памятником математического содержания до настоящего времени считается рукописное сочинение новгородского монаха Кирика, написанное им в 1136 г.

К XVI в. относится изобретение замечательного счетного прибора, получившего впоследствии название «русские счеты».

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

Лекция №7

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

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

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

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

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

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

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

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

Определение. Считают, что множество Х разбито на классы Х 1 , Х 2 ,…,Х п, если:

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

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

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

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

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

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

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

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

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

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

Проанализируем получившуюся картину. Круг, изображающий множество N натуральных чисел, разбился на 4 непересекающиеся области – они пронумерованы римскими цифрами. Каждая область изображает некоторое подмножество множества N. Определим, какие числа оказались в каждом из этих непересекающихся подмножеств. Подмножество I состоит из чисел, кратных 3 и 5; подмножество II – из чисел, кратных 3 и не кратным 5; подмножество III – из чисел, кратных 5 и не кратных 3; подмножество IY – из чисел, не кратных 3 и не кратных 5. Объединение этих четырех подмножеств есть множество 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)

Множеств , где - некоторое множество индексов (конечное или бесконечное), называется разбиением , если:

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

Разбиения конечных множеств

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

Например, число Стирлинга второго рода представляет собой количество неупорядоченных разбиений 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 руб электронная книга
• Минимакс и восстановление по вектору в графах , Мокряков Алексей Викторович, Селин Павел Сергеевич, Цурков Владимир Иванович. В предлагаемой книге развивается теория минимакса при транспортных ограничениях. Представлена основная постановка о поиске минимума максимального элемента матрицы с неотрицательными…