Включения исключения

Беспорядок (Derangement) — это перестановка чисел от 1 , в которой ни один элемент не стоит на своем месте.

Количество беспорядков порядка n

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

Таким образом ,то есть количество искомых беспорядков.

Рассмотрим . Таким образом получаем, что:

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

Формула включений и исключений для двух множеств

Для любых конечных множеств $A$ и $B$ справедливо равенство:

Формула включений и исключений для трех множеств

Для любых конечных множеств $A$, $B$ и $C$ справедливо равенство:

Поясним кратко, откуда берутся слагаемые справа. Назовём двукратными элементы, входящие в пересечение ровно двух множеств, и трёхкратными — элементы, входящие в пересечение трёх множеств. Сложив мощности $A$, $B$ и $C$, мы дважды учли каждый двукратный элемент и трижды — каждый трёхкратный. Вычтя три попарных пересечения, мы «восстановили справедливость» в отношении двукратных элементов, но при этом трижды вычли трехкратные элементы, которые теперь оказались полностью неучтёнными. Поэтому надо добавить мощность тройного пересечения.

Разберем примеры решений типовых задач с этой формулой включений и исключений для случая 2 и 3 множеств (другие примеры подобных заданий вы найдете в разделе Примеры по дискретной математике: Множества и отношения).

Доказательство основного утверждения

| {A i ∣ 1 ⩽ i ⩽ t} | – | {A i ∩ A j ∣ 1 ⩽ i < j ⩽ t } | + ⋯ + ( − 1) t + 1 | { A 1 ∩ A 2 ∩ ⋯ ∩ A t } | = ( t 1) − ( t 2) + ⋯ + ( − 1) t + 1 ( t t). {\displaystyle {\begin{aligned}|\{A_{i}\mid 1\leqslant i\leqslant t\}|-|\{A_{i}\cap A_{j}\mid 1\leqslant i<j\leqslant t\}|+\cdots="" +(-1)^{t+1}|\{a_{1}\cap="" a_{2}\cap="" \cdots="" \cap="" a_{t}\}|="{\binom" {t}{1}}-{\binom="" {t}{2}}+\cdots="" +(-1)^{t+1}{\binom="" {t}{t}}.\end{aligned}}}<img alt="{\ displaystyle {\ begin {align} | \ {A_ {i} \ mid 1 \ leqslant i \ leqslant t \} | – | \ {A_ {i} \ cap A_ {j} \ mid 1 \ leqslant i

По биномиальной теореме,

0 = (1 – 1) t = (t 0) – (t 1) + (t 2) – ⋯ + ( – 1) т (тт). {\ displaystyle 0 = (1-1) ^ {t} = {\ binom {t} {0}} – {\ binom {t} {1}} + {\ binom {t} {2}} – \ cdots + (- 1) ^ {t} {\ binom {t} {t}}.}

1 = (t 1) – (t 2) + ⋯ + (- 1) t + 1 (tt), {\ displaystyle 1 = {\ binom {t} {1}} – {\ binom {t} {2}} + \ cdots + (- 1) ^ {t + 1} {\ binom {t} {t}},}

и поэтому выбранный элемент учитывается только один раз правой части уравнения (1).

Алгебраическое доказательство

Алгебраическое доказательство может быть получено с использованием индикаторных функций (также известных как типические функции). Индикаторная функция подмножества S множество X является функцией

