Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика

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

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

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

| A ∪ B | = | A | + | B | − | A ∩ B | . {displaystyle |Acup B|=|A|+|B|-|Acap B|.}

В сумме | A | + | B | {displaystyle |A|+|B|} элементы пересечения A ∩ B {displaystyle Acap B} учтены дважды, и чтобы компенсировать это мы вычитаем | A ∩ B | {displaystyle |Acap B|} из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.

Таким же образом и в случае n > 2 {displaystyle n>2} множеств процесс нахождения количества элементов объединения A 1 ∪ A 2 ∪ … ∪ A n {displaystyle A_{1}cup A_{2}cup ldots cup A_{n}} состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

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

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

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

Пусть A 1 , A 2 , … , A n {displaystyle A_{1},A_{2},ldots ,A_{n}} — конечные множества. Формула включений-исключений утверждает:

| ⋃ i = 1 n A i | = ∑ i | A i | − ∑ i < j | A i ∩ A j | + ∑ i < j < k | A i ∩ A j ∩ A k | − … + ( − 1 ) n − 1 | A 1 ∩ A 2 ∩ … ∩ A n | . {displaystyle {iggl |}igcup _{i=1}^{n}A_{i}{iggl |}=sum _{i}|A_{i}|-sum _{i<j}|A_{i}cap A_{j}|+sum _{i<j<k}|A_{i}cap A_{j}cap A_{k}|-ldots +(-1)^{n-1}|A_{1}cap A_{2}cap ldots cap A_{n}|.}

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

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

Принцип включений-исключений часто приводят в следующей альтернативной формулировке . Пусть дано конечное множество U {displaystyle U} , состоящее из N {displaystyle N} элементов, и пусть имеется набор свойств a 1 , … , a n {displaystyle a_{1},ldots ,a_{n}} . Каждый элемент множества U {displaystyle U} может обладать или не обладать любым из этих свойств. Обозначим через N ( a i 1 … a i s ) {displaystyle N(a_{i_{1}}ldots a_{i_{s}})} количество элементов, обладающих свойствами a i 1 , … , a i s {displaystyle a_{i_{1}},ldots ,a_{i_{s}}} (и, может быть, некоторыми другими). Также через N ( a ¯ i 1 … a ¯ i s ) {displaystyle N({overline {a}}_{i_{1}}ldots {overline {a}}_{i_{s}})} обозначим количество элементов, не обладающих ни одним из свойств a i 1 , … , a i s {displaystyle a_{i_{1}},ldots ,a_{i_{s}}} . Тогда имеет место формула:

N ( a ¯ 1 … a ¯ n ) = N − ∑ i N ( a i ) + ∑ i < j N ( a i a j ) − ∑ i < j < k N ( a i a j a k ) + … + ( − 1 ) n N ( a 1 … a n ) . {displaystyle N({overline {a}}_{1}ldots {overline {a}}_{n})=N-sum _{i}N(a_{i})+sum _{i<j}N(a_{i}a_{j})-sum _{i<j<k}N(a_{i}a_{j}a_{k})+ldots +(-1)^{n}N(a_{1}ldots a_{n}).}

Формулировка принципа включений-исключений в терминах множеств эквивалентна формулировке в терминах свойств. Действительно, если множества A i {displaystyle A_{i}} являются подмножествами некоторого множества U {displaystyle U} , то в силу правил де Моргана | ⋃ i A i | = | U | − | ⋂ i A i ¯ | {displaystyle |igcup olimits _{i}A_{i}|=|U|-|igcap olimits _{i}{overline {A_{i}}}|} (черта над множеством — дополнение в множестве U {displaystyle U} ), и формулу включений-исключений можно переписать так:

| ⋂ i = 1 n A i ¯ | = | U | − ∑ i | A i | + ∑ i < j | A i ∩ A j | − ∑ i < j < k | A i ∩ A j ∩ A k | + … + ( − 1 ) n | A 1 ∩ A 2 ∩ … ∩ A n | . {displaystyle {iggl |}igcap _{i=1}^{n}{overline {A_{i}}}{iggl |}=|U|-sum _{i}|A_{i}|+sum _{i<j}|A_{i}cap A_{j}|-sum _{i<j<k}|A_{i}cap A_{j}cap A_{k}|+ldots +(-1)^{n}|A_{1}cap A_{2}cap ldots cap A_{n}|.}

