7090996923

W. Guzicki: Zadania z kombinatoryki

•    trójkę (1,5,8) łączymy w parę z ciągiem 10001001.

Sprawdzenie, że ten sposób łączenia w pary spełnia warunki (Rl), (R2) i (R3), pozostawię jako ćwiczenie.

9. Dane są liczby naturalne k i n takie, że 1 < fc < n. Definiujemy zbiór A w następujący sposób:

•    zbiór A składa się z ciągów (ai,..., a*,) takich, że 1 < ai < ... < a* < n.

Udowodnij, że wówczas |^4| = |5fc(n)|.

Rozwiązanie. To zadanie jest uogólnieniem zadań 7 i 8. Ciąg rosnący (ax,...,a^) łączymy w parę z ciągiem zerojedynkowym długości n, w którym występuje dokładnie k jedynek (na miejscach o numerach oi,... ,afc) i n — k zer (na pozostałych miejscach). Niech na przykład n = 8 i k = 5. Wówczas:

•    ciąg (1,2,3,4,5) łączymy w parę z ciągiem 11111000,

•    ciąg (2,3,4,6,7) łączymy w parę z ciągiem 01110110,

•    ciąg (1,3,4,6,8) łączymy w parę z ciągiem 10110101.

Sprawdzenie warunków (Rl), (R2) i (R3) pozostawię jako ćwiczenie. Zatem |A| = |Sk(n)|.

10. Dana jest liczba naturalna n > 1. Definiujemy zbiór A w następujący sposób:

•    zbiór A składa się z par (i,j) takich, że 1 < i < j < n.

Udowodnij, że wówczas |j4| = |5₂(n-l-1)|.

Rozwiązanie. Pokażę dwa sposoby rozwiązania zadania. W sposobie pierwszym najpierw definiujemy pomocniczy zbiór B w następujący sposób:

•    zbiór B składa się z par (i, j) takich, żel<i<j<n + l.

Wówczas parę (i,j) należącą do zbioru A łączymy z parą (i, j+1) należącą do zbioru B. Niech na przykład n = 8. Wówczas:

•    parę (2,6) łączymy z parą (2,7),

•    parę (5,5) łączymy z parą (5,6),

•    parę (1,8) łączymy z parą (1,9).

Sprawdzenie, że ten sposób łączenia w pary par należących do zbiorów A i B spełnia warunki (Rl), (R2) i (R3), pozostawię jako ćwiczenie. Zatem |A| = |B|. To, że |2?| = |Ć?₂(n + 1)|, wynika z zadania 7.

W sposobie drugim pokażę bezpośredni sposób łączenia w pary par ze zbioru A z ciągami zerojedynkowymi długości n + 1 zawierającymi dokładnie dwie jedynki. Zacznijmy od wypisania n — 1 zer i ponumerowania miejsc między nimi (łącznie z miejscem przed pierwszym zerem i po ostatnim zerze):

1O2O3O4O5    ...    n—2 o n—1 o n

Napisane zera stały się w ten sposób granicami między miejscami ponumerowanymi liczbami od 1 do n. Niech teraz dana będzie para (i,j) ze zbioru A. Jeśli i < j, to w miejscach o numerach i oraz j wpisujemy jedynki; jeśli i = j, to w miejsce o numerze i wpisujemy obok siebie dwie jedynki. W ten sposób otrzymamy ciąg zerojedynkowy składający się z n — 1 zer i 2 jedynek; łącznie ma on zatem długość n + 1 i ma dokładnie dwie jedynki. A więc otrzymany ciąg zerojedynkowy należy do zbioru S₂(n -I- 1). Popatrzmy na przykład ilustrujący ten sposób łączenia w pary. Niech n = 8. Napisaliśmy zatem 7 zer, oddzielających 8 ponumerowanych miejsc:

l0₂030405060₇0₈

Teraz:

•    parę (3,7) łączymy z ciągiem, w którym jedynki wpisujemy w miejsca o numerach 3 i 7 czyli z ciągiem

001000010,

•    parę (1,8) łączymy z ciągiem 100000001,

•    parę (6,6) łączymy z ciągiem 000001100.

Sprawdzenie, że taki sposób łączenia w pary spełnia warunki (Rl), (R2) i (R3), pozostawię jako ćwiczenie. Zatem |A| = |S₂(n + 1)|.

11. Dana jest liczba naturalna n > 1. Definiujemy zbiór A w następujący sposób:

• zbiór A składa się z ciągów (i,j, k) takich, że 1 < i < j < k < n.

Udowodnij, że wówczas |A| = |5s(n + 2)|.

Warszawa, 19-20 października 2013 r.