{1 S: X → {0, 1} 1 S (x) = {1 x ∈ S 0 x ∉ S {\ displaystyle {\ begin {case} \ mathbf {1 } _ {S}: X \ to \ {0,1 \} \\\ mathbf {1} _ {S} (x) = {\ begin {cases} 1 x \ in S \\ 0 x \ notin S \ end {case}} \ end {ases}}

1 A ⋅ 1 B = 1 A ∩ B. {\ displaystyle \ mathbf {1} _ {A} \ cdot \ mathbf {1 } _ {B} = \ mathbf {1} _ {A \ cap B}.}

для индикаторных функций, где:

AI = ⋂ i ∈ IA i. {\ displaystyle A_ {I} = \ bigcap _ {i \ in I} A_ {i}.}

(1 A – 1 A 1) (1 A – 1 A 2) ⋯ (1 A – 1 A n), {\ displaystyle \ left (\ mathbf {1} _ {A} – \ mathbf {1} _ {A_ {1}} \ right) \ left (\ mathbf {1} _ {A} – \ mathbf {1} _ {A_ {2}} \ right) \ cdots \ left (\ mathbf {1} _ {A} – \ mathbf {1} _ {A_ {n}} \ right),}

тождественно равенство нулю, потому что: если x не входит в A, то все множители равны 0 – 0 = 0; в противном случае, если x принадлежит некоторому A m, то соответствующий множитель m равен 1 – 1 = 0. Разложив произведение в левой части, получаем уравнение (∗).

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

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

Случай двух множеств

Например, в случае двух множеств формула включений-исключений имеет вид:

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

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

Диаграмма Венна, показывающая объединение множеств A и B все, что не выделено белым

В комбинаторика, ветвь математики, принцип включения-исключения – это метод определения, который обобщает методы определения количества элементов в объединение двух конечных множеств ; символически выражается как

| A ∪ B | = | А | + | B | – | A ∩ B |, {\ displaystyle | A \ чашка B | = | А | + | B | – | A \ cap B |,}

Принцип более четко виден в случае трех наборов, которые для наборов A, B и C задаются как

| A ∪ B ∪ C | = | А | + | B | + | C | – | A ∩ B | – | A ∩ C | – | B ∩ C | + | A ∩ B ∩ C |. {\ Displaystyle | A \ чашка B \ чашка C | = | А | + | B | + | C | – | A \ cap B | – | A \ cap C | – | B \ cap C | + | A \ cap B \ cap C |.}

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

Включение-исключение, проиллюстрированное диаграмма Венмой для трех наборов

Обобщение результатов этих примеров дает принцип-исключение. Чтобы найти мощность объединения n множеств:

1. Включите мощности множеств.
2. Исключите мощности попарных пересечений.
3. Включите мощности тройных пересечений.
4. Исключить мощность четырехкратных пересечений.
5. Включения мощности пятикратных пересечений.
6. Продолжать до тех пор, пока мощность кортежа из мудрого пересечения включается (если нечетно) или исключается (n четно).

Название происходит от идеи, основан на чрезмерном включении, за которым следует компенсирующее исключение. Эта концепция приписывается Аврааму де Муавру (1718 г.); но сначала он появляется в статье Даниэля да Силва (1854), а затем в статье Дж. Дж. Сильвестр (1883). Иногда принцип определяется как формула Да Силвы или Сильвестра из-за этих публикаций. Этот принцип является примером метода сита, широко используемого в теории чисел и иногда называемого формулой сита, хотя Лежандр уже использует подобное устройство в контексте сита в 1808 году.

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

«Одним из наиболее полезных принципов перечисления в дискретной вероятности и комбинаторной теории знаменитый принцип включения-исключения. При умелом применении этот принцип дает решение многих комбинаторных проблем. “

Утверждение формы

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

Это может компактно записать как

| ⋃ i = 1 n A i | = ∑ k = 1 n (- 1) k + 1 (∑ 1 ⩽ i 1 < ⋯ < i k ⩽ n | A i 1 ∩ ⋯ ∩ A i k |) {\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}|a_{i_{1}}\cap="" \cdots="" \cap="" a_{i_{k}}|\right)}<img alt="{\ displaystyle \ left | \ bigcup _ {i = 1} ^ {n} A_ {i} \ right | = \ sum _ {k = 1} ^ {n} (- 1) ^ {k + 1} \ left (\ sum _ {1 \ leqslant i_ {1} <\ cdots

| ⋃ i = 1 n A i | = ∑ ∅ ≠ J ⊆ {1,…, n} (- 1) | J | + 1 | ⋂ J ∈ JA J |. {\ Displaystyle \ left | \ bigcup _ {i = 1} ^ {n} A_ {i} \ right | = \ sum _ {\ emptyset \ neq J \ substeq \ {1, \ ldots, n \}} (- 1) ^ {| J | +1} \ left | \ bigcap _ {j \ in J} A_ {j} \ right |.}

| ⋂ i = 1 n A i ¯ | = | S – ⋃ i = 1 n A i | = | S | – ∑ i = 1 n | A i | + ∑ 1 ⩽ i < j ⩽ n | A i ∩ A j | − ⋯ + ( − 1) n | A 1 ∩ ⋯ ∩ A n |. {\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|a_{i}\cap="" a_{j}|-\cdots="" +(-1)^{n}|a_{1}\cap="" \cdots="" \cap="" a_{n}|.}<img alt="{\ displaystyle \ left | \ bigcap _ {i = 1} ^ {n} {\ bar {A_ {i}}} \ right | = \ left | S- \ bigcup _ {i = 1} ^ {n} A_ {i} \ right | = | S | – \ sum _ {i = 1} ^ {n} | A_ {i} | + \ sum _ {1 \ leqslant i

Обратите внимание, что если вы учитываете только первые m <n sums="" on="" the="" right="" (in="" general="" form="" of="" principle),="" then="" you="" will="" get="" an="" overestimate="" if="" m="" is="" odd="" and="" underestimate="" even.

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

На этой странице мы собрали примеры решения учебных задач на применение принципа включений-исключений в комбинаторных задачах по теории вероятностей или дискретной математике.

Лучшее спасибо – порекомендовать эту страницу

Приложения

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

Подсчет сбоев

Впервые проблема подсчета количества психических расстройств в одной из первых книг о азартных играх: Essai d’analyse sur les jeux de risk, написанной П.Р. де Монмором (1678-1719) и известной как либо «проблема Монморта», либо судя по названию, которое он дал ей, «проблема отношений». Проблема также известна как проблема топора.

Количество неисправностей известно также как субфактор числа n, записывается! N. Отсюда следует, что если всем биекциям присваивается одинаковая вероятность, то вероятность того, что случайная биекция является расстройством, быстро приближается к 1 / e по мере роста.

Подсчет пересечений

⋂ я = 1 NA я = ⋃ я = 1 N A я ¯ ¯ {\ displaystyle \ bigcap _ {i = 1} ^ {n} A_ {i} = {\ overline {\ bigcup _ {i = 1} ^ {n} {\ overline {A_ {i}}}}}}

тем самым превращая проблему поиска пересечения в проблему поиска объединения.

Раскраска графа

Принцип исключения включения формирует основу алгоритмов для ряда проблем NP-жесткого разбиения графа, таких как раскраска графа.

Хорошо известный принцип применения в построении хроматического полинома графа.

Совершенное сопоставление двудольного графа

Количество идеального сопоставления из двудольный граф может быть вычислен по принципу.

Число онт-функций

∑ j = 0 n (nj) (- 1) j (n – j) k. {\ displaystyle \ sum _ {j = 0} ^ {n} {\ binom {n} {j}} (- 1) ^ {j} (nj) ^ {k}.}

Перестановки с запрещенными позициями

В примере 12 = 2 (3!) Перестановки со своимством P 1, 6 = 3! перестановки со своимством P 2 и никакие перестановки имеют свойства P 3 или P 4, поскольку для этих двух элементов нет ограничений. Таким образом, количество перестановок, удовлетворяющих ограничений, равно:

4! – (12 + 6 + 0 + 0) + (4) = 24 – 18 + 4 = 10.

Последние 4 в этом вычислении – это количество перестановок, обладающих обоими свойствами P 1 и P 2. Других ненулевых вкладов в формулу нет.

Числа Стирлинга второго рода

S (n, k) = 1 k! ∑ т знак равно 0 к (- 1) т (к т) (к – т) п. {\ displaystyle S (n, k) = {\ frac {1} {k!}} \ sum _ {t = 0} ^ {k} (- 1) ^ {t} {\ binom {k} {t} } (kt) ^ {n}.}

Полиномы ладьи

Иногда бывает удобно вычислить наивысший коэффициент ладейного многочлена через коэффициенты ладейного многочлена дополнительной доски. Без ограничения общности можно считать, что n ≤ m, поэтому этот коэффициент равенства r n (B). Количество способов link не атакующих ладей на полной «шахматной доске» размером n × m (независимо от того, находятся ли ладьи в клетках доски B) дается с помощью факториала падения :

(т) п знак равно т (м – 1) (т – 2) ⋯ (т – п + 1). {\ displaystyle (m) _ {n} = m (m-1) (m-2) \ cdots (mn + 1).}

Если P я быть своим, присвоение n не – у атакующих ладей на полной доске в столбце i находится ладья, которая не находится в клетке доски B, то по принципу включения-исключения имеем:

rn (B) = ∑ t = 0 n (- 1) t (m – t) n – trt (B ′). {\ displaystyle r_ {n} (B) = \ sum _ {t = 0} ^ {n} (- 1) ^ {t} (mt) _ {nt} r_ {t} (B ‘).}

Функция фи Эйлера

n = p 1 a 1 p 2 a 2 ⋯ prar. {\ displaystyle n = p_ {1} ^ {a_ {1}} p_ {2} ^ {a_ {2}} \ cdots p_ {r} ^ {a_ {r}}.}

φ (n) = n – ∑ i = 1 rnpi + ∑ 1 ⩽ i < j ⩽ r n p i p j − ⋯ = n ∏ i = 1 r ( 1 − 1 p i). {\displaystyle \varphi (n)=n-\sum _{i=1}^{r}{\frac {n}{p_{i}}}+\sum _{1\leqslant i<j\leqslant r}{\frac="" {n}{p_{i}p_{j}}}-\cdots="n\prod" _{i="1}^{r}\left(1-{\frac" {1}{p_{i}}}\right).}<img alt="{\ displaystyle \ varphi (n) = n- \ sum _ {i = 1} ^ {r} {\ frac {n} {p_ {i}}} + \ sum _ {1 \ leqslant i

