7090996917
W. Guzicki: Zadania z kombinatoryki
Tak więc na przykład
(1,1,0,1,0,0,0,1) € S4(8), (1,1,1,1) € S4(4), (0,0,0,0) € S0(4).
Często, gdy mamy do czynienia z ciągami liczbowymi, których wyrazy są liczbami naturalnymi jednocyfrowymi (to znaczy wyrazy należą do zbioru {0,1,2,..., 9}), będę opuszczał w zapisie ciągu nawiasy i przecinki. Tak więc powyższe przykłady mogę zapisać w sposób następujący:
lioioooi e S4(8), inieS4(4), ooooeS0(4).
Symbolem P(A) oznaczam zbiór wszystkich podzbiorów zbioru skończonego A, symbolem Pk(A) oznaczam zbiór wszystkich podzbiorów ^-elementowych zbioru A:
P(A) = {X : XCA}, Pk(A) = {X e P(A): \X\ = fc}.
Ponadto będę używał oznaczeń:
P(n) = P([n]), P„(ń) = P*(M).
2. Podstawowe zasady kombinatoryczne
Przy zliczaniu elementów zbiorów skończonych będę stosował następujące trzy zasady kombinatoryczne.
• Zasada równoliczności. Przypuśćmy, że elementy dwóch zbiorów skończonych A i B można połączyć w pary (o, b) tak, że spełnione są następujące własności:
(Rl) w każdej parze (o, b) element a należy do zbioru A i element b należy do zbioru B,
(R2) każdy element zbioru A znajduje się w dokładnie jednej parze (a, b),
(R3) każdy element zbioru B znajduje się w dokładnie jednej parze (a, b).
Wówczas zbiory A i B mają tyle samo elementów: |A| = |B|.
• Reguła dodawania. Przypuśćmy, że możemy wykonać dwie czynności. Pierwsza z nich kończy się jednym z m wyników, druga kończy się jednym z n wyników. Żaden z wyników pierwszej czynności nie jest jednocześnie wynikiem drugiej czynności. Załóżmy następnie, że wykonujemy jedną z tych dwóch czynności. Otrzymamy wówczas jeden z m + n wyników.
• Reguła mnożenia. Przypuśćmy, że możemy wykonać dwie czynności. Pierwsza z nich kończy się jednym z m wyników, druga — niezależnie od wyniku pierwszej czynności — kończy się jednym z n wyników. Załóżmy następnie, że wykonujemy obie czynności, najpierw pierwszą, a następnie drugą. Otrzymamy wówczas jeden z m ■ n wyników. Wynikiem wykonania obu tych czynności jest oczywiście para (a,b), gdzie a jest wynikiem pierwszej czynności i 6 jest wynikiem drugiej czynności.
Zasada równoliczności, w terminologii teoriomnogościowej, oczywiście mówi, że jeśli istnieje funkcja
/ : A B,
to |.A| = |B|. Reguła dodawania mówi, że jeśli zbiory A i B są rozłączne, to \AUB\ = \A\ + \B\.
Reguła mnożenia w najprostszej wersji, w której zbiór wyników drugiej czynności nie zależy od wyniku pierwszej czynności, mówi, że
\AxB\ = \A\-\B\.
W wersji ogólnej przypuśćmy, że A jest zbiorem wyników pierwszej czynności oraz dla każdego a € A zbiór Ba jest zbiorem tych wyników drugiej czynności, które mogą być uzyskane wtedy, gdy pierwsza czynność zakończy się wynikiem a. Reguła mnożenia mówi wówczas, że jeśli |j4| = m oraz \Ba\ = n dla każdego a € A, to
|{(a, b) : a € A oraz b € Ba}| = m ■ n.
Warszawa, 19-20 października 2013 r.
Wyszukiwarka
Podobne podstrony:
Habermas10 116 Rozdział III Tak więc na przykład F. Michelman dostrzega w amerykańskiej tradycji kon
nych maniaków, ale i jako myślicieli torujących drogę naukowemu myśleniu. Tak więc na przykład
W. Guzicki: Zadania z kombinatoryki podzielna przez 7, więc do otrzymania odpowiedzi na pierwsze pyt
W. Guzicki: Zadania z kombinatoryki Rozwiązanie. Postępujemy tak samo jak w zadaniu 10. Mamy dwa spo
12 W. Guzicki: Zadania z kombinatoryki Obszar o numerze III, zawarty wewnątrz lewego okręgu i na zew
W. Guzicki: Zadania z kombinatoryki 13 Te obszary także nazywamy składowymi. A więc okręgi należy na
W. Guzicki: Zadania z kombinatoryki 17 • pierwsza czynność polega na rzuceniu kost
18 W. Guzicki: Zadania z kombinatoryki • druga czynność polega na wybraniu drugiej
W. Guzicki: Zadania z kombinatoryki ile pełnych, siedmioelementowych grup. A więc 128. A jak jest w
img266 (6) ci rekurencyjne Tak więc na początku egzaminu tworzysz obraz mniej (rys. 11.13) albo siln
poetyka011 Czysto kompozycyjnymi zadaniami objaśnić można także na przykład fakt, iż konstatację c u
W odróżnieniu więc na przykład od Rousseau i Pestalozziego, Her-bart przeszedł zwykłą dla jego czasó
CCF20111010 020 Tak więc na progu XXI w., przy uwzględnianiu zarówno doświadczeń przeszłości, jak i
58981 IMGB61 280 Pędzenie warzyw 280 Pędzenie warzyw stopniodni (Loughton 1969). a więc na przykład:
5.5. SZUMY ODBIORNIKÓW AM 319 Tak więc na podstawie równań (5.12) i (5.15) współczynnik poprawy stos
więcej podobnych podstron