Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Принцип включения-исключения
Этот метод (просеивания) известен еще с работ Бернулли. Решето Эратосфена – разновидность принципа включения-исключения. Рассмотрим некоторое множество A1 как универсальное множество. Это множество обладает рядом свойств: , которое обладает свойством (Дополнение не обладает свойством , а обладает свойством ) (1) Наряду с рассмотрим подмножество , которое обладает свойством Требуется найти число подмножеств не обладающих ни ни , то есть их объединения Если взять все элементы множества A и удалить все не обладающие ни ни , то получим нужное нам свойство включения-исключения: Найдем число элементов полученного множества (2) с помощью диаграмм Эйлера-Венна
= - Поставим (3) во (2): = Формулу (4) можно распространить на любое число аналогично. Свойств, то есть можно считать, что: , , причем, все элементы = обладают свойством , а не обладают таким свойством, так как не существует взаимо-однозначных соответствий между элементами множества и подмножества, то есть они близки или похожи. Раздел математики Фунтеры и категории. Для уравнения (4) характерно следующее выражение:
1)Множество не обладает свойством ( 2) обладает свойством ( хотя бы одним 3) Здесь в (5) сумму ров. осущ. По всем сочетаниям без повторения, a представляет собой число элементов, обладающих по крайней мере 2-мя свойствами 4) По крайней мере 3-мя свойствами 5) Подмножество обладает всеми свойствами Предположим для доказательства справедливости следующее соотношение: (6) Считаем, что все элементы обладают , и каждому члену выражения (6) добавим , тогда получим следующее выражение: Требуется получить или найти число элементов, не обладающих ни одним из указанных свойств, но обладает свойством ? В выражение (8) подставим (6) и (7) и получим после объединения и преобразования выражение (5). Таким образом в итоге, предположив справедливость выражения (5) согласно принципу математической индукции она справедлива. Пример: часто ставится задача найти число элементов A, обладающих k -заданным свойством. , … и не обладающее n-k свойствами , …
Сначала записываем формулу включения-исключения и проверяем ее на справедливость. Для этого каждому члену, полученного подмножества добавляем пересечение с многочленами и получаем:
Пример: подмножество A= Свойства: : , : , : 8 Найти , т.е. = - -()+ = (0; 6) =6-2- Формула (9) позволяет определить число элементов Aс заданными свойствами. В некоторых случаях ставится задача найти число. Это число обозначает W(k). Для этого введем сведущее обозначение: Т.е. здесь записано число элементов, обладающих k- , … Произведем суммирование по всем k- сочетаниям без повторений из заданных n -подмножеств, тогда: W(k) W(0)= Исходя из (9) можно доказать, что W(k) есть число элементов, обладающих в точности k -свойствами и равными Если мы хотим найти число элементов, не обладающих некоторыми свойствами, мы можем прибавить r=0, при этом получим Пример: Задача о беспорядках (как пример метода включений/исключений) Рассмотрим следующее множество: Q – множество ячеек, которые нужно поместить в A. Найти, каким количеством способов в множество Q по одному элементов в каждую ячейку, при чем ни один элемент не должен попадать в ячейку то есть в соседнюю ячейку. Необходимо найти общее число беспорядков. Пусть , где i=1, …2-n! Если есть беспорядок, то он обладает свойствами P0 Если в перестановке элемент попадает в ячейку , то обладает свойством : - множество всех перестановок, в которых не переходит в , а объединение - множество всех беспорядков. W(n) – число перестановок, имеющих… Для нахождения совпадений, тогда Есть число совпадений с фиксированным беспорядком. Если (4) подставить в (3) то получится при достаточно большом r
|