Если теперь вместо «элемент x {displaystyle x} принадлежит множеству A i {displaystyle A_{i}} » говорить «элемент x {displaystyle x} обладает свойством a i {displaystyle a_{i}} », то мы получим формулировку принципа включений-исключений в терминах свойств, и наоборот.

Обозначим через N ( r ) {displaystyle N(r)} количество элементов, обладающих в точности r {displaystyle r} свойствами из набора a 1 , … , a n {displaystyle a_{1},ldots ,a_{n}} .Тогда формулу включений-исключений можно переписать в следующей форме:

N ( 0 ) = ∑ k = 0 n ( − 1 ) k ∑ i 1 < … < i k N ( i 1 , … , i k ) . {displaystyle N(0)=sum _{k=0}^{n}(-1)^{k}sum _{i_{1}<ldots <i_{k}}N(i_{1},ldots ,i_{k}).}

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

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

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

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

При n = 1 {displaystyle n=1} формула включений-исключений тривиальна:

N ( a ¯ ) = N − N ( a ) . {displaystyle N({overline {a}})=N-N(a).}

Пусть формула верна для n = m {displaystyle n=m} , докажем её для n = m + 1 {displaystyle n=m+1} .

Пусть каждый элемент множества U {displaystyle U} может обладать или не обладать любым из свойств a 1 , … , a m , a m + 1 {displaystyle a_{1},ldots ,a_{m},a_{m+1}} . Применим формулу включений-исключений для свойств a 1 , … , a m {displaystyle a_{1},ldots ,a_{m}} :

N ( a ¯ 1 … a ¯ m ) = N − ∑ i ≤ m N ( a i ) + ∑ i < j ≤ m N ( a i a j ) + … + ( − 1 ) m N ( a 1 … a m ) . {displaystyle N({overline {a}}_{1}ldots {overline {a}}_{m})=N-sum _{ileq m}N(a_{i})+sum _{i<jleq m}N(a_{i}a_{j})+ldots +(-1)^{m}N(a_{1}ldots a_{m}).}

Теперь применим формулу для свойств a 1 , … , a m {displaystyle a_{1},ldots ,a_{m}} к множеству N ( a m + 1 ) {displaystyle N(a_{m+1})} объектов, для которых выполнено свойство a m + 1 {displaystyle a_{m+1}} :

N ( a ¯ 1 … a ¯ m a m + 1 ) = N ( a m + 1 ) − ∑ i ≤ m N ( a i a m + 1 ) + ∑ i < j ≤ m N ( a i a j a m + 1 ) + … + ( − 1 ) m N ( a 1 … a m a m + 1 ) . {displaystyle N({overline {a}}_{1}ldots {overline {a}}_{m}a_{m+1})=N(a_{m+1})-sum _{ileq m}N(a_{i}a_{m+1})+sum _{i<jleq m}N(a_{i}a_{j}a_{m+1})+ldots +(-1)^{m}N(a_{1}ldots a_{m}a_{m+1}).}

Наконец, применим формулу для одного свойства a m + 1 {displaystyle a_{m+1}} к совокупности N ( a ¯ 1 … a ¯ m ) {displaystyle N({overline {a}}_{1}ldots {overline {a}}_{m})} , объектов, которые не обладают свойствами a 1 , … , a m {displaystyle a_{1},ldots ,a_{m}} :

N ( a ¯ 1 … a ¯ m a ¯ m + 1 ) = N ( a ¯ 1 … a ¯ m ) − N ( a ¯ 1 … a ¯ m a m + 1 ) . {displaystyle N({overline {a}}_{1}ldots {overline {a}}_{m}{overline {a}}_{m+1})=N({overline {a}}_{1}ldots {overline {a}}_{m})-N({overline {a}}_{1}ldots {overline {a}}_{m}a_{m+1}).}

Комбинируя выписанные три формулы, получим формулу включений-исключений для m + 1 {displaystyle m+1} свойств a 1 , … , a m + 1 {displaystyle a_{1},ldots ,a_{m+1}} . Что и требовалось доказать. ■

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

Рассмотрим произвольный элемент e ∈ U {displaystyle ein U} и подсчитаем, сколько раз он учитывается в правой части формулы включений-исключений.

