Правило включений исключений

Главная / Правило включений исключений

Правило включений исключений

Пусть у множеств А и В общая часть насчитывает k элементов. Тогда всего, в объединении множеств А и В, число элементов равно т. е.
Понятно, что, складывая числа m и n , мы засчитываем общие элементы дважды.
Правило включения – исключения распространяют на объединение произвольного числа множеств. Для трех множеств соответствующая формула написана ниже.

Теорема.

Пример.
В классе 30 человек, каждый из которых изучает иностранный язык. 20 человек изучает английский, 15 – французский и 17 – немецкий. При этом в группах изучающих по два языка насчитывается по 10 человек. Сколько человек изучает все три языка?
Применяем формулу включения – исключения:

30 = 20 + 15 +17 — 10 — 10 — 10 + x , откуда x = 8 .

Буквами А , Ф и Н обозначены множества учащихся, изучающих данный язык.

1. Решите задачу: «Имеется некоторое множество из 100 различных натуральных чисел. В нём 50 чётных чисел, 40 чисел, кратных (делящихся нацело) трём, 35 чисел, кратных пяти, 15 чисел, кратных шести, 10 чисел, заканчивающихся нулём, 8 чисел, кратных 15 и 3 числа, кратные 30». Есть ли в этом множестве, числа не делящиеся ни на 2, ни на 3, ни на 5? сколько? Есть ли нечётные числа, кратные трём? Сколько? Есть ли числа, заканчивающиеся на 5? Сколько?

2. Проиллюстрируйте решение задачи из приведённого выше примера. Для этого попробуйте подобрать такое значение количества человек, изучающих все три языка (пересечение всех трёх множеств), чтобы число людей не изучающих языки (которое вычисляется в динамической иллюстрации стало равным нулю).

3. Попробуйте проиллюстрировать решение задачи из следующего — «странного» — примера. Почему динамический иллюстратор выдаёт ошибку. Объясните.

4*. Попробуйте ввести более ли, менее ли случайные числа в динамический иллюстратор. Если данные не подходят, попробуйте менять их по одному, пока не подберёте комбинацию, дающую решение. Напишите условия, которым должны удовлетворять исходные данные задачи, чтобы задача имела решение.

files.school-collection.edu.ru

Сформулируем и докажем теорему для нахождения мощности объединения произвольного количества множеств.

Приведем два разноплановых доказательства теоремы.

I. Комбинаторное доказательство теоремы.

В силу того, что [math] (1 + (-1)) ^ t = 1^t (-1)^0 + 1 ^ (-1) ^ 1 + \ldots + 1^0 (-1)^t = \sum \limits_^ (-1)^j [/math] , имеем [math] 0 = (1 + (-1)) ^ t = \sum \limits_^ (-1)^j [/math] , то равенство доказано.

l=2[/math] — база индукции.

n[/math] множеств. Очевидно, что [math] A = \bigcup \limits_^A_i = \left( <\bigcup \limits_^A_i> \right) \cup A_n [/math] . Пусть [math] B = \bigcup \limits_^A_i [/math] ; [math]N’ = \ < 1,2, \ldots ,n-1 \>[/math] .

Исходя из предположения индукции, имеем, что [math] | B | = \sum \limits_> (-1)^ <|I|+1>\left| \bigcap \limits_ < j \in I>A_j \right| [/math]

Кроме того, так как формула верна для [math]

Очевидно, что [math] B \cap A_n = \left( \bigcup \limits_^A_i \right) \cap A_n = \bigcup \limits_^ \left( A_i \cap A_n \right) (**)[/math]

Опираясь на предположение индукции и равенство [math] (**) [/math] имеем, что [math] |B \cap A_n| = \sum \limits_> (-1)^ <|I|+1>\left| \bigcap \limits_ < j \in I>\left( A_j \cap A_n \right) \right| = \sum \limits_> (-1)^ <|I|+1>\left| \bigcap \limits_ < j\in I \cup \< n \>> A_j \right| [/math]

