5600235757

6 Metody zliczania zbiorów i funkcji 14

6.2 Zasada dodawania

Twierdzenie 6.3 (Zasada dodawania). Dla dowolnych parami rozłącznych zbiorów skończonych 4i,42,...,4_n mamy

\A\ U A2 U • • • U A_n\ —- |>4.i| + |^4.21 + • • • + |4_n|.

Dowód. Dla n = 1 dowód jest trywialny. Dla n = 2 załóżmy, że \A\ \ = p i | 421 = q. Elementy A\ możemy ponumerować 1,2,... ,p, natomiast elementy A2 ponumerujemy p + l,p + 2,... ,p + q. Ponieważ A\ fi A2 = 0, więc w A\ nie ma elementów z A2 i żaden element nie był numerowany dwukrotnie. Tak więc

\A\ U -A21 = P + Q = \Ai \ + I-A2I-

Załóżmy teraz indukcyjnie dla n = k, że

\A\ U A2 U • • • U Ak| = |-4i| -h |-421 +----1- \Af.\.

Dla n = k + 1 mamy

\A₁UA₂U---UA_kUA_k+1\ = \(A₁UA₂U---UA_k)uA_k+1\ =

|4i U A2 U • • • U A_k| + |4fc₊i| = |4i| + |-42| H-----h |4fc| + |4/c+i|

ponieważ w A_k+\ nie ma żadnego elementu ze zbiorów A\, A2,..., A_k, to znaczy (4i U 4.2 U • • • U A_k) f~l A_k+i = 0 i postępujemy jak dla dwóch zbiorów.    □

Przykład 6.4. Powiedzmy, że mamy 5 czerwonych guzików i 7 niebieskich. Zbiór 4 czerwonych guzików jest rozłączny ze zbiorem B niebieskich guzików. Zatem z zasady dodawania 6.3, aby policzyć ile jest w sumie guzików, czyli w zbiorze 4 U B, dodajemy |4| + |B| = 5 + 7 = 12.

6.3 Metoda włączania-wyłączania

Twierdzenie 6.5 (Metoda włączania-wyłączania dla dwóch zbiorów). Dla dowolnych zbiorów skończonych 4, B mamy

\A U B\ = |4| 4- \B\ — |4 fi B\.

Dowód. Zliczając elemety zbioru AU B dwukrotnie liczymy te elementy, które występują jednocześnie w 4 i w B, czyli w 4 fi B. Tak więc od sumy |4| + \B\ musimy odjąć ilość elementów w przekroju 4 fi B.    □

Inny dowód można przeprowadzić w oparciu o zasadę dodawania 6.3, gdy zauważymy, że po pierwsze, zbiory 4 \ B, AC\B oraz B \ A są parami rozłączne i w sumie dają 4UB, po drugie, |(4 \B)U(4fl B)\ = |4| i | (B \ 4) U (4 fi B)\ = |B|. A więc

|4 U B\ = |(4 \ B) U (4 n B) U (B \ 4)| = |4 \ B\ + \A fi B\ + \B \ A\ =

(|4 \ B\ + |4 n B|) + (|B \ 4| + |4 n B\) -\AnB\ = |4| + \B\ - \A n B\.