Навигация
Формула включения и исключения
44497
знаков
0
таблиц
23
изображения
2.1. Формула включения и исключения
Пусть А – конечное множество и 
. Будем обозначать через 
дополнение А1 по отношению к А, а через Card A – число элементов в А.
Тогда
.
Если и 
, то
(1)
.
Покажем, что формула (1) обобщается на случай n подмножеств 
, i=1, 2, ... n:
(2)
Действуем по индукции. Имеем
(3)
Предположим, что (2) выполняется для случая n-1 подмножеств Ai, i=1, 2,…,n-1:
(4)
Рассмотрим следующие подмножества множества An:
Применяя (4) с A=An, имеем
(5)
Подставляя (5) и (4) в (3), получаем (2). Таким образом, с учётом (1) формула (2) доказана по индукции. Эту формулу называют формулой включения и исключения. Часто её представляют в таком виде:
(6)
Формулы (2) и (6) играют основную роль в перечислении подмножеств, обладающих заданными свойствами. Посмотрим на эти формулы с другой точки зрения. Пусть элементы обладают свойством Pi, i=1, 2, …,n. Тогда мы скажем, что подмножество 
обладает свойством 
. Таким образом, если элементы А могут обладать n различными свойствами, то число элементов А, обладающих k указанными свойствами и не обладающих n-k остальными, дается формулой (6).
2.2. Общий метод «просеивания» или «пропускания через решето». Решето Сильва – Сильвестра
Формула (6) описывает последовательный процесс пересчёта, называемый решетом Сильва – Сильвестра.
Пример. Рассмотрим множество
и следующие свойства:
четное число,
и А >6, (7)
и 2 < A < 8.
Подсчитаем число элементов А, обладающих свойством 
. Обозначим подмножества, соответствующие свойствам Р1, Р2, Р3, через А1, А2, А3. Тогда
«Просеиваем» сначала А через Р1: Card A1=6. Затем просеиваем А1 через Р2 и Р3: 
, 
. Просеиваем 
через Р3: 
Итак, 
Формула (6) не позволяет, однако, перечислить элементы искомого множества. Находим его, выписывая последовательно: 
, 
, 
. Разумеется, для множества с небольшим числом элементов проще выписать искомое подмножество, однако это трудно сделать при большой мощности множества.
Похожие работы
... наука стала развиваться в XIII веке параллельно с возникновением теории вероятностей, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов. Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н. Тарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б. Паскалю (1623-1662) и П. Ферма. Комбинаторику ...
... обучения, школа предоставляет учащимся право выбора предметов по интересам и склонностям. В соответствии с требованиями была разработана программа факультативного курса по теме «Элементы комбинаторики» для 8 класса. 2.2 Программа факультативного курса Пояснительная записка В математике и ее приложениях часто приходится иметь дело с различного рода множествами и подмножествами: ...
... познания, а не наблюдателем происходящего. При обучении студентов разработке содержания внеурочного мероприятия по математике методисты рекомендуют студентам активно использовать свои знания и опыт по развитию познавательной активности учащихся, приобретенный на занятиях по психолого-педагогическими дисциплинам. Курс: Знания и умения: Психология человека знания о протекании познавательных ...
... при ошибке в его выборе, учитывать по уровневый подход. 4. Математика должна входить в набор обязательных учебных предметов любого из профилей.2 МАТЕМАТИЧЕСКИЙ ФАКУЛЬТАТИВ КАК ВЕДУЩАЯ ФОРМА ПРОФИЛЬНОГО ОБУЧЕНИЯ МАТЕМАТИКЕ В ОБЩЕОБРАЗОВАТЕЛЬНОЙ ШКОЛЕ2.1. Организационно-педагогические условия успешного функционирования математических факультативов Еще на рубеже XIX и XX вв. некоторые ...
0 комментариев