[math] | A | = | A_n |+\left( \sum \limits_> (-1)^ <|I|+1>\left| \bigcap \limits_ < j \in I>A_j \right| \right) — \left( \sum \limits_> (-1)^ <|I|+1>\left| \bigcap \limits_ < j\in I \cup \< n \>> A_j \right| \right)[/math] [math] =| A_n |+\left( \sum \limits_> (-1)^ <|I|+1>\left| \bigcap \limits_ < j \in I >A_j \right| \right) + \left( \sum \limits_> (-1)^ <|I|+2>\left| \bigcap \limits_ < j\in I \cup \< n \>> A_j \right| \right) [/math]

Явная формула с использованием принципа включения-исключения [ править ]

Рассмотрим [math] |A_ \bigcap A_ \bigcap . \bigcap A_| [/math] , где [math] 1\leqslant i_1 \lt i_2 \lt . \lt i_k \leqslant n [/math] . Так как некоторые [math]k[/math] позиций [math]i_1, i_2, . , i_k [/math] заняты соответствующими числами, то количество способов расставить остальные [math]n-k[/math] чисел равно [math](n-k)![/math] . То есть [math] |A_ \bigcap A_ \bigcap . \bigcap A_| = (n — k)! [/math] Количество всех способов выбрать [math]k[/math] позиций [math]i_1, i_2, . , i_k [/math] равно [math]\binom [/math] . Таким образом получаем, что:

Раскрывая [math]\binom[/math] по общеизвестной формуле, получим требуемое выражение, то есть количество беспорядков порядка [math]n[/math] .

Так как [math] d(n)=!n [/math] , то можно переписать эту формулу, как [math] !n=n!(n-1)+(-1)^ [/math]

В итоге получается необходимая формула.

Сколько есть перестановок чисел от [math] 0 [/math] до [math] 9 [/math] таких, что первый элемент больше [math] 1 [/math] , а последний меньше [math] 8 [/math] ?

Проведя несложные комбинаторные вычисления, получим:

[math] answer=\sum \limits_ (-1)^ \times f(d) [/math] ,

neerc.ifmo.ru

Формула включения-исключения

Для случая из двух множеств [math] A, B [/math] формула включения-исключения имеет следующий вид:

[math] | A \cup B | = | A | + | B | — | A \cap B |[/math]

Для случая с большим количеством рассматриваемых множеств [math] n [/math] процесс нахождения количества элементов объединения состоит в поочередном включений ошибочно исключенного и исключений ошибочно включенного. Отсюда и происходит название формулы.

Рассмотрим некоторый элемент [math] x \in \bigcup \limits_^A_i [/math] . Пусть [math] x \in \bigcap \limits_^A_ [/math] . Тогда найдем число вхождений элемента [math] x [/math] в правую часть формулы.

Докажем, что [math] \sum \limits_^ (-1)^j = 0[/math]

Таким образом, [math] k = — \sum \limits_^ (-1)^j = 1 — 0 = 1[/math] , то есть каждый элемент подсчитан в правой части формулы ровно один раз, то теорема доказана.

II. Доказательство теоремы по индукции.

l=2[/math] справедливость теоремы пояснена выше. Таким образом, [math]

Пусть [math] A [/math] — объединение [math]

Подставим полученные значения в [math](*)[/math] :

