Skip to Content

Wariacje

pon., 09/13/2010 - 11:58 — ciebie

Zdefiniujemy teraz jeszcze jedno działanie na zbiorach. Jeśli dane są dwa zbiory skończone A i B , to iloczynem kartezjańskim tych zbiorów nazywamy zbiór, którego elementami są pary elementów: jednego ze zbioru A i drugiego ze zbioru B . Parę takich elementów oznaczamy symbolem (a,b).

Dwie pary uporządkowane (a,b) i (c,d) są równe wtedy i tylko wtedy, gdy a = c i b = d. W szczególności para (a,b) na ogół jest różna od pary (b,a). Równość zachodzi wtedy i tylko wtedy, gdy a = b. (Dlatego właśnie używa się nazwy para uporządkowana - kolejność elementów ma tu znaczenie.)

Iloczyn kartezjański zbiorów A i B oznaczamy symbolem \(A \times B.\) Możemy więc zapisać:

\(A \times B = \{ (a,b):\, a \in A \, \land \, b \in B\} .\)

Liczba elementów iloczynu kartezjańskiego dwóch zbiorów skończonych A i B (zbiór A ma m elementów, a zbiór B ma n elementów) wyraża się prostym wzorem:

\(|A \times B| = m \cdot n = |A| \cdot |B|.\)


Wyprowadzenie tego wzoru też nie jest trudne.
Przypuśćmy bowiem, że zbiór A ma m elementów, a zbiór B ma n elementów:

\(A=\{ a_1,a_2,a_3,\ldots ,a_ m\} , \quad B=\{ b_1,b_2,b_3,\ldots ,b_ n\} .\)

Wtedy elementy iloczynu kartezjańskiego można wypisać w następującej tablicy:

\(\begin{array}{ccccc} (a_1,b_1) & (a_1,b_2) & (a_1,b_3) & \ldots & (a_1,b_ n) \\ (a_2,b_1) & (a_2,b_2) & (a_2,b_3) & \ldots & (a_2,b_ n) \\ (a_3,b_1) & (a_3,b_2) & (a_3,b_3) & \ldots & (a_3,b_ n) \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ (a_ m,b_1) & (a_ m,b_2) & (a_ m,b_3) & \ldots & (a_ m,b_ n) \\ \end{array}\)

Ta tablica ma m wierszy, w każdym wierszu znajduje się n par. Mamy zatem łącznie \(m \cdot n\) par uporządkowanych; tak właśnie określa się mnożenie dwóch liczb. Te pary to są wszystkie elementy iloczynu kartezjańskiego. Zatem

\(|A \times B| = m \cdot n = |A| \cdot |B|.\)


Reguła mnożenia - najprostsza wersja

Wzór na liczbę elementów iloczynu kartezjańskiego to w istocie jeden z najważniejszych faktów w kombinatoryce, który zasługuje na wyraźne sformułowanie w potocznym języku i na oddzielną nazwę.

Twierdzenie (reguła mnożenia):

Przypuśćmy, że mamy do wykonania dwie czynności. Pierwsza z nich kończy się jednym z m możliwych wyników, druga zaś jednym z n możliwych wyników.

Wtedy wykonanie jednej czynności po drugiej zakończy się jednym z \(m \cdot n\) wyników (tu wynikiem jest oczywiście para: wynik pierwszej czynności i wynik drugiej czynności).

Popatrzmy teraz na typowy prosty przykład, w którym można zastosować regułę mnożenia.

Zadanie 1.4.1: Mamy wybrać dwuosobową delegację parlamentu, w skład której ma wejść jeden poseł i jeden senator. Na ile sposobów możemy wybrać taką delegację?

Rozwiązanie:
Posła można wybrać na 460 sposobów, senatora na 100 sposobów. Mamy wykonać po sobie dwie czynności: wybrać posła, a następnie wybrać senatora. Liczba możliwych wyników jest więc równa \(460 \cdot 100 = 46000\) . Tyle właśnie jest możliwych sposobów wyboru delegacji.
∎


Uogólnione wersje reguły mnożenia

Regułę mnożenia można uogólnić na więcej czynności.

Twierdzenie (uogólniona reguła mnożenia):

Przypuśćmy, że mamy do wykonania n czynności, przy czym pierwsza kończy się jednym z k1 wyników, druga jednym z k2 wyników itd, aż do n -tej czynności, która kończy się jednym z kn wyników. Wówczas wykonanie tych wszystkich czynności jedna po drugiej zakończy się jednym z \(k_1 \cdot k_2 \cdot \ldots \cdot k_ n\) wyników (wynikiem jest tu oczywiście ciąg uporządkowany n wyników: pierwszej czynności, drugiej czynności itd. aż do n-tej czynności).