Если элемент e {displaystyle e} не обладает ни одним из свойств a i {displaystyle a_{i}} , то в правой части формулы он учитывается ровно 1 раз (в члене N {displaystyle N} ).

Пусть элемент e {displaystyle e} обладает в точности r {displaystyle r} свойствами, скажем a j 1 , … , a j r {displaystyle a_{j_{1}},ldots ,a_{j_{r}}} . Он дает по 1 в тех слагаемых суммы ∑ i 1 < … < i s N ( a i 1 , … , a i s ) {displaystyle sum olimits _{i_{1}<ldots <i_{s}}N(a_{i_{1}},ldots ,a_{i_{s}})} , для которых { i 1 , … , i s } {displaystyle {i_{1},ldots ,i_{s}}} есть подмножество { j 1 , … , j r } {displaystyle {j_{1},ldots ,j_{r}}} , и 0 для остальных. Число таких подмножеств по определению есть число сочетаний ( r s ) {displaystyle { binom {r}{s}}} . Следовательно, вклад элемента e {displaystyle e} в правую часть равен

1 − ( r 1 ) + ( r 2 ) − … + ( − 1 ) r ( r r ) . {displaystyle 1-{r choose 1}+{r choose 2}-ldots +(-1)^{r}{r choose r}.}

При s > r {displaystyle s>r} числа сочетаний равны нулю. Оставшаяся сумма в силу биномиальной теоремы равна

∑ s = 0 r ( − 1 ) s ( r s ) = ( 1 + ( − 1 ) ) r = 0. {displaystyle sum _{s=0}^{r}(-1)^{s}{r choose s}={igg (}1+(-1){igg )}^{r}=0.}

Таким образом, правая часть формулы включений-исключений учитывает каждый элемент, не имеющий указанных свойств точно по одному разу, а каждый элемент, обладающий хотя бы одним из свойств — нуль раз. Следовательно, она равна количеству элементов, не обладающих ни одним из свойств a i {displaystyle a_{i}} , то есть N ( a ¯ 1 … a ¯ n ) {displaystyle N({overline {a}}_{1}ldots {overline {a}}_{n})} . Что и требовалось доказать. ■

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

Пусть A i {displaystyle A_{i}} — произвольные (не обязательно конечные) множества, являющиеся подмножествами некоторого множества U {displaystyle U} , и пусть 1 A i {displaystyle mathbf {1} _{A_{i}}} — индикаторные функции A i {displaystyle A_{i}} (или, эквивалентно, свойств a i {displaystyle a_{i}} ).

Индикаторная функция их дополнений A i ¯ {displaystyle {overline {A_{i}}}} равна

1 A i ¯ = 1 − 1 A i , {displaystyle mathbf {1} _{overline {A_{i}}}=1-mathbf {1} _{A_{i}},}

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

1 ∩ i A i ¯ = ∏ i ( 1 − 1 A i ) . {displaystyle mathbf {1} _{cap _{i}{overline {A_{i}}}}=prod _{i}(1-mathbf {1} _{A_{i}}).}

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

1 ⋂ i A i ¯ = 1 − ∑ i 1 A i + ∑ i < j 1 A i ∩ A j − ∑ i < j < k 1 A i ∩ A j ∩ A k + … + ( − 1 ) n 1 A 1 ∩ … ∩ A n . {displaystyle mathbf {1} _{igcap _{i}{overline {A_{i}}}}=1-sum _{i}mathbf {1} _{A_{i}}+sum _{i<j}mathbf {1} _{A_{i}cap A_{j}}-sum _{i<j<k}mathbf {1} _{A_{i}cap A_{j}cap A_{k}}+ldots +(-1)^{n}mathbf {1} _{A_{1}cap ldots cap A_{n}}.}

Это соотношение — одна из форм принципа включений-исключений. Оно выражает собой логическое тождество и верно для произвольных множеств A i {displaystyle A_{i}} . В случае конечных множеств A i {displaystyle A_{i}} (и, соответственно, в предположении конечности множества U {displaystyle U} ), просуммировав это соотношение по всем x ∈ U {displaystyle xin U} и воспользоваться тем, что для произвольного подмножества A ⊂ U {displaystyle Asubset U} его мощность равна

| A | = ∑ x ∈ U 1 A ( x ) , {displaystyle |A|=sum _{xin U}mathbf {1} _{A}(x),}

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