Особый случай

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

AJ: = ⋂ j ∈ JA j {\ displaystyle A_ {J}: = \ bigcap _ {j \ in J} A_ {j}}

| ⋃ i = 1 n A i | Знак равно ∑ К знак равно 1 N (- 1) К – 1 (N К) α К. {\ displaystyle \ left | \ bigcup _ {i = 1} ^ {n} A_ {i} \ right | = \ sum _ {k = 1} ^ {n} (- 1) ^ {k-1} {\ binom {n} {k}} \ alpha _ {k}.}

Или в дополнительной форме, где универсальное множество S имеет мощность α 0,

| S ∖ ⋃ i = 1 n A i | = ∑ К знак равно 0 N (- 1) К (N К) α К. {\ displaystyle \ left | S \ setminus \ bigcup _ {i = 1} ^ {n} A_ {i} \ right | = \ sum _ {k = 0} ^ {n} (- 1) ^ {k} {\ binom {n} {k}} \ alpha _ {k}.}

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

История

Впервые формулу включений-исключений опубликовал португальский математик Даниэль да Сильва (англ.) в 1854 году . Об этом говорит сайт https://intellect.icu . Но еще в 1713 году Николай Бернулли использовал этот метод для решения задачи Монмора , известной как задача о встречах (фр. Le problème des rencontres) , частным случаем которой является задача о беспорядках. Также формулу включений-исключений связывают с именами французского математика Абрахама де Муавра и английского математика Джозефа Сильвестра .

Доказательство принципа включений-исключений

Для доказательства удобно пользоваться математической формулировкой в терминах теории множеств:

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

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

• в тех слагаемых, у которых раз, со знаком плюс;
• в тех слагаемых, у которых ;
• в тех слагаемых, у которых раз, со знаком плюс;
• в тех слагаемых, у которых ;
• в тех слагаемых, у которых учтется ноль раз.

Таким образом, нам надо посчитать такую сумму биномиальных коэффициентов:

Проще всего посчитать эту сумму, сравнив ее с разложением в бином Ньютона выражения :

Видно, что при , что и требовалось доказать.

Доказательство

Существует несколько доказательств формулы включений-исключений.

Доказательство по индукции

Формулу включений-исключений можно доказать по индукции .

При формула включений-исключений тривиальна:

Пусть формула верна для .

Пусть каждый элемент множества :

Теперь применим формулу для свойств :

Наконец, применим формулу для одного свойства :

Комбинируя выписанные три формулы, получим формулу включений-исключений для . Что и требовалось доказать. ■

Рассмотрим произвольный элемент .

Если элемент ).

Пусть элемент в правую часть равен

При числа сочетаний равны нулю. Оставшаяся сумма в силу биномиальной теоремы равна

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

Доказательство через индикаторные функции

Индикаторная функция их дополнений равна

а индикаторная функция пересечения дополнений:

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

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

получим формулировку принципа включений-исключений в терминах мощностей множеств (или в терминах свойств). ■

Формулировка

Формулу включений-исключений можно сформулировать в разных формах.

В терминах множеств

Пусть — конечные множества. Формула включений-исключений утверждает:

При получаем формулу для двух множеств, приведенную выше.

В терминах свойств

Принцип включений-исключений часто приводят в следующей альтернативной формулировке . Пусть дано конечное множество . Тогда имеет место формула:

Формулировка принципа включений-исключений в терминах множеств эквивалентна формулировке в терминах свойств. Действительно, если множества ), и формулу включений-исключений можно переписать так:

Если теперь вместо «элемент », то мы получим формулировку принципа включений-исключений в терминах свойств, и наоборот.