Zadanie 1.4.2: Rzucamy trzy razy kostką do gry i zapisujemy kolejno otrzymywane wyniki rzutów. Wynikiem naszego doświadczenia jest więc trójka liczb, każda z nich jest liczbą naturalną z przedziału \(\langle 1;6 \rangle\) . Ile jest takich wyników?


Rozwiązanie:
Mamy tu trzy czynności: rzut kostką za pierwszym razem, za drugim razem i za trzecim razem. Pierwsza czynność kończy się jednym z sześciu wyników, druga i trzecia też jednym z sześciu wyników. Z reguły mnożenia wynika, że łączna liczba wyników jest równa \(6 \cdot 6 \cdot 6 = 6^3 = 216\) .
∎

Regułę mnożenia można uogólnić w jeszcze jeden sposób, tak, aby rozszerzyć możliwości jej stosowania. Okazuje się, że zbiór wyników drugiej czynności wcale nie musi być ustalony. Ważne jest tylko, by ustalona była liczba tych wyników.

Twierdzenie (reguła mnożenia, wersja 2):

Przypuśćmy, że mamy do wykonania po sobie dwie czynności. Pierwsza kończy się jednym z m wyników. Wyniki drugiej czynności nie są ustalone, jak to było poprzednio, ale zależą teraz od wyniku pierwszej. Jest jednak tak, że - niezależnie od wyniku pierwszej czynności! - zawsze druga czynność kończy się jednym z n wyników. Wtedy wykonanie tych czynności po sobie, najpierw pierwszej, potem drugiej, zakończy się jednym z \(m \cdot n\) wyników.

Zadanie 1.4.3: Mamy 5 kart, na każdej z nich jest napisana jedna liczba od 1 do 5. Będziemy losować kolejno dwie karty, przy czym kartę wylosowaną za pierwszym razem odkładamy na bok, tak że nie możemy jej wylosować po raz drugi. W skrócie będziemy mówić, że losujemy kolejno dwie liczby ze zbioru liczb {1,2,3,4,5} . Wylosowane liczby zapisujemy, z uwzględnieniem kolejności (wynikiem całego doświadczenia jest więc para liczb). Ile różnych wyników można otrzymać w takim losowaniu?


Rozwiązanie:
Pierwsza czynność to oczywiście wylosowanie pierwszej liczby. Możemy otrzymać jeden z pięciu wyników. A jak wygląda druga czynność? Druga czynność polega na wylosowaniu jednej karty spośród pozostałych kart (zauważmy, że w zależności od tego, jaką kartę wylosowaliśmy za pierwszym razem, za drugim razem losujemy z innego zbioru kart). Zatem zbiór możliwych wyników drugiej czynności zależy od wyniku pierwszej. Jeśli na przykład za pierwszym razem wylosujemy liczbę 2, to za drugim losujemy jedną liczbę ze zbioru {1,3,4,5} . Jeśli zaś za pierwszym razem wylosujemy liczbę 5, to za drugim losujemy ze zbioru {1,2,3,4} . Zbiory, z których losujemy, są różne: w pewnym sensie te drugie czynności są różne; wprawdzie druga czynność zawsze polega na losowaniu kart z pewnego zbioru, ale te zbiory mogą się różnić. Zauważmy jednak, że za drugim razem możemy otrzymać jeden z 4 wyników, niezależnie od wyniku pierwszego losowania. Po pierwszym losowaniu z naszego zbioru ubywa jedna liczba, zostają więc zawsze cztery liczby. Uogólniona reguła mnożenia mówi teraz, że łącznie możemy otrzymać jeden z \(5 \cdot 4=20\) wyników.
∎

W podobny sposób postępujemy, jeśli mamy wykonać więcej czynności.

Twierdzenie (uogólniona reguła mnożenia, wersja 2):
Jeśli pierwsza czynność kończy się jednym z k1 wyników, druga czynność, niezależnie od wyniku pierwszej, kończy się jednym z k2 wyników, trzecia czynność, niezależnie od wyników pierwszych dwóch czynności, kończy się jednym z k3 wyników i tak dalej, aż do n-tej czynności, która niezależnie od wyników pierwszych n − 1 czynności kończy się jednym z kn wyników, to wykonanie tych czynności po kolei da jeden z \(k_1 \cdot k_2 \cdot k_3 \cdot \ldots \cdot k_ n\) wyników.


Przykłady (zadań i typowych błędów)

