7090996922

W. Guzicki: Zadania z kombinatoryki

6.    Udowodnij, że jeśli 0 < k < n, to |Sfc(n)| = |Pfc(n)|. Ogólnie, jeśli zbiór A ma n elementów, to

|S/b(»)l = lft(A)|.

Rozwiązanie. Ciąg zerojedynkowy (ai,...,o_n) łączymy w parę ze zbiorem tych miejsc, na których w tym ciągu stoi jedynka. Formalnie: ten ciąg łączymy ze zbiorem {z G [n] :    = 1}. Na przykład, jeśli

n = 8, to:

•    dla k = 3 ciąg 01100010 łączymy w parę ze zbiorem {2,3,7},

•    dla k = 0 ciąg 00000000 łączymy w parę ze zbiorem pustym,

•    dla k = 8 ciąg 11111111 łączymy w parę ze zbiorem [8] = {1,2,3,4,5,6,7,8}.

W przypadku dowolnego zbioru A zaczynamy od ponumerowania elementów tego zbioru:

A= {*X,*2,-••»*„}•

Następnie ciąg (aą,..., a_n) łączymy w parę ze zbiorem {xj G A : a, = 1}.

Uwaga. Nietrudno dostrzec, że w przypadku, gdy rozważamy podzbiory zbioru [n], ciąg zerojedynkowy jest funkcją charakterystyczną podzbioru, w którym jest w parze. Oczywiście to jest uwaga dla nauczycieli; uczniom nie mówię nic o funkcjach charakterystycznych. Tłumaczę im natomiast udowodnioną odpowiedniość w następujący sposób.

Dany jest zbiór A mający n elementów; ponumerujmy je: A = {ai,a2,. ■ ■ ,a„}. Każdemu podzbiorowi zbioru A odpowiada wówczas pewien ciąg zerojedynkowy. Nadajmy elementom zbioru A jakąś interpretację: niech nasz zbiór A będzie zbiorem n osób, na przykład uczniów danej klasy. Chcemy wybrać pewną liczbę osób (być może nikogo lub nawet wszystkich) do nagrody. Na ile sposobów możemy to zrobić? Otóż przyglądamy się kolejno tym osobom i co do każdej podejmujemy jedną z dwóch decyzji: „tak” lub „nie”. Jeśli tak, to piszemy jedynkę; w przeciwnym przypadku piszemy zero. Tworzymy w ten sposób pewien ciąg zerojedynkowy długości n. Każdemu sposobowi wyboru osób do nagrody (czyli każdemu podzbiorowi zbioru A) odpowiada jeden ciąg zerojedynkowy długości n i na odwrót; ponadto różnym podzbiorom odpowiadają różne ciągi. A więc tych sposobów wyboru osób do nagrody (czyli podzbiorów zbioru A) jest tyle, ile ciągów zerojedynkowych. W podobny sposób można przekonać uczniów, że podzbiorów A:-elementowych jest tyle, ile ciągów zerojedynkowych długości n, w których jest k jedynek, a więc |5fc(n)|.

Uczniowie często mają trudności ze zrozumieniem pojęcia podzbioru. Powyższa interpretacja pomaga im to pojęcie zrozumieć: mamy całą klasę i niektórych uczniów chcemy nagrodzić; uczniowie nagrodzeni tworzą podzbiór zbioru wszystkich uczniów. W szczególności uczniowie łatwiej rozumieją, co to jest zbiór pusty. Na ogół sprawia im kłopot to, że zbiór pusty także pochodzi z pewnego wyboru. Zastanawiają się, co to znaczy, że istnieje tylko jeden sposób wyboru podzbioru pustego. Interpretacja za pomocą ciągu decyzji pomaga: ciąg pusty powstaje z ciągu decyzji indywidualnych tak samo, jak każdy inny podzbiór.

7.    Dana jest liczba naturalna n > 2. 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 |A| = |S2(n)|.

Rozwiązanie. Parę (i,j) łączymy z ciągiem zerojedynkowym długości n, w którym na miejscach z-tym i j-ym stoją jedynki, a na pozostałych miejscach stoją zera. Niech na przykład n = 8. Wówczas:

•    parę (3,7) łączymy z ciągiem 00100010,

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

•    parę (7,8) łączymy z ciągiem 00000011.

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

8.    Dana jest liczba naturalna n > 3. 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)|.

Rozwiązanie. Postępujemy tak jak w zadaniu 7. Trójkę (i,j,k) łączymy w parę z ciągiem zerojedynkowym długości n, w którym stoją 3 jedynki (na miejscach z-tym, j-ym i fc-tym) oraz n — 3 zer (na pozostałych miejscach). Niech na przykład n = 8. Wówczas:

•    trójkę (2,3,4) łączymy w parę z ciągiem 01110000,

•    trójkę (2,5,7) łączymy w parę z ciągiem 01001010,

Warszawa, 19-20 października 2013 r.