Princip inkluze a exkluze
Jan Paseka
Masarykova univerzita Brno
Princip inkuze a exkluze ­ p.1/15

Abstrakt
Opakování principu inkluze a exkluze.
Princip inkuze a exkluze ­ p.2/15

Obsah přednášky
Princip inkluze a exkluze.
Příklad na počet surjektivních zobrazení.
Příklad na počet permutací bez pevného
bodu.
Princip inkuze a exkluze ­ p.3/15

Princip inkluze a exkluze I
Je dána konečná množina Q objektů, u nichž rozlišujeme
konečný počet jistých vlastností, indexovaných prvky
nějaké konečné množiny I. Každý z objektů množiny Q
může mít některé ze zmíněných vlastností a jiné mít
nemusí.
Princip inkuze a exkluze ­ p.4/15

Princip inkluze a exkluze I
Je dána konečná množina Q objektů, u nichž rozlišujeme
konečný počet jistých vlastností, indexovaných prvky
nějaké konečné množiny I. Každý z objektů množiny Q
může mít některé ze zmíněných vlastností a jiné mít
nemusí.
Problém, který zkoumáme, spočívá v tom, jak určit, kolik je
objektů nemajících žádnou z uvedených vlastností.
Princip inkuze a exkluze ­ p.4/15

Princip inkluze a exkluze I
Je dána konečná množina Q objektů, u nichž rozlišujeme
konečný počet jistých vlastností, indexovaných prvky
nějaké konečné množiny I. Každý z objektů množiny Q
může mít některé ze zmíněných vlastností a jiné mít
nemusí.
Problém, který zkoumáme, spočívá v tom, jak určit, kolik je
objektů nemajících žádnou z uvedených vlastností.
Jestliže pro každé i  I označíme Ai množinu všech těch
objektů z Q, které mají vlastnost s indexem i, pak jde o to,
jak zjistit, kolik prvků má množina A(0) = Q -
i
I Ai.
Princip inkuze a exkluze ­ p.4/15

Vennův diagram
|ABC| = |A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|
Princip inkuze a exkluze ­ p.5/15

Vennův diagram
|Q| - |A  B  C| = |Q| - |A| - |B| - |C| + |A  B| + |A  C| + |B  C| - |A  B  C|
Princip inkuze a exkluze ­ p.6/15

Princip inkluze a exkluze II
Věta. Bud' Q konečná množina. Mějme konečnou
indexovou množinu I a mějme konečný soubor množin Ai,
kde i  I, jež jsou všechny podmnožinami množiny Q. To
znamená, že Ai  Q pro každé i  I.
Princip inkuze a exkluze ­ p.7/15

Princip inkluze a exkluze II
Věta. Bud' Q konečná množina. Mějme konečnou
indexovou množinu I a mějme konečný soubor množin Ai,
kde i  I, jež jsou všechny podmnožinami množiny Q. To
znamená, že Ai  Q pro každé i  I. Potom pro množinu
A(0) = Q -
i
I Ai platí
|A(0)| =
K
I
(-1)|K|

i
K
Ai
.
Princip inkuze a exkluze ­ p.7/15

Princip inkluze a exkluze II
Věta. Bud' Q konečná množina. Mějme konečnou
indexovou množinu I a mějme konečný soubor množin Ai,
kde i  I, jež jsou všechny podmnožinami množiny Q. To
znamená, že Ai  Q pro každé i  I. Potom pro množinu
A(0) = Q -
i
I Ai platí
|A(0)| =
K
I
(-1)|K|

i
K
Ai
.
Poznámka. Poněvadž Ai  Q pro i  I, klademe
i
 Ai = Q.
Princip inkuze a exkluze ­ p.7/15

Princip inkluze a exkluze III
Vztah dokázaný v předchozí větě lze přepsat na
Princip inkuze a exkluze ­ p.8/15

Princip inkluze a exkluze III
Vztah dokázaný v předchozí větě lze přepsat na
Q
-
i
I
Ai
=
|Q| -
i
I
A
i
+ {
i,j}I
i=j
A
i  Aj
-
{
i,j,k}I
i=j=k=i
A
i  Aj  Ak
+
   + (-1)|I|

i
I
Ai
.
Princip inkuze a exkluze ­ p.8/15

Princip inkluze a exkluze III
Vztah dokázaný v předchozí větě lze přepsat na
Q
-
i
I
Ai
=
|Q| -
i
I
A
i
+ {
i,j}I
i=j
A
i  Aj
-
{
i,j,k}I
i=j=k=i
A
i  Aj  Ak
+
   + (-1)|I|