Zadanie 1.4.4: Ile jest liczb trzycyfrowych mających różne cyfry (dokładniej: żadna cyfra nie może się powtórzyć)?


Rozwiązanie:
Pierwszą cyfrę możemy wybrać na 9 sposobów (nie możemy wybrać zera). Drugą cyfrę też możemy wybrać (niezależnie od wyboru pierwszej) na 9 sposobów (nie możemy wybrać cyfry stojącej już na pierwszym miejscu, możemy natomiast wybrać zero). Wreszcie trzecią cyfrę możemy wybrać na 8 sposobów (mamy do wyboru 10 cyfr, ale nie możemy wybrać żadnej z cyfr stojących na pierwszych dwóch miejscach). Z uogólnionej reguły mnożenia wynika, że łącznie mamy \(9 \cdot 9 \cdot 8 = 648\) sposobów wyboru takiej liczby; tyle więc jest trzycyfrowych liczb o trzech różnych cyfrach.
∎

Przestroga. Przy obliczaniu liczby możliwych wyników uczniowie często popełniają błąd polegający na dwukrotnym policzeniu tej samej możliwości. Popatrzmy na następujące dwa zadania.

Zadanie 1.4.5: Ile jest trzycyfrowych liczb naturalnych o trzech różnych cyfrach i takich, że jedną z tych cyfr jest 9 i żadna z pozostałych dwóch cyfr nie jest zerem?


Rozwiązanie:
Pierwsza czynność polega na wyborze miejsca, na którym stoi cyfra 9. Mamy do wyboru 3 możliwości. Następnie na pierwszym wolnym miejscu zapisujemy jedną z cyfr od 1 do 8 i wreszcie na ostatnim wolnym miejscu wpisujemy jedną z cyfr od 1 do 8, różną od ostatnio wpisanej. Druga czynność kończy się zatem jednym z 8 wyników, a trzecia jednym z 7 wyników. Z uogólnionej reguły mnożenia wynika zatem, że otrzymujemy jeden z \(3 \cdot 8 \cdot 7 = 168\) wyników. Tyle jest więc szukanych liczb.
∎

Zadanie 1.4.6: Ile jest trzycyfrowych liczb naturalnych o tej własności, że wśród cyfr danej liczby jest co najmniej jedna 9 i żadna cyfra nie jest zerem?


Rozwiązanie (z błędem):
Taki błąd jest niezwykle często popełniany przez uczniów rozwiązujących to zadanie.

Wiemy, że jedną z cyfr jest 9; możemy ją umieścić na jednym z trzech miejsc. Na każdym z pozostałych miejsc może stać jedna z dziewięciu cyfr (oprócz zera). Mamy zatem trzy czynności: umieszczenie cyfry 9 na jednym z trzech miejsc, umieszczenie dowolnej cyfry różnej od zera na pierwszym wolnym miejscu i wreszcie umieszczenie dowolnej cyfry różnej od zera na pozostałym wolnym miejscu. Pierwsza czynność kończy się jednym z trzech wyników, każda z dwóch następnych kończy się jednym z 9 wyników. Korzystając z reguły mnożenia dostajemy łącznie \(3 \cdot 9 \cdot 9 = 243\) możliwych wyników, a więc tyle jest szukanych liczb trzycyfrowych.
∎


A gdzie jest błąd w tym rozumowaniu?
Otóż okazuje się, że niektóre liczby zostały policzone wielokrotnie.

Przypuśćmy, że w pierwszej czynności umieściliśmy cyfrę 9 na pierwszym miejscu, a w czynnościach drugiej i trzeciej na pozostałych miejscach umieściliśmy kolejno cyfry 5 i 9. Otrzymaliśmy liczbę 959. Przypuśćmy teraz, że w czynności pierwszej umieściliśmy cyfrę 9 na trzecim miejscu, a w czynnościach drugiej i trzeciej umieściliśmy na pierwszych dwóch miejscach kolejno cyfry 9 i 5. Znów otrzymaliśmy liczbę 959. Ta liczba została więc w powyższym sposobie zliczania policzona dwukrotnie.

Zobaczmy teraz cztery poprawne sposoby rozwiązania tego zadania.


Sposób I.
Najpierw policzymy wszystkie liczby trzycyfrowe, w których nie występuje cyfra zero. Na każdym z trzech miejsc możemy umieścić jedną z 9 cyfr; łącznie mamy zatem \(9 \cdot 9 \cdot 9 = 9^3 = 729\) liczb. Teraz policzymy wszystkie liczby, w których nie występują cyfry 0 i 9. Tym razem na każdym z trzech miejsc możemy umieścić jedną z 8 cyfr; łącznie mamy zatem \(8 \cdot 8 \cdot 8 = 8^3 = 512\) liczb. Liczby, o które chodzi w zadaniu to oczywiście liczby należące do pierwszej grupy (liczby, w których nie występuje cyfra 0) i nie należące do drugiej grupy (w której są liczby również bez zera). Stąd wynika, że liczb, o które chodzi w zadaniu, jest 729 − 512 = 217 .
∎