Обозначим через .Тогда формулу включений-исключений можно переписать в следующей замкнутой форме (англ.)

Решебник по терверу и комбинаторике

Если решения нужны срочно и почти даром? Ищите в решебнике по теории вероятностей:

Применение

Задача о беспорядках

Задача о беспорядках

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

Пусть беспорядков:

Это соотношение можно преобразовать к виду

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

Вычисление функции Эйлера

Другой пример применения формулы включений-исключений — нахождение явного выражения для функции Эйлера .

Пусть каноническое разложение числа на простые множители имеет вид

По формуле включений-исключений находим

Эта формула преобразуется к виду:

Принцип включений-исключений

Принцип включений-исключений — это важный комбинаторный прием, позволяющий подсчитывать размер каких-либо множеств, или вычислять вероятность сложных событий.

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

Словесная формулировка

Принцип включений-исключений выглядит следующим образом:

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

Формулировка в терминах множеств

В математической форме приведенная выше словесная формулировка выглядит следующим образом:

Ее можно записать более компактно, через сумму по подмножествам. Обозначим через . Тогда принцип включений-исключений принимает вид:

Эту формулу приписывают Муавру (Abraham de Moivre).

Формулировка с помощью диаграмм Венна

Пусть на диаграмме отмечены три фигуры :

Тогда площадь объединения :

Аналогичным образом это обобщается и на объединение фигур.

Формулировка в терминах теории вероятностей

Если — их вероятности, то вероятность их объединения (т.е. того, что произойдет хотя бы одно из этих событий) равна:

Эту сумму также можно записать в виде суммы по подмножествам множества :

Ссылки

• Алленби, RBJT; Сломсон, Алан (2010), Как считать: Введение в комбинаторику, дискретную математику и ее приложения (2-е изд.), CRC Press, стр. 51–60, ISBN 9781420082609
• Björklund, A.; Husfeldt, T.; Койвисто, М. (2009), «Установить разбиение через включение – исключение», SIAM Journal on Computing, 39(2): 546–563, doi : 10.1137 / 070683933
• Бруальди, Ричард А. (2010), Введение в комбинаторику (5-е изд.), Прентис-Холл, ISBN 9780136020400
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, Методы, алгоритмы, Cambridge University Press, ISBN 0-521-45761-0
• Фернандес, Роберто; Фрёлих, Юрг ; Алан Д., Сокал (1992), Случайные блуждания, критические явления и тривиальность в квантовой теории поля, тексты и монографии по физике, Берлин: Springer-Verlag, стр. Xviii + 444, ISBN 3-540-54358-9, MR 1219313, Zbl 0761.60061
• Graham, RL; Grötschel, M. ; Ловас, Л. (1995), Справочник по комбинаторике (том-2), MIT Press – Северная Голландия, ISBN 9780262071710
• Гросс, Джонатан Л. (2008), Комбинаторные методы с Компьютерные приложения, Chapman Hall / CRC, ISBN 9781584887430
• , Энциклопедия математики, EMS Press, 2001 [1994]
• Мазур, Дэвид Р. (2010), Комбинаторика: экскурсия, Математическая ассоциация Америки, ISBN 9780883857625
• Робертс, Фред С.; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, ISBN 9781420099829
• Стэнли, Ричард П. (1986), Перечислительная комбинаторика, том I, Wadsworth Brooks / Коул, ISBN 0534065465
• ван Линт, JH; Уилсон, Р. (1992), Курс комбинаторики, Cambridge University Press, ISBN 0521422604

Примеры

Подсчет целых чисел

В качестве примера использования принципа –Exclusion, рассмотрите вопрос:

Сколько целых чисел в {1,…, 100} не делятся на 2, 3 или 5?

100 – (50 + 33 + 20) + (16 + 10 + 6) – 3 = 26.

Нарушения подсчета

Более сложный пример – следующий.

Предположим, есть колода из n карт, пронумерованных от 1 до n. Предположим, карта с номером находится в правильном положении, если это m-я карта в колоде. Сколько способов, W, можно перетасовать карты, если хотя бы одна карта находится в правильном положении?

Начните определения набора A m, который представляет собой все правильные порядки карт с м-й картой. Тогда количество заказов, W, с хотя бы одной картой, находящейся в правильном положении, m, составляет

W = | ⋃ m = 1 n A m |. {\ displaystyle W = \ left | \ bigcup _ {m = 1} ^ {n} A_ {m} \ right |.}

Примените принцип – включение исключение,