i
I
Ai
.
Tento vztah kvůli střídání znamének bývá právě označován
termínem princip inkluze a exkluze.
Princip inkuze a exkluze ­ p.8/15

Princip inkluze a exkluze - příklady I
Příklad IE1. Necht' n, k  N  {0} splňují k  n.
Necht' S, resp. U jsou konečné množiny mající n,
resp. k prvků. Je třeba určit, kolik existuje
surjektivních zobrazení g : S  U.
Princip inkuze a exkluze ­ p.9/15

Princip inkluze a exkluze - příklady I
Příklad IE1. Necht' n, k  N  {0} splňují k  n.
Necht' S, resp. U jsou konečné množiny mající n,
resp. k prvků. Je třeba určit, kolik existuje
surjektivních zobrazení g : S  U.
Ř ešení. Jako základní množinu Q vezmeme
množinu všech možných zobrazení f : S  U.
Indexovou množinu I položíme rovnu U.
Princip inkuze a exkluze ­ p.9/15

Princip inkluze a exkluze - příklady I
Příklad IE1. Necht' n, k  N  {0} splňují k  n.
Necht' S, resp. U jsou konečné množiny mající n,
resp. k prvků. Je třeba určit, kolik existuje
surjektivních zobrazení g : S  U.
Ř ešení. Jako základní množinu Q vezmeme
množinu všech možných zobrazení f : S  U.
Indexovou množinu I položíme rovnu U.
Pro w  U máme Aw = {f : S  U ; w / f(S)}.
Princip inkuze a exkluze ­ p.9/15

Princip inkluze a exkluze - příklady I
Příklad IE1. Necht' n, k  N  {0} splňují k  n.
Necht' S, resp. U jsou konečné množiny mající n,
resp. k prvků. Je třeba určit, kolik existuje
surjektivních zobrazení g : S  U.
Ř ešení. Jako základní množinu Q vezmeme
množinu všech možných zobrazení f : S  U.
Indexovou množinu I položíme rovnu U.
Pro w  U máme Aw = {f : S  U ; w / f(S)}.
Tedy A(0) = {f : S  U ; f(S) = U}.
Princip inkuze a exkluze ­ p.9/15

Princip inkluze a exkluze - příklady II
Víme, že
() |A(0)| =
V
U
(-1)|V |

w
V
Aw
.
Princip inkuze a exkluze ­ p.10/15

Princip inkluze a exkluze - příklady II
Víme, že
() |A(0)| =
V
U
(-1)|V |

w
V
Aw
.
Zároveň
w
V Aw = {f : S  U ; V  f(S) = }
= {f : S  U ; f(S)  U - V }.
Princip inkuze a exkluze ­ p.10/15

Princip inkluze a exkluze - příklady II
Ale
|
w
V Aw| = |{f : S  U ; f(S)  U - V }|
= |{f : S  U - V }| = |U - V ||S|
= |U - V |n
= (k - |V |)n
.
Princip inkuze a exkluze ­ p.11/15

Princip inkluze a exkluze - příklady II
Ale
|
w
V Aw| = |{f : S  U ; f(S)  U - V }|
= |{f : S  U - V }| = |U - V ||S|
= |U - V |n
= (k - |V |)n
.
Po dosazení do () obdržíme
()
|A(0)| =
V
U (-1)|V |
 (k - |V |)n
=
k
j=0 (-1)j

k
j

(k - j)n
.
Princip inkuze a exkluze ­ p.11/15

Princip inkluze a exkluze - příklady IV
Příklad IE2. Ř ekneme, že číslo i  {1, 2, . . . , n} je pevný
bod takto permutace  : {1, 2, . . . , n}  {1, 2, . . . , n},
platí-li, že (i) = i .
Princip inkuze a exkluze ­ p.12/15

Princip inkluze a exkluze - příklady IV
Příklad IE2. Ř ekneme, že číslo i  {1, 2, . . . , n} je pevný
bod takto permutace  : {1, 2, . . . , n}  {1, 2, . . . , n},
platí-li, že (i) = i .
Určete, kolik existuje permutací množiny {1, 2, . . . , n}, které
nemají ani jeden pevný bod.
Princip inkuze a exkluze ­ p.12/15

Princip inkluze a exkluze - příklady IV
Příklad IE2. Ř ekneme, že číslo i  {1, 2, . . . , n} je pevný
bod takto permutace  : {1, 2, . . . , n}  {1, 2, . . . , n},
platí-li, že (i) = i .
Určete, kolik existuje permutací množiny {1, 2, . . . , n}, které
nemají ani jeden pevný bod.
Ř ešení. Jako základní množinu Q vezmeme množinu Sn
všech možných permutací  : {1, 2, . . . , n}  {1, 2, . . . , n}.
Princip inkuze a exkluze ­ p.12/15

