Jeśli dany jest zbiór skończony A , to liczbę jego elementów będziemy oznaczać symbolem | A | .
Wspomnieliśmy wyżej, że najprostszą metodą odpowiedzi na pytanie o liczbę elementów zbioru jest po prostu policzenie tych elementów. W tym rozdziale przyjrzymy się tej metodzie. Popatrzmy najpierw na parę prostych przykładów.
Przykłady
Zadanie 1.1.1: Ile elementów ma zbiór
\(\{ 1,2,3,4,\ldots ,117\} ?\)
∎
Zadanie 1.1.2: Ile elementów ma zbiór
\(\{ 14, 15, 16, \ldots , 103\} ?\)
∎
Zadanie 1.1.3: Ogólnie: ile elementów ma zbiór
\(\{ k,k+1,k+2,\ldots ,n\} ,\)
gdzie n > k ?
\(\Big|\{ k,k+1,k+2,\ldots ,n\} \Big| = n-k+1.\)
Uczniowie często popełniają błąd i piszą, że ten zbiór ma n − k elementów.
∎
Popatrzmy na następne przykłady.
Zadanie 1.1.4: Ile elementów ma zbiór
\(\{ 1, 5, 9, 13, \ldots , 201\} ?\)
\(\{ 4k+1:\, 0 \le k \le 50\} .\)
Liczba k przebiega 51 różnych wartości: od 0 do 50. Czy stąd wynika, że nasz zbiór ma 51 elementów? W naszym przypadku tak, gdyż różnym liczbom k odpowiadają różne elementy naszego zbioru. Jeśli bowiem \(k \ne l\) , to \(4k \ne 4l\) i stąd \(4k+1 \ne 4l+1\) . Zatem
\(\Big|\{ 1, 5, 9, 13, \ldots , 201\} \Big| = 51.\)
∎
Może się jednak zdarzyć, że reguła opisująca zbiór zostanie dobrana tak, że pewne elementy zbioru zostaną przez nią wskazane wielokrotnie. Popatrzmy na kolejny przykład.
Zadanie 1.1.5: Ile elementów ma zbiór:
\(\{ k^2-8k+20:\, 1 \le k \le 6\} ?\)
\(\begin{array}{ccc} k & \quad & k^2-8k+20 \\ 1 & & 13 \\ 2 & & 8 \\ 3 & & 5 \\ 4 & & 4 \\ 5 & & 5 \\ 6 & & 8 \\ \end{array}\)
Zmienna k przebiega 6 wartości, ale wzór k2 − 8k + 20 daje nam dla tych k tylko 4 różne wartości. Zatem
\(\{ k^2-8k+20:\, k\in \mathbb {N} \, \land \, 1 \le k \le 6\} = \{ 4,5,8,13\}\)
i ten zbiór ma tylko 4 elementy.
∎
Widzimy już jedną trudność. Przypuśćmy, że nasz zbiór jest opisany w następujący sposób:
\(\{ F(i):\, k \le i \le n\} .\)
W tej definicji F(i) jest pewnym wzorem dającym wartości rzeczywiste dla liczb naturalnych i . Jeśli dla różnych liczb naturalnych i z przedziału \(\langle k;n \rangle\) obliczone wartości F(i) są różne, to ten zbiór ma n − k + 1 elementów:
\(\Big|\{ F(i):\, k \le i \le n\} \Big| = n-k+1.\)
Jeśli jednak pewne wartości się powtarzają, to obliczenie, ile wśród nich jest różnych liczb, może okazać się zadaniem bardzo trudnym.
Liczenie elementów zbioru musi zatem spełniać dwa warunki:
- wszystkie elementy zbioru muszą być policzone,
- każdy element musi być policzony tylko jeden raz.
Jeżeli te dwa warunki są spełnione, to liczbę elementów zbioru otrzymujemy natychmiast: patrzymy tylko, ile liczb naturalnych zostało zużytych. Najczęściej liczymy elementy zaczynając od 1. Wtedy patrzymy, na której liczbie naturalnej skończyliśmy liczenie. Czasami jednak wygodniejsze jest rozpoczynanie liczenia od innej liczby. Popatrzmy na przykład.
Zadanie 1.1.6: Ile elementów ma zbiór
\(\{ 25, 28, 31, 34, \ldots , 100\} ?\)
\(\{ 3k+1:\, 8 \le k \le 33\} .\)
Najwygodniej zliczać jego elementy numerując je liczbami naturalnymi od 8 do 33. Jest 26 takich liczb, zatem nasz zbiór ma 26 elementów.
∎
Dygresja: dlaczego popełniamy błędy w kombinatoryce?
O błędach w kombinatoryce. Naruszenie jednej (lub nawet obu!) zasad zliczania jest najczęstszym źródłem błędów w zadaniach kombinatorycznych. Zdarza się, że znajdujemy metodę zliczania elementów danego zbioru i nie zauważamy, że przy tej metodzie pomijamy pewne elementy. Oczywiście otrzymujemy wtedy błędny wynik. Zdarza się też, że pewne elementy liczymy dwukrotnie (lub nawet więcej razy). Też otrzymujemy błędny wynik. Niestety zdarza się także, że o pewnych elementach zapominamy, za to inne liczymy dwukrotnie i wynik się zgadza. Rozwiązanie jest jednak błędne, gdyż niepoprawna była metoda zliczania.
O liczeniu jako takim. Przyjrzyjmy się bliżej samej czynności liczenia. Jeśli mamy policzyć zapałki w pudełku, to możemy wyjmować po jednej, odliczając na głos lub w myśli kolejne liczby naturalne. Liczba, na której skończyliśmy, jest liczbą elementów naszego zbioru. Co naprawdę robiliśmy (z matematycznego punktu widzenia)? Otóż łączyliśmy w pary elementy dwóch zbiorów: naszego zbioru i pewnego podzbioru zbioru liczb naturalnych. Zobaczymy to łączenie w pary na innym przykładzie, nieco mniejszego zbioru. Jeśli liczymy elementy zbioru
\(A = \{ \clubsuit , \diamondsuit , \heartsuit , \spadesuit \} ,\)
to wskazujemy palcem kolejne symbole, odliczając: 1, 2, 3, 4. Robiąc to, łączymy w pary elementy naszego zbioru A i zbioru {1,2,3,4} , na przykład w następujący sposób:
\((1,\clubsuit ), \quad (2,\diamondsuit ), \quad (3,\heartsuit ), \quad (4,\spadesuit ).\)
Oczywiście to łączenie w pary musi być zgodne z zasadami (1) i (2): każdy element zbioru A musi być w parze z dokładnie jednym elementem zbioru {1,2,3,4} i na odwrót, każdy element zbioru {1,2,3,4} musi być w parze z dokładnie jednym elementem zbioru A . Jeśli takie łączenie w pary się powiedzie, to powiemy, że zbiór A ma cztery elementy: dlatego, że zbiór {1,2,3,4} ma cztery elementy.
Co zatem oznacza zdanie zbiór A ma n elementów? Jak widać, mówimy, że zbiór skończony A ma n elementów, jeśli elementy tego zbioru można tak połączyć w pary z elementami zbioru \(\{ 1,2,3,\ldots ,n\}\) , by każdy element zbioru A był w parze z dokładnie jednym elementem zbioru \(\{ 1,2,3,\ldots ,n\}\) , różne elementy zbioru A były w parach z różnymi elementami zbioru \(\{ 1,2,3,\ldots ,n\}\) oraz wszystkie elementy zbioru \(\{ 1,2,3,\ldots ,n\}\) zostały wykorzystane.
Zasada równoliczności
Możemy teraz sformułować pierwszą ze wspomnianych zasad ułatwiających zliczanie elementów zbiorów.
| Twierdzenie (zasada równoliczności): |
|
Jeśli mamy dane dwa zbiory A i B i ich elementy możemy połączyć w pary w taki sposób, że każdy element zbioru A jest w parze z dokładnie jednym elementem zbioru B i każdy element zbioru B jest w parze z dokładnie jednym elementem zbioru A , to zbiory A i B mają tyle samo elementów (są równoliczne). |
Zbiór \(\{ 1,2,3,\ldots ,n\}\) jest wzorcem zbioru n -elementowego. Zatem liczenie elementów zbioru A polega na znalezieniu takiego wzorca, z którym zbiór A jest równoliczny.
Pokażemy przykład zastosowania zasady równoliczności.
Zadanie 1.1.7: Przypuśćmy, że rzucamy 25 razy monetą, zapisując wyniki rzutów: piszemy O , gdy wypadnie orzeł i R , gdy wypadnie reszka. Wynikiem całego doświadczenia jest ciąg 25 liter. Jest bardzo wiele takich ciągów, niedługo dowiemy się, jak je policzyć. Nie to jest teraz jednak istotne. Chcemy wiedzieć tylko, czy więcej jest ciągów, w których jest parzysta liczba liter O , czy też więcej jest ciągów, w których jest nieparzysta liczba liter O .
∎
\((a_1,a_2,a_3,\ldots ,a_{25})\)
ustawimy ciąg
\((b_1,b_2,b_3,\ldots ,b_{25})\)
o tej własności, że dla każdego i litera bi jest różna od litery ai . To znaczy, że jeśli ai jest literą O , to bi jest literą R oraz jeśli ai jest literą R , to bi jest literą O . Zauważmy następnie, że w jedną parę łączymy dwa ciągi, z których jeden ma parzystą liczbę liter O i nieparzystą liczbę liter R , a drugi odwrotnie: ma parzystą liczbę liter R i nieparzystą liczbę liter O . Wynika to stąd, że w każdym ciągu jest w sumie 25 liter; jeśli wśród nich jest parzysta liczba liter O , to jest też nieparzysta liczba liter R. Gdy teraz zamienimy każdą literę na "przeciwną" (tzn. O na R i odwrotnie), to otrzymamy ciąg stojący w parze z naszym ciągiem. Będzie on miał parzystą liczbę liter R i nieparzystą liczbę liter O .
Ustawmy wreszcie ciągi w parach tak, by na pierwszym miejscu stał ciąg mający parzystą liczbę liter O . Połączyliśmy w ten sposób w pary elementy dwóch zbiorów: zbioru tych ciągów, w których jest parzysta liczba liter O i zbioru tych ciągów, w których jest nieparzysta liczba liter O . Te zbiory są zatem równoliczne.
Opisany wyżej sposób łączenia w pary zobaczymy na przykładzie ciągów długości 3:
\((RRR,OOO), \quad (OOR,RRO), \quad (ORO,ROR), \quad (ROO,ORR).\)
W powyższym rozwiązaniu istotne było to, że łączna liczba rzutów była liczbą nieparzystą. Gdybyśmy bowiem wykonywali 24 rzuty monetą i łączyli ciągi w pary w taki sam sposób, to np. ciąg samych liter O byłby połączony z ciągiem samych liter R . Oba te ciągi mają parzystą liczbę liter O : pierwszy ma 24 takie litery, drugi ma ich zero. Pomysł, by łączyć w pary ciągi mające parzystą liczbę liter O z ciągami mającymi nieparzystą liczbę liter O, nie powiódł się. Okazuje się natomiast, że niezależnie od tego, czy liczba rzutów jest parzysta czy nieparzysta, liczba tych ciągów, w których jest parzysta liczba liter O jest równa liczbie tych ciągów, w których jest nieparzysta liczba liter O . Dowód jednak musi być inny. Taki dowód niezależny od tego, czy liczba rzutów jest parzysta czy nie, jest pokazany w drugim sposobie rozwiązania zadania.
\((a_1,a_2,a_3,\ldots ,a_{25})\)
ustawimy ciąg
\((b_1,b_2,b_3,\ldots ,b_{25})\)
o tej własności, że dla każdego \(i \le 24\) litera bi jest taka sama jak litera ai , natomiast litera b25 jest różna od litery a25 . Inaczej mówiąc, ciągi umieszczone w tej samej parze różnią się tylko ostatnim wyrazem. Jest wtedy oczywiste, że jeśli w jednym ciągu z tej samej pary jest parzysta liczba liter O , to w drugim jest nieparzysta liczba liter O .
Ustawiamy ciągi w parach tak jak poprzednio: na pierwszym miejscu w parze stawiamy ciąg mający parzystą liczbę liter O . Na drugim miejscu będzie więc stał ciąg mający nieparzystą liczbę liter O . Znów połączyliśmy w pary elementy dwóch zbiorów: zbioru tych ciągów, w których jest parzysta liczba liter O i zbioru tych ciągów, w których jest nieparzysta liczba liter O . Te zbiory są zatem równoliczne.
Opisany wyżej sposób łączenia w pary zobaczymy na przykładzie ciągów długości 4:
\(\begin{array}{c} (OOOO,OOOR), \quad (OORR,OORO), \quad (OROR,OROO), \quad (ORRO,ORRR), \\ (ROOR,ROOO), \quad (RORO,RORR), \quad (RROO,RROR), \quad (RRRR,RRRO). \\ \end{array}\)
Zauważmy na koniec, że dzięki zasadzie równoliczności mogliśmy pokazać, że pewne dwa zbiory mają tyle samo elementów, nie licząc tych elementów. Nadal nie wiemy, ile elementów ma każdy z tych zbiorów, wiemy jednak, że tyle samo.