W = ∑ m 1 = 1 п | А м 1 | – ∑ 1 ⩽ m 1 < m 2 ⩽ n | A m 1 ∩ A m 2 | + ⋯ + ( − 1) p − 1 ∑ 1 ⩽ m 1 < ⋯ < m p ⩽ n | A m 1 ∩ ⋯ ∩ A m p | + ⋯ {\displaystyle W=\sum _{m_{1}=1}^{n}|A_{m_{1}}|-\sum _{1\leqslant m_{1}<m_{2}\leqslant n}|a_{m_{1}}\cap="" a_{m_{2}}|+\cdots="" +(-1)^{p-1}\sum="" _{1\leqslant="" m_{1}<\cdots="" <m_{p}\leqslant="" \cdots="" \cap="" a_{m_{p}}|+\cdots="" }<img alt="{\ displaystyle W = \ sum _ {m_ {1} = 1} ^ {n} | A_ {m_ {1}} | – \ sum _ {1 \ leqslant m_ {1} <m_ {2} \ leqslant n} | A_ {m_ {1}} \ cap A_ {m_ {2}} | + \ cdots + (- 1) ^ {p-1} \ sum _ {1 \ leqslant m_ {1} <\ cdots

W = (n 1) | A 1 | – (п 2) | A 1 ∩ A 2 | + ⋯ + (- 1) p – 1 (n p) | A 1 ∩ ⋯ ∩ A p | + ⋯ {\ displaystyle W = {n \ choose 1} | A_ {1} | – {п \ выбрать 2} | A_ {1} \ cap A_ {2} | + \ cdots + (- 1) ^ {p- 1} {n \ choose p} | A_ {1} \ cap \ cdots \ cap A_ {p} | + \ cdots}

W = (n 1) (n – 1)! – (n 2) (n – 2)! + ⋯ + (- 1) п – 1 (п п) (п – п)! + ⋯ знак равно ∑ п знак равно 1 N (- 1) п – 1 (п п) (п – п)! Знак равно ∑ п знак равно 1 N (- 1) п – 1 п! п! (п – р)! (п – р)! Знак равно ∑ п знак равно 1 N (- 1) п – 1 п! п! {\ displaystyle {\ begin {align} W = {n \ choose 1} (n-1)! – {п \ выбрать 2} (п-2)! + \ cdots + (- 1) ^ {p-1} {n \ choose p} (np)! + \ cdots \\ = \ sum _ {p = 1} ^ {n} (- 1) ^ {p-1} {n \ choose p} (np)! \ \ = \ sum _ {p = 1} ^ {n} (- 1) ^ {p-1} {\ frac {n!} {p! (np)!}} (np)! \\ = \ sum _ {p = 1} ^ {n} (- 1) ^ {p-1} {\ frac {n!} {p!}} \ end {align}}}

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

Q = 1 – W n! Знак равно ∑ п знак равно 0 N (- 1) п п!, {\ displaystyle Q = 1 – {\ frac {W} {n!}} = \ sum _ {p = 0} ^ {n} {\ frac {(-1) ^ {p}} {p!}},}

усечение до n + 1 членов разложения Тейлора числа e. Таким образом, вероятность угадать порядок перетасованной колоды карт и ошибиться по каждой карте составляет примерно e или 37%.

Вау!! 😲 Ты еще не читал? Это зря!

• Формула Грассмана
• операции над множествами
• множества

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

В вероятности

P (A 1 ∪ A 2) = P (A 1) + P (A 2) – P (A 1 ∩ A 2), {\ displaystyle \ mathbb {P} (A_ {1 } \ cup A_ {2}) = \ mathbb {P} (A_ {1}) + \ mathbb {P} (A_ {2}) – \ mathbb {P} (A_ {1} \ cap A_ {2}),}

для n = 3

P (A 1 ∪ A 2 ∪ A 3) = P (A 1) + P (A 2) + P (A 3) – P (A 1 ∩ A 2) – п (A 1 ∩ A 3) – п (A 2 ∩ A 3) + P (A 1 ∩ A 2 ∩ A 3) {\ displaystyle \ mathbb {P} (A_ {1} \ чашка A_ {2} \ чашка A_ {3}) = \ mathbb {P} (A_ {1}) + \ mathbb {P} (A_ {2}) + \ mathbb {P} (A_ {3}) – \ mathbb {P} (A_ {1} \ cap A_ {2}) – \ mathbb {P} (A_ {1} \ cap A_ {3}) – \ mathbb {P} (A_ {2} \ cap A_ {3}) + \ mathbb { P} (A_ {1} \ cap A_ {2} \ cap A_ {3})}

и в целом

P (⋃ i = 1 n A i) = ∑ i = 1 n P (A i) – ∑ я < j P ( A i ∩ A j) + ∑ i < j < k P ( A i ∩ A j ∩ A k) + ⋯ + ( − 1) n − 1 ∑ i <… < n P ( ⋂ i = 1 n A i), {\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i<j}\mathbb {p}="" (a_{i}\cap="" a_{j})+\sum="" _{i<j<k}\mathbb="" a_{j}\cap="" a_{k})+\cdots="" +(-1)^{n-1}\sum="" _{i<…<n}\mathbb="" \left(\bigcap="" _{i="1}^{n}A_{i}\right),}<img alt="{\ displaystyle \ mathbb {P} \ left (\ bigcup _ {i = 1} ^ {n} A_ {i} \ right) = \ sum _ {i = 1} ^ {n} \ mathbb {P} (A_ {i}) – \ sum _ {i <j} \ mathbb {P} (A_ {i} \ cap A_ {j}) + \ sum _ {i <j <k} \ mathbb {P} (A_ {i} \ cap A_ {j} \ cap A_ {k}) + \ cdots + (- 1) ^ {n-1} \ sum _ {i <…

, которое в замкнутой форме может быть записано как

P (⋃ i = 1 n A i) = ∑ k = 1 n ((- 1) k – 1 ∑ I ⊆ {1,…, n} | Я | знак равно К П (AI)), {\ Displaystyle \ mathbb {P} \ left (\ bigcup _ {i = 1} ^ {n} A_ {i} \ right) = \ sum _ {k = 1} ^ { n} \ left ((- 1) ^ {k-1} \ sum _ {I \ substeq \ {1, \ ldots, n \} \ atop | I | = k} \ mathbb {P} (A_ {I}) \ right),}

AI: = ⋂ i ∈ IA i {\ displaystyle A_ {I }: = \ bigcap _ {i \ in I} A_ {i}}

обозначает пересечение всех этих A i индексом в I.

Согласно неравенства Бонферрони, первая сумма элементов в формуле по очереди верхней и нижней границей для LHS. Это можно использовать в случаях, когда полная формула слишком громоздка.

Частный случай

ak = P (AI) для любого I ⊂ {1,…, n} с | Я | = к, {\ displaystyle a_ {k} = \ mathbb {P} (A_ {I}) {\ text {для каждого}} I \ subset \ {1, \ ldots, n \} {\ text {with}} | Я | = k,}

тогда приведенная выше формула упрощается до

P (⋃ i = 1 n A i) = ∑ k = 1 n (- 1) k – 1 (nk) ak {\ displaystyle \ mathbb {P } \ left (\ bigcup _ {i = 1} ^ {n} A_ {i} \ right) = \ sum _ {k = 1} ^ {n} (- 1) ^ {k-1} {\ binom { n} {k}} a_ {k}}

P (⋃ i = 1 n A i) = 1 – (1 – p) n. {\ displaystyle \ mathbb {P} \ left (\ bigcup _ {i = 1} ^ {n} A_ {i} \ right) = 1- (1-p) ^ {n}.}

Другие формы

Иногда принцип выражается в форме, в которой сказано, что если

g (A) = ∑ S ⊆ A f (S) {\ displaystyle g (A) = \ sum _ {S \ substeq A} f (S)}

f (A) = ∑ S ⊆ A (- 1) | А | – | S | g (S) (∗ ∗) {\ Displaystyle f (A) = \ sum _ {S \ substeq A} (- 1) ^ {| А | – | S |} g (S) \ qquad (**)}

Комбинаторная и вероятностная версия принципа включения-исключения являются примерами (**).

Для обобщения полной версии формулы обращения Мёбиуса, (**) должна быть обобщена на мультимножества. Для мультимножеств вместо наборов (**) становится

f (A) = ∑ S ⊆ A μ (A – S) g (S) (∗ ∗ ∗) {\ displaystyle f (A) = \ sum _ {S \ substeq A} \ mu (AS) g (S) \ qquad (***)}

• μ (S) = 1, если S – множество (т. Е. Мультимножество без двойных элементов) четных мощности.
• μ (S) = −1, если S – множество (т. Е. Мультимножество без двойных элементов) нечетной мощности.
• μ (S) = 0, если S является правильным мультимножеством (т. Е. S имеет двойные элементы).

Применения при решении задач

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

Сначала мы рассмотрим три простые задачи “на бумажке”, иллюстрирующие применение принципа, затем рассмотрим более практические задачи, которые трудно решить без использования принципа включений-исключений.

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

Простая задачка о перестановках

Сколько есть перестановок чисел от ?

Посчитаем число “плохих” перестановок, т.е. таких, у которых первый элемент .

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

Отнимая это число от общего числа перестановок , мы получим ответ.

Простая задачка о (0,1,2)-последовательностях

Сколько существует последовательностей длины , причем каждое число встречается хотя бы раз?

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

Размеры каждого из (поскольку доступных цифр вообще не остается).

Вспоминая, что мы решали обратную задачу, получаем итоговый ответ:

Количество целочисленных решений уравнения

где все ).

Требуется посчитать число решений этого уравнения.

Забудем сначала про ограничение местам:

Посчитаем теперь по формуле включений-исключений число “плохих” решений, т.е. таких решений уравнения, в которых один или более .

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

Аналогично, мощность пересечения двух множеств равна числу:

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

Объединяя все это в формулу включений-исключений и учитывая, что мы решали обратную задачу, окончательно получаем ответ:

Количество взаимно простых чисел в заданном отрезке

Пусть даны числа .

Сразу перейдем к обратной задаче — посчитаем количество не взаимно простых чисел.

Рассмотрим все простые делители числа ).

Сколько чисел в отрезке ? Их количество равно:

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

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

Итоговая реализация для подсчета количества взаимно простых чисел:

Асимптотика решения составляет .

Количество чисел в заданном отрезке, кратных хотя бы одному из заданных чисел

Алгоритм решения практически совпадает с предыдущей задачей — делаем формулу включений-исключений над числами (иными словами, делящихся на их наименьшее общее кратное).

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

Количество строк, удовлетворяющих заданному числу паттернов

Дано паттернам.

Заметим вначале, что мы можем легко посчитать число строк, удовлетворяющих сразу всем указанным паттернам. Для этого надо просто “пересечь” эти паттерны: посмотреть на первый символ (во всех ли паттернах на первой позиции стоит вопрос, или не во всех — тогда первый символ определен однозначно), на второй символ, и т.д.

Научимся теперь решать первый вариант задачи: когда искомые строки должны удовлетворять ровно паттернам.

Для этого переберем и зафксируем конкретное подмножество , и либо прибавляем к текущему ответу, либо отнимаем от него количество строк, подходящих под текущее множество:

Если мы просуммируем , то получим ответ:

Однако тем самым мы получили решение за время порядка .

Решение можно ускорить, заметив, что в разных .

Перевернем формулу включений-исключений и будем вести суммирование по :

Решение получилось с асимптотикой .

Перейдем теперь ко второму варианту задачи: когда искомые строки должны удовлетворять как минимум паттернам.

Понятно, мы можем просто воспользоваться решением первого варианта задачи и просуммировать ответы от .

Таким образом, в итоговой формуле перед будет стоять другой коэффициент: не один биномиальный коэффициент с каким-то знаком, а их сумма:

Применяя ее здесь, получаем, что вся эта сумма биномиальных коэффициентов сворачивается в:

Таким образом, для этого варианта задачи мы также получили решение с асимптотикой :

Количество путей

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

Предполагаем, что размеры ).

Для решения сразу в целях удобства отсортируем препятствия в том порядке, в каком мы можем их обойти: т.е., например, по координате .

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

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

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

Однако это снова будет неполиномиальное решение — за асимптотику . Покажем, как получить полиномиальное решение.

Решать будем динамическим программированием: научимся вычислять числа точки, поскольку к препятствиям добавляются стартовая и конечная клетки.

Если мы на секунду забудем про все препятствия и просто посчитаем число путей из клетки

Таким образом, значение .

Число взаимно простых четверок

Дано . Требуется посчитать количество способов выбрать из них четыре числа так, что их совокупный наибольший общий делитель равен единице.

Будем решать обратную задачу — посчитаем число “плохих” четверок, т.е. таких четверок, в которых все числа делятся на число .

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

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

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

Число гармонических троек

Дано число , что они являются гармоническими тройками, т.е.:

Во-первых, сразу перейдем к обратной задаче — т.е. посчитаем число негармонических троек.

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

Таким образом, количество негармонических троек равно сумме по всем числам от произведений количества взаимно простых с текущим числом чисел на количество не взаимно простых чисел.

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

Поэтому нам понадобится более быстрое решение, которое подсчитывает ответы для всех чисел из отрезка сразу.

Для этого можно реализовать такую модификацию решета Эратосфена:

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

  Для этого нам надо завести массивы или нет.

  После этого во время решета Эратосфена при обработке очередного простого числа мы пройдемся по всем числам, кратным текущему числу, и увеличим .

• Во-вторых, нам надо посчитать ответ для всех чисел от — количество чисел, не взаимно простых с данным.

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

  Итак, пусть у нас есть число нечетна, то надо прибавлять, иначе вычитать.

Асимптотика такого решения составляет итераций вложенного цикла.

Число перестановок без неподвижных точек

Докажем, что число перестановок длины без неподвижных точек равно следующему числу:

и приблизительно равно числу:

(более того, если округлить это выражение к ближайшему целому — то получится в точности число перестановок без неподвижных точек)

Обозначим через ).

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

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

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