Princip inkluze a exkluze - příklady IV
Příklad IE2. Ř ekneme, že číslo i  {1, 2, . . . , n} je pevný
bod takto permutace  : {1, 2, . . . , n}  {1, 2, . . . , n},
platí-li, že (i) = i .
Určete, kolik existuje permutací množiny {1, 2, . . . , n}, které
nemají ani jeden pevný bod.
Ř ešení. Jako základní množinu Q vezmeme množinu Sn
všech možných permutací  : {1, 2, . . . , n}  {1, 2, . . . , n}.
Za indexovou množinu I vezmeme množinu {1, 2, . . . , n} .
Princip inkuze a exkluze ­ p.12/15

Princip inkluze a exkluze - příklady V
Pro každé i  {1, 2, . . . , n} položíme
Ai = {  Sn | (i) = i}.
Princip inkuze a exkluze ­ p.13/15

Princip inkluze a exkluze - příklady V
Pro každé i  {1, 2, . . . , n} položíme
Ai = {  Sn | (i) = i}.
Množinu A(0) tvoří právě ty permutace   Sn,
které nemají žádný pevný bod.
Princip inkuze a exkluze ­ p.13/15

Princip inkluze a exkluze - příklady V
Pro každé i  {1, 2, . . . , n} položíme
Ai = {  Sn | (i) = i}.
Množinu A(0) tvoří právě ty permutace   Sn,
které nemají žádný pevný bod.
Podle principu inkluze a exkluze máme
(2) |A(0)| =
K
{1,2,...,n}
(-1)|K|

i
K
Ai
.
Princip inkuze a exkluze ­ p.13/15

Princip inkluze a exkluze - příklady V
Množinu
i
K Ai tvoří právě ty permutace   Sn,
pro něž každé číslo z K je pevným bodem.
Princip inkuze a exkluze ­ p.14/15

Princip inkluze a exkluze - příklady V
Množinu
i
K Ai tvoří právě ty permutace   Sn,
pro něž každé číslo z K je pevným bodem.
Tj. permutace množiny {1, 2, . . . , n} - K .
Princip inkuze a exkluze ­ p.14/15

Princip inkluze a exkluze - příklady V
Množinu
i
K Ai tvoří právě ty permutace   Sn,
pro něž každé číslo z K je pevným bodem.
Tj. permutace množiny {1, 2, . . . , n} - K .
Máme pak
i
K Ai
=
(n - |K|)! .
Princip inkuze a exkluze ­ p.14/15

Princip inkluze a exkluze - příklady V
Množinu
i
K Ai tvoří právě ty permutace   Sn,
pro něž každé číslo z K je pevným bodem.
Tj. permutace množiny {1, 2, . . . , n} - K .
Máme pak
i
K Ai
=
(n - |K|)! . Dosazením
do rovnosti (2) dostáváme
(22) |A(0)| =
K
{1,2,...,n}
(-1)|K|
 (n - |K|)! .
Princip inkuze a exkluze ­ p.14/15

Princip inkluze a exkluze - příklady V
Jednotliví sčítanci v sumě (22) závisí pouze na
|K|.
Princip inkuze a exkluze ­ p.15/15

Princip inkluze a exkluze - příklady V
Jednotliví sčítanci v sumě (22) závisí pouze na
|K|.
Pro každé   {0, 1, 2, . . . , n} je počet těch
sčítanců, v nichž |K| = , roven ( n
 ) .
Princip inkuze a exkluze ­ p.15/15

Princip inkluze a exkluze - příklady V
Jednotliví sčítanci v sumě (22) závisí pouze na
|K|.
Pro každé   {0, 1, 2, . . . , n} je počet těch
sčítanců, v nichž |K| = , roven ( n
 ) . Je tedy
(222) |A(0)| =
n
=0
(-1)

n


(n - )!
=
n
=0
(-1)

n!
!
Princip inkuze a exkluze ­ p.15/15

Princip inkluze a exkluze - příklady V
Jednotliví sčítanci v sumě (22) závisí pouze na
|K|.
Pro každé   {0, 1, 2, . . . , n} je počet těch
sčítanců, v nichž |K| = , roven ( n
 ) . Je tedy
(222) |A(0)| =
n
=0
(-1)

n


(n - )!
=
n
=0
(-1)

n!
!

n!
e .
Princip inkuze a exkluze ­ p.15/15