Топологическое доказательство

Снабдим множества A i {displaystyle A_{i}} дискретной топологией. В таком случае H k ( A i ) = 0 {displaystyle H^{k}(A_{i})=0} при k > 0 {displaystyle k>0} , а при k = 0 {displaystyle k=0} имеет место тождество dim ⁡ H 0 ( A i ) = | A i | . {displaystyle dim H^{0}(A_{i})=|A_{i}|.} В случае двух множеств A 1 {displaystyle A_{1}} и A 2 {displaystyle A_{2}} можно воспользоваться точной последовательностью Майера — Вьеториса, которая, учитывая зануление старших когомологий, будет выглядеть как: 0 → H 0 ( A 1 ∪ A 2 ) → H 0 ( A 1 ) ⊕ H 0 ( A 2 ) → H 0 ( A 1 ∩ A 2 ) → 0. {displaystyle 0 o H^{0}(A_{1}cup A_{2}) o H^{0}(A_{1})oplus H^{0}(A_{2}) o H^{0}(A_{1}cap A_{2}) o 0.} Значит, имеет место тождество dim ⁡ H 0 ( A 1 ) ⊕ H 0 ( A 2 ) = dim ⁡ H 0 ( A 1 ∪ A 2 ) + dim ⁡ H 0 ( A 1 ∩ A 2 ) , {displaystyle dim H^{0}(A_{1})oplus H^{0}(A_{2})=dim H^{0}(A_{1}cup A_{2})+dim H^{0}(A_{1}cap A_{2}),} или, если переписать его, | A 1 | + | A 2 | = | A 1 ∪ A 2 | + | A 1 ∩ A 2 | , {displaystyle |A_{1}|+|A_{2}|=|A_{1}cup A_{2}|+|A_{1}cap A_{2}|,} что эквивалентно формуле включений-исключений.

В случае более чем двух множеств для доказательства формулы включений-исключений вместо точной последовательности Майера — Вьеториса надо написать некоторую спектральную последовательность (а именно спектральную последовательность Лере для отображения проекции из несвязного объединения A i {displaystyle A_{i}} в их объединение), и так же вычислить ранги групп когомологий. ■

Применение

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

Классический пример использования формулы включений-исключений — задача о беспорядках. Требуется найти число перестановок ( p 1 , p 2 , … , p n ) {displaystyle (p_{1},p_{2},ldots ,p_{n})} множества { 1 , 2 , … , n } {displaystyle {1,2,ldots ,n}} таких что p i ≠ i {displaystyle p_{i} eq i} для всех i {displaystyle i} . Такие перестановки называются беспорядками.

Пусть U {displaystyle U} — множество всех перестановок p {displaystyle p} и пусть свойство a i {displaystyle a_{i}} перестановки выражается равенством p i = i {displaystyle p_{i}=i} . Тогда число беспорядков есть N ( a ¯ 1 , a ¯ 2 , … , a ¯ n ) {displaystyle N({overline {a}}_{1},{overline {a}}_{2},ldots ,{overline {a}}_{n})} . Легко видеть, что N ( a i 1 , … , a i s ) = ( n − s ) ! {displaystyle N(a_{i_{1}},ldots ,a_{i_{s}})=(n-s)!} — число перестановок, оставляющих на месте элементы i 1 , … , i s {displaystyle i_{1},ldots ,i_{s}} , и таким образом сумма ∑ N ( a i 1 , a i 2 , … , a i s ) {displaystyle sum N(a_{i_{1}},a_{i_{2}},ldots ,a_{i_{s}})} содержит ( n s ) {displaystyle { binom {n}{s}}} одинаковых слагаемых. Формула включений-исключений дает выражение для числа D n {displaystyle D_{n}} беспорядков:

D n = n ! − ( n 1 ) ( n − 1 ) ! + ( n 2 ) ( n − 2 ) ! − … + ( − 1 ) n ( n n ) 0 ! . {displaystyle D_{n}=n!-{n choose 1}(n-1)!+{n choose 2}(n-2)!-ldots +(-1)^{n}{n choose n}0!.}

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