Тогда число перестановок без неподвижных точек равно:

Упрощая это выражение, получаем точное и приблизительное выражения для количества перестановок без неподвижных точек:

(поскольку сумма в скобках — это первые )

В заключение стоит отметить, что аналогичным образом решается задача, когда требуется, чтобы неподвижных точек не было среди m первых элементов перестановок (а не среди всех, как мы только что решали). Формула получится такая, как приведенная выше точная формула, только в ней сумма будет идти до k, а не до n.

Вариации и обобщения

Принцип включения-исключения для вероятностей

<img alt="
\mathcal{P} \biggl( \bigcup_{i=1}^n A_i \biggr) = \sum_{i} \mathcal{P}(A_i) – \sum_{i<j} \mathcal{P}(A_i \cap A_j) + \sum_{i<j

Эта формула выражает принцип включений-исключений для вероятностей. Ее можно получить из принципа включений-исключений в форме индикаторных функций:

Пусть , получим формулу включения-исключения для вероятностей.

Принцип включений-исключений в пространствах с мерой

Пусть имеет место формула включений-исключений:

Очевидно, принцип включений-исключений для вероятностей и для мощностей конечных множеств являются частными случаями этой формулы. В первом случае мерой является, естественно, вероятностная мера в соответствующем вероятностном пространстве: .

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

Пусть , и получим формулу включений-исключений для меры.

Тождество максимумов и минимумов

Формула включений-исключений может рассматриваться как частный случай тождества максимумов и минимумов:

<img alt="
\max(a_1, \ldots , a_n) = \sum_{i} a_i – \sum_{i

Это соотношение справедливо для произвольных чисел , то получим соотношение для индикаторных функций множеств:

Обращение Мебиуса

Пусть следующим соотношением:

Тогда имеет место следующая формула обращения :

Это утверждение является частным случаем общей формулы обращения Мебиуса для алгебры инцидентности (англ.) совокупности .

Покажем, как из этой формулы следует принцип включения-исключения для конечных множеств. Пусть дано семейство подмножеств . Математически это можно записать так:

Тогда функция , определенная формулой

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

Заметим далее, что — количество элементов, не обладающих ни одним из свойств:

С учетом сделанных замечаний запишем формулу обращения Мебиуса:

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

Разбавленный принцип включения-исключения

Во многих случаях, когда принцип может давать точную формулу (в частности, подсчет простые числа с использованием решета Эратосфена ), возникающая формула не предлагает полезного содержания, потому что количество членов в ней чрезмерно. Если каждый член в отдельности можно оценить точно, накопление ошибок может означать, что формула включения-исключения не применима напрямую. В теории чисел эта проблема была рассмотрена Вигго Бруном. После медленного старта его идеи были подхвачены другими, и было разработано большое количество ситовых методов. Они, например, могут попытаться найти верхние границы для “просеянных” множеств, а не точную формулу.

1 A 1 ∪ ⋯ ∪ A n ≥ ∑ j = 1 k (- 1) j – 1 ∑ 1 ≤ i 1 < ⋯ < i j ≤ n p i 1 … p i j 1 A i 1 ∩ ⋯ ∩ A i j. {\displaystyle 1_{A_{1}\cup \cdots \cup A_{n}}\geq \sum _{j=1}^{k}(-1)^{j-1}\sum _{1\leq i_{1}<\cdots <i_{j}\leq n}p_{i_{1}}\dots="" p_{i_{j}}\,1_{a_{i_{1}}\cap="" \cdots="" \cap="" a_{i_{j}}}.}<img alt="{\ displaystyle 1_ {A_ {1} \ cup \ cdots \ чашка A_ {n} } \ geq \ sum _ {j = 1} ^ {k} (- 1) ^ {j-1} \ sum _ {1 \ leq i_ {1} <\ cdots

Примеры решенных задач

Задача 1. Формула включений и исключений (для трех множеств). Известно, что свойством А обладает n объектов, В — m объектов, С — с объектов, АВ — р объектов, АС — g объектов, ВС — r объектов, АВС — q объектов. Сколько всего объектов?

Задача 2. Из 100 человек студентов, сдавших сессию, 48 человек сдали экономику, 42 студента – математику и 37 человек – логику. По экономике или математике сдали экзамен 76 человек, по экономике или логике также 76 человек, а по математике или логике – 66 человек. Сколько человек сдали хотя бы один экзамен, если все три предмета сдали 5 человек? Сколько человек не сдали ни одного экзамена? Сколько человек сдали только один экзамен по логике?

Задача 3. При обследовании читательских вкусов студентов оказалось, что 60 % студентов читают журнал А, 50 % – журнал В, 50 % – журнал С, 30 % – журналы А и В, 20 % – журналы В и С, 40 % – журналы А и С, 10 % – журналы А, В и С. Выяснить, сколько процентов студентов:
1) не читает ни одного из журналов;
2) читает в точности два журнала;
3) читает не менее двух журналов.