Sposób II.
Najpierw policzymy liczby, w których jest tylko jedna cyfra 9. Tym razem zastosujemy metodę znaną z zadań 18 i 19 oraz z powyższego błędnego rozwiązania. Tym razem jednak użycie tej metody będzie poprawne, gdyż jest tylko jedna cyfra 9. Możemy umieścić ją na jednym z trzech miejsc. Na każdym z pozostałych dwóch miejsc możemy umieścić jedną z ośmiu cyfr; mamy zatem łącznie \(3 \cdot 8 \cdot 8 = 192\) takie liczby. Następnie policzymy liczby, w których występują dwie cyfry 9. Najpierw wybieramy miejsce, na którym nie ma dziewiątki. Mamy trzy możliwości. Na tym miejscu stawiamy jedną z ośmiu cyfr, a na pozostałych oczywiście dziewiątki. Mamy zatem \(3 \cdot 8 = 24\) możliwości. Wreszcie zauważamy, że jest tylko jedna liczba zapisana za pomocą trzech dziewiątek. Korzystamy teraz z reguły dodawania, dostając łącznie 192 + 24 + 1 = 217 liczb.
∎


Sposób III.
Poprawimy rozwiązanie błędne. Dostaliśmy wtedy wynik 243. Pamiętamy jednak, że niektóre liczby zostały policzone wielokrotnie: liczby z dwiema dziewiątkami były policzone po dwa razy, a liczba 999 nawet trzy razy. Tak jak w sposobie II obliczamy, że mamy 24 liczby z dwiema dziewiątkami. Zatem liczb, które nas interesują jest 243 − 24 − 2 = 217 .
∎


Sposób IV.
Skorzystamy z zasady włączeń i wyłączeń. Niech A będzie zbiorem liczb bez zera i z dziewiątką na pierwszym miejscu, B zbiorem liczb bez zera i z dziewiątką na drugim miejscu i wreszcie C zbiorem bez zera i z dziewiątką na trzecim miejscu. Zbiorem liczb, które nas interesują, jest oczywiście zbiór \(A \cup B \cup C\) . Nietrudno teraz zauważyć, że:

\(\begin{array}{ll}& |A| = |B| = |C| = 9^2 = 81, \\ & |A \cap B| = |A \cap C| = |B \cap C| = 9, \\ & |A \cap B \cap C| = 1. \\ \end{array}\)

Z zasady włączeń i wyłączeń dostajemy

\(\begin{array}{ll} |A \cup B \cup C| & = |A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A \cap B \cap C| = \\ & = 3 \cdot 81 - 3 \cdot 9 + 1 = 243 - 27 + 1 = 217. \\ \end{array}\)
∎

Zadanie 1.4.7: Ile jest ciągów długości n o wyrazach ze zbioru A = {1,2,3} , w których występują wszystkie liczby należące do A ?


Rozwiązanie:
Skorzystamy z zasady włączeń i wyłączeń. Obliczymy jednak, ile jest ciągów, które nie spełniają warunku podanego w zadaniu. Oznaczmy przez Ai (dla i = 1,2,3 ) zbiór tych ciągów, w których nie występuje liczba i . Wówczas z reguły mnożenia wynika, że | A1 | = | A2 | = | A3 | = 2n. Na przykład, w przypadku zbioru A1 na każdym z n miejsc możemy postawić jedną z dwóch liczb: 2 lub 3. Następnie \(|A_1 \cap A_2| = |A_1 \cap A_3| = |A_2 \cap A_3| = 1.\) Na przykład, w przypadku zbioru \(A_1 \cap A_2\) na każdym z n miejsc musimy postawić liczbę 3. Wreszcie \(A_1 \cap A_2 \cap A_3 = \emptyset\) . Teraz z zasady włączeń i wyłączeń wynika, że
\(|A_1 \cup A_2 \cup A_3| = 3 \cdot 2^ n - 3.\)
Ponieważ z reguły mnożenia łatwo wynika, że istnieje 3n wszystkich ciągów długości n o wyrazach ze zbioru A , więc liczba ciągów, o które chodzi w zadaniu, jest równa \(3^ n - 3 \cdot 2^ n + 3.\)
∎



Theme by Dr. Radut.