Равенство справедливо, потому что все наборы [math] I \in 2^N [/math] можно разбить на две группы :

  1. [math] I \in 2^ [/math] Это означает, что в наборе точно не будет присутствовать индекс [math] n [/math] , а будут все различные варианты индексов остальных множеств, т.е. [math] I \in 2^[/math] .
  2. Как видно из равенства, первое и третье слагаемое «отвечают» за вторую группу, а второе слагаемое за первую группу. Значит, равенство истинно и [math]|A| = \sum \limits_ (-1)^ <|I|+1>\left| \bigcap \limits_ < j \in I >A_j \right| [/math] .

    Таким образом, для [math]

    Воспользуемся принципом включения-исключения: обозначим за [math]A_i[/math] — количество перестановок из [math]n[/math] элементов, в каждой из которых [math]i[/math] -ый элемент стоит на своём месте. Тогда по формуле включения-исключения имеем:

    [math]|A_i| = (n — 1)![/math] , так как [math]i[/math] -ая позиция занята числом [math]i[/math] . [math]\binom<1>[/math] — количество способов выбрать одну [math]i[/math] -ую позицию [math] \Rightarrow \sum \limits_^ |A_i| = \binom <1>(n-1)![/math]

    [math] d(n)=n \times d(n-1)+(-1)^ [/math] ,

    где [math] d(1)=0 [/math] , а [math] d(2)=1 [/math]

    У нас есть [math] n [/math] чисел и столько же мест. Мы должны найти количество способов разместить эти числа так, что ни одно из чисел не оказалось на месте с таким же номером.

    Предположим, что первое число оказалось на месте с номером [math] i [/math] . Это можно сделать [math] n-1 [/math] способами, так как первое число может оказаться на любом месте, кроме первого. Теперь есть 2 варианта, зависящие от того, окажется ли число с номером [math] i [/math] на первом месте или нет.

    • Число [math] i [/math] на первом месте. Остается [math] n-2 [/math] мест и [math] n-2 [/math] чисел. То есть количество беспорядков от [math] n-2 [/math]

    Эти 2 случая не пересекаются и поэтому суммируются. В первом случае число [math] i [/math] занимает первое место, затем идет распределение остальных чисел, не зависящее от первого и [math] i [/math] -го чисел. Во втором же случае число с номером [math] i [/math] попасть на первое место не может, а значит займет какое-то другое место, и распределение остальных чисел уже будет другое.

    Тогда количество «плохих» перестановок по формуле включений-исключений равно:

    [math] |X|+|Y|-|X \cap Y| [/math]

    [math] 2 \times 9!+2 \times 9! — 2 \times 2 \times 8! [/math]

    где [math] deg(d) [/math] — это количество простых в факторизации числа [math] d [/math] , [math] f(d) [/math] — количество четвёрок, делящихся на [math] d [/math] .

    Таким образом, с помощью формулы включений-исключений мы суммируем количество четвёрок, делящихся на простые числа, затем отнимаем число четвёрок, делящихся на произведение двух простых, прибавляем четвёрки, делящиеся на три простых, и т.д.

    В силу того, что в сумме [math] | A | + | B |[/math] элементы пересечения [math] A \cap B [/math] учтены дважды, то уменьшаем текущее значение суммы на мощность пересечения, чтобы каждый элемент был подсчитан ровно один раз. Для наглядности воспользуемся диаграммой Эйлера—Венна для двух множеств, приведенной на рисунке справа.

    l[/math] — это количество множеств, мощность пересечения которых мы ищем. Для случая [math]

    l=1[/math] равенство обращается в тривиальное ( [math] |A| = |A_1| [/math] — истинно). Для случая [math]

    Предположим, что для [math]

    l=n-1[/math] равенство верно. Докажем, что равенство истинно для [math]

    l=2[/math] (из базы индукции), то верно равенство [math] | A | = | B | + | A_n | — | B \cap A_n | (*)[/math] .

    Докажем, что [math] | A_n |+\left( \sum \limits_> (-1)^ <|I|+1>\left| \bigcap \limits_ < j \in I >A_j \right| \right) + \left( \sum \limits_> (-1)^ <|I|+2>\left| \bigcap \limits_ < j\in I \cup \< n \>> A_j \right| \right) [/math] [math] = \sum \limits_ (-1)^ <|I|+1>\left| \bigcap \limits_ < j \in I >A_j \right| [/math]

  3. [math]\ \cup I[/math] , где [math]I \in N'[/math] Аналогично предыдущему, только в наборе будет индекс [math] n [/math] .
  4. l=n[/math] мы доказали, что равенство верно. Значит, индукционный переход верен, то есть теорема доказана.

    Подставляя соответствующие значения мощностей множеств в формулу включения-исключения, получаем:

    Рекурретное соотношение для нахождения количества беспорядков [ править ]

    1) Докажем второе соотношение:

    2) Докажем первое соотношение:

  5. Число [math] i [/math] не может оказаться на первом месте. Это эквивалентно решению задачи с [math] n-1 [/math] местами и [math] n-1 [/math] числами (первое число уже заняло место, а остальные еще нет): у каждого числа будет одно запрещенное место (у числа с номером [math] i [/math] запрещенным будет первое место). Получается количество беспорядков от [math] n-1 [/math] .
  6. Посчитаем количество «плохих» перестановок, то есть таких, у которых первый элемент [math] \leqslant 1 [/math] (множество таких перестановок обозначим [math] X [/math] ) и/или последний [math] \leqslant 8 [/math] (множество таких перестановок обозначим [math] Y [/math] ).

    Отнимая это число от общего числа перестановок [math] 10! [/math] , получим ответ.

    Дано [math] n [/math] чисел: [math] a_1, a_2. a_n [/math] . Необходимо посчитать количество способов выбрать из них четыре числа так, что они будут взаимно простыми, то есть их НОД равен единице.

    Посчитаем число «плохих» четвёрок, то есть таких, в которых все числа делятся на число [math] d \gt 1 [/math] .

    Воспользуемся формулой включений-исключений, суммируя количество четвёрок, делящихся на [math] d [/math] (но, возможно, делящихся и на больший делитель).

    Чтобы посчитать функцию [math] f(d) [/math] , надо просто посчитать количество чисел, кратных [math] d [/math] , и с помощью биномиальных коэффициентов посчитать число способов выбрать из них четвёрку.

    Смотрите так же:

    • Повысят ли пенсии в 2018 году пенсионерам фсин Изменения в пенсии сотрудников ФСИН в 2018 году Экономика России до сих пор находится в кризисном положении, из-за чего правительство всевозможными методами пытается рационально распределять средства бюджета. Это приводит к невыполнению некоторых социальных обязательств, касающихся и […]
    • Патент резины морозостойкая резина на основе пропиленоксидного каучука и природных бентонитов Изобретение относится к резиновой промышленности, в частности к разработке эластомерных материалов уплотнительного назначения с высоким уровнем морозостойкости и низким значением остаточной деформации сжатия. […]
    • Пенсия полковника в отставке Минимальная пенсия у военнослужащих в России ​ на. ​ минимум (майор, к-р​ 1991 года, то​ в 1.7 раз​ в 2.5 раза​В ГРУ надбавка 1,2.​ разы больше, чем​ лет и 5​ самому:​ пенсионеры не ждали​7,5%​ колеблется от 15​Все параметры суммируются и​ службы тоже может​ к Вооружённым силам.​ Как […]
    • Решение задач на закон сохранения заряда Примеры решения задач по теме «Закон Кулона» «Физика - 10 класс» При решении задач на применение закона Кулона используются те же приёмы, что и при решении задач в курсе механики. Надо лишь иметь в виду, что направление кулоновской силы зависит от знаков зарядов взаимодействующих тел. […]
    • Трудовой стаж женщин начисления пенсии Женщины в России отправляются на пенсию раньше мужчин. И это даже несмотря на то, что их продолжительность жизни длиннее в отличие от представителей сильной половины. Но чтобы получать деньги, положенные по старости, надо не только быть определенного возраста, но и иметь наработанный […]
    • Услуги нотариуса в балашихе Нотариусы Балашиха Ниже представлен список нотариусов в выбранной категории. Чтобы посмотреть подробную информацию по конкретному нотариусу, кликните по ФИО нотариуса. Нотариус Акимова Татьяна Владимировна Телефон: (8495) 5217747 Адрес: г. Балашиха, пр-т Ленина, д. 41, пом 1Н Часы […]
    • Мера наказания 15 лет Какая статья УК РФ предусмотрена за убийство человека? За убийство статья 105 уголовного кодекса предусматривает различные сроки и меры наказания. Также рассматривается убийство статьями 106–109, которые содержат уникальные признаки данного преступления. Сколько дают лет за убийство […]
    • Л2 штраф за смерть High Five: Изменение скорости прокачки ============================ В предстоящем апдейте High Five корейские разработчики пересмотрели систему прокачки персонажей. I.Изменен бонус по получению опыта при нахождении в пати 2 человека: 30%->10% 3 человека: 39%->20% 4 человека: 50%->30% 5 […]