Задача 4. На одной из кафедр университета работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро – немецкий, шестеро – французский, пятеро знают английский и немецкий, четверо – английский и французский, трое – немецкий и французский. Выяснить:
1) сколько человек знают все три языка;
2) сколько человек знают ровно два языка;
3) сколько человек знают только английский язык.

Задача 5. Из 100 туристов, выехавших в заграничное путешествие, 10 человек не знают ни немецкого, ни французского языков, 76 человек знают немецкий и 83 – французский. Сколько туристов знают оба эти языка?

Задача 6. В отряде из 40 ребят 30 умеют плавать; 27 умеют играть в шахматы; 5 не умеют ни плавать, ни играть в шахматы. Определить количество ребят, умеющих плавать и играть в шахматы.

Мы отлично умеем решать задачи по теории вероятностей

Обобщение

∑ J ⊆ [n] (- 1) | J | | A J |. {\ displaystyle \ sum _ {J \ substeq [n]} (- 1) ^ {| J |} | A_ {J} |.}

Если I – фиксированное подмножество набора индексов N, то число элементов, которые принадлежат A i для всех i в I и ни для каких других значений:

∑ I ⊆ J (- 1) | J | – | Я | | A J |. {\ displaystyle \ sum _ {I \ substeq J} (- 1) ^ {| J | – | I |} | A_ {J} |.}

