Princip inkluze a exkluze popisuje vztah mezi velikostí sjednocení nějakých množin a velikostmi všech možných průniků těchto množin.
Představme si úlohu, máme čísla 1 až 1000, kolik z nich je dělitelných dvěma nebo třemi? (jsou to 2, 3, 4, 6, 8, 9, 10 ...) Můžeme vzít sudá čísla (500) a přičíst k ním násobky trojky (333), ale pozor – čísla 6 nebo 12 jsme započítali dvakrát!
Princip inkluze a exkluze nám říká, že počet prvků ve sjednocení dvou množin je součet počtu prvků v každé z nich, minus počet prvků, které jsou v obou.
|
A
∪
B
|
=
|
A
|
+
|
B
|
−
|
A
∩
B
|
{\displaystyle |A\cup B|=|A|+|B|-|A\cap B|\,}
Tedy výsledek = počet čísel dělitelných dvěma (500) + počet čísel dělitelných třemi (333) – počet čísel dělitelných šesti (166) = 667.
Podobně pro 3 množiny A , B a C ,
|
A
∪
B
∪
C
|
=
|
A
|
+
|
B
|
+
|
C
|
−
|
A
∩
B
|
−
|
A
∩
C
|
−
|
B
∩
C
|
+
|
A
∩
B
∩
C
|
{\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\,}
Obecně, pro každý soubor
n
{\displaystyle n}
A
1
,
A
2
,
.
.
.
,
A
n
{\displaystyle A_{1},A_{2},...,A_{n}}
|
⋃
i
=
1
n
A
i
|
=
∑
∅
≠
I
⊆
{
1
,
2.
,
.
.
.
,
n
}
(
−
1
)
|
I
|
−
1
|
⋂
i
∈
I
A
i
|
{\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq I\subseteq \{1,2.,...,n\}}\left(-1\right)^{\left|I\right|-1}\left|\bigcap _{i\in I}A_{i}\right|}
|
⋃
i
=
1
n
A
i
|
=
∑
i
=
1
n
|
A
i
|
−
∑
1
≤
i
1
<
i
2
≤
n
|
A
i
1
∩
A
i
2
|
+
+
∑
1
≤
i
1
<
i
2
<
i
3
<
…
≤
n
|
A
i
1
∩
A
i
2
∩
A
i
3
|
−
−
⋯
+
(
−
1
)
n
−
1
|
A
1
∩
A
2
∩
…
∩
A
n
|
{\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{1\leq i_{1}<i_{2}\leq n}\left|A_{i_{1}}\cap A_{i_{2}}\right|+\\&{}+\sum _{1\leq i_{1}<i_{2}<i_{3}<\ldots \leq n}\left|A_{i_{1}}\cap A_{i_{2}}\cap A_{i_{3}}\right|-\\&{}-\cdots +\left(-1\right)^{n-1}\left|A_{1}\cap A_{2}\cap \ldots \cap A_{n}\right|\end{aligned}}}
či
|
⋃
i
=
1
n
A
i
|
=
∑
k
=
1
n
(
−
1
)
k
−
1
∑
I
∈
(
{
1
,
2
,
.
.
.
,
n
}
k
)
|
⋂
i
∈
I
A
i
|
{\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}\left(-1\right)^{k-1}\sum _{I\in {\{1,2,...,n\} \choose k}}\left|\bigcap _{i\in I}A_{i}\right|}
kde symbol
(
X
k
)
{\displaystyle {X \choose k}}
k –prvkové podmnožiny množiny X .
Označme
A
=
⋃
i
=
1
n
A
i
{\displaystyle A=\bigcup _{i=1}^{n}A_{i}}
f
i
:
A
→
{
0
,
1
}
{\displaystyle f_{i}:A\rightarrow \{0,1\}}
charakteristická funkce množiny
A
i
{\displaystyle A_{i}}
f
i
(
a
)
=
{
1
,
a
∈
A
i
0
,
jinak
{\displaystyle f_{i}(a)=\left\{{\begin{matrix}1,&a\in A_{i}\\0,&{\mbox{jinak}}\end{matrix}}\right.}
Pro každé
a
∈
A
{\displaystyle a\in A}
∏
i
=
1
n
(
1
−
f
i
(
a
)
)
=
0
{\displaystyle \prod _{i=1}^{n}(1-f_{i}(a))=0}
(
1
+
x
1
)
(
1
+
x
2
)
⋯
(
1
+
x
n
)
=
∑
I
⊆
{
1
,
2
,
.
.
.
n
}
(
∏
i
∈
I
x
i
)
{\displaystyle (1+x_{1})(1+x_{2})\cdots (1+x_{n})=\sum _{I\subseteq \{1,2,...n\}}\left(\prod _{i\in I}x_{i}\right)}
a dosazením
x
i
=
−
f
i
(
x
)
{\displaystyle x_{i}=-f_{i}\,\!(x)}
∑
I
⊆
{
1
,
2
,
.
.
.
n
}
(
−
1
)
|
I
|
∏
i
∈
I
f
i
(
a
)
=
0.
{\displaystyle \sum _{I\subseteq \{1,2,...n\}}\left(-1\right)^{\left|I\right|}\prod _{i\in I}f_{i}(a)=0.}
Sečtením těchto rovností pro všechna
a
∈
A
{\displaystyle a\in A}
sumace získáme
0
=
∑
a
∈
A
(
∑
I
⊆
{
1
,
2
,
.
.
.
n
}
(
−
1
)
|
I
|
∏
i
∈
I
f
i
(
a
)
)
=
∑
I
⊆
{
1
,
2
,
.
.
.
n
}
(
−
1
)
|
I
|
(
∑
a
∈
A
∏
i
∈
I
f
i
(
A
)
)
.
{\displaystyle 0=\sum _{a\in A}\left(\sum _{I\subseteq \{1,2,...n\}}\left(-1\right)^{\left|I\right|}\prod _{i\in I}f_{i}(a)\right)=\sum _{I\subseteq \{1,2,...n\}}\left(-1\right)^{\left|I\right|}\left(\sum _{a\in A}\prod _{i\in I}f_{i}(A)\right).}
Nyní si stačí uvědomit, že
∏
i
∈
I
f
i
(
a
)
{\displaystyle \prod _{i\in I}f_{i}(a)}
⋂
i
∈
I
A
i
{\displaystyle \bigcap _{i\in I}A_{i}}
∑
a
∈
A
∏
i
∈
I
f
i
(
a
)
=
|
⋂
i
∈
I
A
i
|
{\displaystyle \sum _{a\in A}\prod _{i\in I}f_{i}(a)=\left|\bigcap _{i\in I}A_{i}\right|}
Speciálně pro
I
=
∅
{\displaystyle I=\emptyset }
∏
i
∈
∅
f
i
(
a
)
{\displaystyle \prod _{i\in \emptyset }f_{i}(a)}
součin , jenž má podle definice hodnotu 1, takže
∑
a
∈
A
∏
i
∈
∅
f
i
(
a
)
=
|
A
|
{\displaystyle \sum _{a\in A}\prod _{i\in \emptyset }f_{i}(a)=\left|A\right|}
0
=
∑
I
⊆
{
1
,
2
,
.
.
.
n
}
(
−
1
)
|
I
|
(
∑
a
∈
A
∏
i
∈
I
f
i
(
A
)
)
=
|
A
|
+
∑
∅
≠
I
⊆
{
1
,
2
,
.
.
.
n
}
(
−
1
)
|
I
|
|
⋂
i
∈
I
A
i
|
,
{\displaystyle 0=\sum _{I\subseteq \{1,2,...n\}}\left(-1\right)^{\left|I\right|}\left(\sum _{a\in A}\prod _{i\in I}f_{i}(A)\right)=\left|A\right|+\sum _{\emptyset \neq I\subseteq \{1,2,...n\}}\left(-1\right)^{\left|I\right|}\left|\bigcap _{i\in I}A_{i}\right|,}
což je přesně princip inkluze a exkluze.