D n = n ! ( 1 − 1 1 ! + 1 2 ! − … + ( − 1 ) n n ! ) . {displaystyle D_{n}=n!left(1-{frac {1}{1!}}+{frac {1}{2!}}-ldots +{frac {(-1)^{n}}{n!}} ight).}

Нетрудно видеть, что выражение в скобках является частичной суммой ряда ∑ k = 0 ∞ ( − 1 ) k k ! = e − 1 {displaystyle sum _{k=0}^{infty }{frac {(-1)^{k}}{k!}}=e^{-1}} . Таким образом, с хорошей точностью число беспорядков составляет 1 / e {displaystyle 1/e} долю от общего числа P n = n ! {displaystyle P_{n}=n!} перестановок:

D n / P n ≈ 1 / e . {displaystyle D_{n}/P_{n}approx 1/e.}

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

Другой пример применения формулы включений-исключений — нахождение явного выражения для функции Эйлера φ ( n ) {displaystyle varphi (n)} , выражающей количество чисел из { 1 , 2 , … , n } {displaystyle {1,2,ldots ,n}} , взаимно простых с n {displaystyle n} .

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

n = p 1 s 1 p 2 s 2 … p k s k . {displaystyle n=p_{1}^{s_{1}}p_{2}^{s_{2}}ldots p_{k}^{s_{k}}.}

Число m ∈ { 1 , … n } {displaystyle min {1,ldots n}} взаимно просто с n {displaystyle n} тогда и только тогда, когда ни один из простых делителей p i {displaystyle p_{i}} не делит m {displaystyle m} . Если теперь свойство a i {displaystyle a_{i}} означает, что p i {displaystyle p_{i}} делит m {displaystyle m} , то количество чисел взаимно простых с n {displaystyle n} есть N ( a ¯ 1 , … , a ¯ k ) {displaystyle N({overline {a}}_{1},ldots ,{overline {a}}_{k})} .

Количество N ( a i 1 , … , a i s ) {displaystyle N(a_{i_{1}},ldots ,a_{i_{s}})} чисел, обладающих свойствами a i 1 , … , a i s {displaystyle a_{i_{1}},ldots ,a_{i_{s}}} равно n / p i 1 … p i s {displaystyle n/p_{i_{1}}ldots p_{i_{s}}} , поскольку p i 1 | m , … , p i s | m ⇔ p i 1 … p i s | m {displaystyle p_{i_{1}}|m,ldots ,p_{i_{s}}|mLeftrightarrow p_{i_{1}}ldots p_{i_{s}}|m} .

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

φ ( n ) = n − ∑ i n / p i + ∑ i , j n / p i p j − … + ( − 1 ) k n / p 1 … p k . {displaystyle varphi (n)=n-sum _{i}n/p_{i}+sum _{i,j}n/p_{i}p_{j}-ldots +(-1)^{k}n/p_{1}ldots p_{k}.}

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

φ ( n ) = n ∏ i = 1 k ( 1 − 1 p i ) . {displaystyle varphi (n)=nprod _{i=1}^{k}left(1-{frac {1}{p_{i}}} ight).}

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

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

Пусть ( Ω , F , P ) {displaystyle (Omega ,{mathfrak {F}},{mathcal {P}})} — вероятностное пространство. Тогда для произвольных событий A 1 , A 2 , … , A n {displaystyle A_{1},A_{2},ldots ,A_{n}} справедлива формула

P ( ⋃ i = 1 n A i ) = ∑ i P ( A i ) − ∑ i < j P ( A i ∩ A j ) + ∑ i < j < k P ( A i ∩ A j ∩ A k ) + … + ( − 1 ) n − 1 P ( ⋂ i = 1 n A i ) . {displaystyle {mathcal {P}}{iggl (}igcup _{i=1}^{n}A_{i}{iggr )}=sum _{i}{mathcal {P}}(A_{i})-sum _{i<j}{mathcal {P}}(A_{i}cap A_{j})+sum _{i<j<k}{mathcal {P}}(A_{i}cap A_{j}cap A_{k})+ldots +(-1)^{n-1},{mathcal {P}}left(igcap _{i=1}^{n}A_{i} ight).}

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

