7090996917

W. Guzicki: Zadania z kombinatoryki

Tak więc na przykład

(1,1,0,1,0,0,0,1) € S₄(8),    (1,1,1,1) € S₄(4),    (0,0,0,0) € S₀(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 S₄(8),    inieS₄(4), ooooeS₀(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 B_a 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 \B_a\ = n dla każdego a € A, to

|{(a, b) : a € A oraz b € B_a}| = m ■ n.

Warszawa, 19-20 października 2013 r.