B k = AI ∪ {k} для k ∈ N ∖ I. {\ displaystyle B_ {k} = A_ {I \ cup \ {k \}} { \ text {for}} k \ in N \ setminus I.}

∑ K ⊆ N ∖ I (- 1) | K | | B K |. {\ displaystyle \ sum _ {K \ substeq N \ setminus I} (- 1) ^ {| K |} | B_ {K} |.}

Соответствие K ↔ J = I ∪ K между подмножествами N \ I и подмножества N, содержит I, являются биекцией, и если J и K соответствуют по этой карте, то B K = A J, преобразовать, что результат действителен.

Примеры с подробным решением.

Задача 1. Из 100 школьников английский знают 42, немецкий — 30, французский — 28, английский и немецкий — 5, английский и французский — 10, немецкий и французский — 8, английский, немецкий и французский — 3 школьника. Сколько школьников не знают ни одного языка?

Решение. I способ.

Обозначим через А — множество школьников, знающих английский язык; N — множество школьников, знающих немецкий язык; F — множество школьников, знающих французский язык.

Тогда n(A) = 42, n(N) = 30, n(F) = 28, n(A ∩ N) = 5,

n(A ∩ F) = 10, n(N ∩ F) = 8, n(A ∩ N ∩ F) = 3.

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

n(A ∪ N ∪ F) = n(A) + n(N) + n(F) =

= n(A ∩ N) – n(A ∩ F) – n(N ∩ F) + n(A ∩ N ∩ F) =

= 42 + 30 + 28 – 5 – 10 – 8 + 3 = 80.

Следовательно, не знают ни одного иностранного языка:

100 – 80 = 20 школьников.

Эту же задачу можно решить с помощью диаграммы Эйлера-Венна (рис. 1).

Так как 3 языка знают 3 школьника, то английский и немецкий знают 5 – 3 = 2, английский и французский — 10 – 3 = 7,

немецкий и французский — 8 – 3 = 5 школьников.

Только английский знают 42 –(2 + 3 + 7) = 30,

только немецкий — 30 – (2 + 3 + 5) = 20,

только французский — 28 – (3 + 5 + 7) = 13 школьников.

Ни одного языка не знают 100 – (2 + 3 + 5 + 7 + 13 + 20 + 30) = 20 школьников.

Задача 2. Сколько двузначных чисел не делятся ни на 2, ни на 3, ни на 5, ни на 11?

Решение. Обозначим: А — множество двузначных чисел, делящихся на 2;

В — множество двузначных чисел, делящихся на 3;

С — множество двузначных чисел, делящихся на 5;

D — множество двузначных чисел, делящихся на 11.

n(A ∪ B ∪ C ∪ D) — количество двузначных чисел, делящихся хотя бы на одно из чисел 2; 3; 5; 11.

n(A ∪ B ∪ C ∪ D) = n(A) + n(B) + n(C) + n(D) –

– n(A ∩ B) – n(A ∩ C) – n(A ∩ D) – n(B ∩ C) –

– n(B ∩ D) – n(C ∩ D) + n(A ∩ B ∩ C) + n(A ∩ B ∩ D) +

+ n(A ∩ C ∩ D) + n(B ∩ C ∩ D) – n(A ∩ B ∩ C ∩ D).

n(A) = 45, n(B) = 30, n(C) = 18, n(D) = 9,

n(A ∩ B) = 15, n(A ∩ C) = 9, n(A ∩ D) = 4, n(B ∩ C) = 6,

n(B ∩ D) = 3, n(C ∩ D) = 1, n(A ∩ B ∩ C) = 3,

n(A ∩ B ∩ D) = 1, n(A ∩ C ∩ D) = n(B ∩ C ∩ D) = n(A ∩ B ∩ C ∩ D) = 0.

Итак, n(A ∪ B ∪ C ∪ D) = 45 + 30 +18 + 9 – 15 – 9 – 4 – 6 – 3 – 1 + 3 + 1 = 68.

Так как всего 90 двузначных чисел, то чисел, не делящихся ни на одно из заданных чисел:

90 – 68 = 22.

Задача 3. Известно, что из n учеников спортом увлекаются a учеников, программированием b, математикой c, спортом и программированием d, спортом и математикой e, программированием и математикой f , спортом, математикой и программированием g учеников. Сколько учеников увлекается только программированием? Сколько учеников увлекается только математикой? Сколько учеников ничем не увлекается?

Решение. Пусть A —множество учеников, которые увлекаются спортом,

B — программированием, С – математикой.