1 ⋃ i A i = ∑ i 1 A i − ∑ i < j 1 A i ∩ A j + ∑ i < j < k 1 A i ∩ A j ∩ A k + … + ( − 1 ) n − 1 1 A 1 ∩ … ∩ A n . {displaystyle mathbf {1} _{igcup _{i}A_{i}}=sum _{i}mathbf {1} _{A_{i}}-sum _{i<j}mathbf {1} _{A_{i}cap A_{j}}+sum _{i<j<k}mathbf {1} _{A_{i}cap A_{j}cap A_{k}}+ldots +(-1)^{n-1},mathbf {1} _{A_{1}cap ldots cap A_{n}}.}

Пусть A i {displaystyle A_{i}} — события вероятностного пространства ( Ω , F , P ) {displaystyle (Omega ,{mathfrak {F}},{mathcal {P}})} , то есть A i ∈ F {displaystyle A_{i}in {mathfrak {F}}} . Возьмем математическое ожидание M {displaystyle {mathcal {M}}} от обеих частей этого соотношения, и, воспользовавших линейностью математического ожидания и равенством P ( A ) = M ( 1 A ) {displaystyle {mathcal {P}}(A)={mathcal {M}}(mathbf {1} _{A})} для произвольного события A ∈ F {displaystyle Ain {mathfrak {F}}} , получим формулу включения-исключения для вероятностей.

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

Пусть ( X , S , μ ) {displaystyle (X,{mathfrak {S}},mu )} — пространство с мерой. Тогда для произвольных измеримых множеств A i {displaystyle A_{i}} конечной меры μ ( A i ) < ∞ {displaystyle mu (A_{i})<infty } имеет место формула включений-исключений:

μ ( ⋃ i = 1 n A i ) = ∑ i μ ( A i ) − ∑ i < j μ ( A i ∩ A j ) + ∑ i < j < k μ ( A i ∩ A j ∩ A k ) + … + ( − 1 ) n − 1 μ ( ⋂ i = 1 n A i ) . {displaystyle mu {iggl (}igcup _{i=1}^{n}A_{i}{iggr )}=sum _{i}mu (A_{i})-sum _{i<j}mu (A_{i}cap A_{j})+sum _{i<j<k}mu (A_{i}cap A_{j}cap A_{k})+ldots +(-1)^{n-1},mu left(igcap _{i=1}^{n}A_{i} ight).}

Очевидно, принцип включений-исключений для вероятностей и для мощностей конечных множеств являются частными случаями этой формулы. В первом случае мерой является, естественно, вероятностная мера в соответствующем вероятностном пространстве: μ ( A ) = P ( A ) {displaystyle mu (A)={mathcal {P}}(A)} . Во втором случае в качестве меры берется мощность множества: μ ( A ) = | A | {displaystyle mu (A)=|A|} .

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

1 ⋃ i A i = ∑ i 1 A i − ∑ i < j 1 A i ∩ A j + ∑ i < j < k 1 A i ∩ A j ∩ A k + … + ( − 1 ) n − 1 1 A 1 ∩ … ∩ A n . {displaystyle mathbf {1} _{igcup _{i}A_{i}}=sum _{i}mathbf {1} _{A_{i}}-sum _{i<j}mathbf {1} _{A_{i}cap A_{j}}+sum _{i<j<k}mathbf {1} _{A_{i}cap A_{j}cap A_{k}}+ldots +(-1)^{n-1},mathbf {1} _{A_{1}cap ldots cap A_{n}}.}

Пусть A i {displaystyle A_{i}} — измеримые множества пространства ( X , S , μ ) {displaystyle (X,{mathfrak {S}},mu )} , то есть A i ∈ S {displaystyle A_{i}in {mathfrak {S}}} . Проинтегрируем обе части этого равенства по мере μ {displaystyle mu } , воспользуемся линейностью интеграла и соотношением μ ( A ) = ∫ X 1 A ( x ) d μ {displaystyle mu (A)=int _{X}mathbf {1} _{A}(x),dmu } , и получим формулу включений-исключений для меры.

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

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

max ( a 1 , … , a n ) = ∑ i a i − ∑ i < j min ( a i , a j ) + … + ( − 1 ) n − 1 min ( a 1 , … , a n ) . {displaystyle max(a_{1},ldots ,a_{n})=sum _{i}a_{i}-sum _{i<j}min(a_{i},a_{j})+ldots +(-1)^{n-1},min(a_{1},ldots ,a_{n}).}

Это соотношение справедливо для произвольных чисел a i {displaystyle a_{i}} . В частном случае, когда a i ∈ { 0 , 1 } {displaystyle a_{i}in {0,1}} мы получаем одну из форм принципа включений-исключений. В самом деле, если положить a i = 1 A i ( x ) {displaystyle a_{i}=mathbf {1} _{A_{i}}(x)} , где x {displaystyle x} — произвольный элемент из U {displaystyle U} , то получим соотношение для индикаторных функций множеств:

1 ⋃ i A i ( x ) = ∑ i 1 A i ( x ) − ∑ i < j 1 A i ∩ A j ( x ) + ∑ i < j < k 1 A i ∩ A j ∩ A k ( x ) + … + ( − 1 ) n − 1 1 A 1 ∩ … ∩ A n ( x ) . {displaystyle mathbf {1} _{igcup _{i}A_{i}}(x)=sum _{i}mathbf {1} _{A_{i}}(x)-sum _{i<j}mathbf {1} _{A_{i}cap A_{j}}(x)+sum _{i<j<k}mathbf {1} _{A_{i}cap A_{j}cap A_{k}}(x)+ldots +(-1)^{n-1},mathbf {1} _{A_{1}cap ldots cap A_{n}}(x).}

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

Пусть S {displaystyle S} — конечное множество, и пусть f : 2 S → R {displaystyle fcolon 2^{S} o mathbb {R} } — произвольная функция, определенная на совокупности подмножеств S {displaystyle S} и принимающая действительные значения. Определим функцию g : 2 S → R {displaystyle gcolon 2^{S} o mathbb {R} } следующим соотношением:

g ( Y ) = ∑ X ⊃ Y f ( X ) . {displaystyle g(Y)=sum _{Xsupset Y}f(X).}

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

f ( Y ) = ∑ X ⊃ Y ( − 1 ) | X | − | Y | g ( X ) . {displaystyle f(Y)=sum _{Xsupset Y}(-1)^{|X|-|Y|},g(X).}

Это утверждение является частным случаем общей формулы обращения Мёбиуса для алгебры инцидентности совокупности 2 S {displaystyle 2^{S}} всех подмножеств множества S {displaystyle S} , частично упорядоченных по отношению включения ⊂ {displaystyle subset } .

Покажем, как из этой формулы следует принцип включения-исключения для конечных множеств. Пусть дано семейство подмножеств A 1 , … , A n {displaystyle A_{1},ldots ,A_{n}} конечного множества U {displaystyle U} , обозначим S = { 1 , … , n } {displaystyle S={1,ldots ,n}} — множество индексов. Для каждого набора индексов X ⊂ S {displaystyle Xsubset S} определим f ( X ) {displaystyle f(X)} как число элементов, входящих только в те множества A i {displaystyle A_{i}} , для которых i ∈ X {displaystyle iin X} . Математически это можно записать так:

f ( X ) = | ( ⋂ i ∈ X A i ) ∩ ( ⋂ j ∉ X A j ¯ ) | . {displaystyle f(X)=left|left(igcap _{iin X}A_{i} ight)cap left(igcap _{j otin X}{overline {A_{j}}} ight) ight|.}

Тогда функция g : 2 S → R {displaystyle gcolon 2^{S} o mathbb {R} } , определенная формулой

g ( Y ) = ∑ X ⊃ Y f ( X ) , {displaystyle g(Y)=sum _{Xsupset Y}f(X),}

даёт количество элементов, каждый из которых входит во все множества A i {displaystyle A_{i}} , i ∈ X {displaystyle iin X} и, быть может, ещё в другие. То есть

g ( X ) = | ⋂ i ∈ X A i | . {displaystyle g(X)=left|igcap _{iin X}A_{i} ight|.}

Заметим далее, что f ( ∅ ) {displaystyle f(varnothing )} — количество элементов, не обладающих ни одним из свойств:

f ( ∅ ) = | ⋂ i A i ¯ | . {displaystyle f(varnothing )=left|igcap _{i}{overline {A_{i}}} ight|.}

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

| ⋂ i A i ¯ | = ∑ X ( − 1 ) | X | | ⋂ i ∈ X A i | . {displaystyle left|igcap _{i}{overline {A_{i}}} ight|=sum _{X}(-1)^{|X|},left|igcap _{iin X}A_{i} ight|.}

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

История

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