Elementy kombinatoryki

Artykuł zachowany ze względów archiwalnych. Nowa wersja znajduje się tutaj.

Strona główna witryny • Kombinatoryka – strona główna

Spis treści

1. Podstawowe pojęcia
2. Rozpoznawanie rodzaju zestawień
3. Obliczanie ilości zestawień
4. Odpowiedzi do zadań
5. Linki

Podstawowe pojęcia

Klasyczna kombinatoryka używa nieco innych pojęć niż inne gałęzie matematyki. Widać to już przy próbie określenia zakresu zainteresowań tej nauki. A zatem możemy powiedzieć, że kombinatoryka jest gałęzią wiedzy, zajmującą się zestawieniami, czyli grupami utworzonymi z przedmiotów zwanych elementami. Mówiąc dokładniej, kombinatoryka odpowiada na pytanie, ile da się zbudować zestawień określonego rodzaju z dostępnych elementów.

Pojęcie zestawienia nie jest formalnie definiowane; nie należy go też utożsamiać z pojęciem zbioru, znanym z innych dziedzin matematyki. Uwaga: w poniższym artykule nawias klamrowy {} nie oznacza zbioru, ale właśnie zestawienie. Należy zwrócić uwagę na tę konwencję, gdyż autorzy podręczników szkolnych często przestrzegają innych zasad. Taki sam system oznaczeń jak w artykule stosowany jest jednak na przykład w niedawno wydanych Tablicach matematycznych wydawnictwa Adamantan.

W literaturze polskiej rozróżnia się na ogół 3 rodzaje zestawień: permutacje, wariacje i kombinacje. Tak oto przedstawiają się te pojęcia w klasycznym rozumieniu (zob. np. J. Królikowski, C. Steckiewicz: Matematyka. Wzory, definicje i tablice. Wiele wydań w latach sześćdziesiątych).

Permutacje to zestawienia spełniające dwa następujące warunki:

• każda permutacja obejmuje wszystkie dane elementy,
• istotna jest tylko kolejność elementów permutacji.

Z trzech danych elementów: a, b, c, można utworzyć następujące permutacje: {a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a}.

Wariacje to zestawienia spełniające dwa następujące warunki:

• obejmują jedynie określoną liczbę k spośród danych n elementów (mniejszą niż liczba elementów danych, k < n, zob. jednak niżej),
• istotna jest kolejność elementów wariacji.

Z trzech danych elementów: a, b, c, można utworzyć następujące dwuelementowe wariacje: {a, b}, {a, c}, {b, a}, {b, c}, {c, a}, {c, b}.

Kombinacje to zestawienia spełniające dwa następujące warunki:

• obejmują jedynie określoną liczbę k spośród danych n elementów (mniejszą niż liczba elementów danych, k < n),
• nie jest istotna kolejność elementów kombinacji.

Z trzech danych elementów: a, b, c, można utworzyć następujące dwuelementowe kombinacje: {a, b}, {a, c}, {b, c}.

Zdefiniowane powyżej pojęcia można również rozszerzyć na przypadki, gdy brane są pod uwagę powtórzenia elementów. W przypadku permutacji rozpatrujemy przypadki, gdy ilość powtórzeń danego elementu jest ściśle określona. A zatem, jeżeli spośród elementów: a, b i c, element a weźmiemy dwa razy, element b jeden raz i element c jeden raz, możemy utworzyć następujące permutacje z powtórzeniami: {a, a, b, c}, {a, a, c, b}, {a, b, a, c}, {a, b, c, a}, {a, c, a, b}, {a, c, b, a}, {b, a, a, c}, {b, a, c, a}, {b, c, a, a}, {c, a, a, b}, {c, a, b, a}, {c, b, a, a}.

Z trzech danych elementów: a, b, c, można utworzyć następujące dwuelementowe wariacje z powtórzeniami: {a, a}, {a, b}, {a, c}, {b, a}, {b, b}, {b, c}, {c, a}, {c, b}, {c, c}. Zwróćmy uwagę, że ilość elementów wariacji z powtórzeniami może być równa całkowitej ilości elementów, a nawet od niej większa. Z podanych trzech elementów możemy więc tworzyć wariacje z powtórzeniami trójelementowe: {a, a, a}, {a, a, b}, …, a także np. czteroelementowe: {a, a, a, a}, {a, a, a, b}, itd.

Z trzech danych elementów: a, b, c, można utworzyć następujące dwuelementowe kombinacje z powtórzeniami: {a, a}, {a, b}, {a, c}, {b, b}, {b, c}, {c, c}. Również i w wypadku kombinacji z powtórzeniami odpada warunek, że ilość elementów tworzących kombinację musi być mniejsza niż całkowita dostępna ilość elementów (np. z trzech elementów możemy tworzyć kombinacje dziesięcioelementowe).

Współczesne podręczniki często definiują powyższe pojęcia kombinatoryki przy pomocy pojęć „zbiór” i „ciąg”, jednak takie podejście nie wydaje się najlepsze, z co najmniej dwóch powodów, o czym niżej. Najpierw jednak zastanówmy się, czym są zbiory i ciągi.

Zbiór i element to pojęcia pierwotne. Nie możemy podać definicji zbioru, mimo to możemy podać dwie cechy zbioru:

• w zbiorze kolejność elementów nie jest istotna,
• zbiór nie zawiera dwóch identycznych elementów.

to znaczy każdy element traktujemy tak, jakby występował tylko jeden raz. Zauważmy, że kombinacje bez powtórzeń są zbiorami.

Multizbiór różni się z kolei tym od zbioru, że może zawierać elementy identyczne, a więc innymi słowy, każdy z różnych elementów multizbioru może występować więcej niż jeden raz. Zauważmy, że kombinacje z powtórzeniami są multizbiorami. Skoro kombinacje z powtórzeniami nie są zbiorami, lecz multizbiorami, rezygnowanie w definicji kombinacji z pojęcia „zestawienie” i zastępowanie go pojęciem „zbiór” nie jest najszczęśliwszym rozwiązaniem.

Ciąg definiuje się formalnie jako funkcję na danym zbiorze, można też określić ciąg jako „zbiór uporządkowany” (takie określenie jest jednak nieścisłe, bo zgodnie z definicjami podręcznikowymi ciąg nie jest zbiorem, por. jednak „a sequence is an ordered set of mathematical objects” – „ciąg jest uporządkowanym zbiorem obiektów matematycznych”, tutaj). Intuicyjnie przez ciąg należy rozumieć obiekt podobny do zbioru, w którym „elementy” (zwane tu wyrazami) ułożone są po kolei. Ciąg może zawierać wyrazy identyczne lub nie. Zauważmy, że permutacje i wariacje są ciągami. Permutacje i wariacje bez powtórzeń są ciągami niezawierającymi wyrazów identycznych. Permutacje i wariacje z powtórzeniami są ciągami zawierającymi wyrazy identyczne.

Zauważmy, że elementy, z których tworzyć będziemy zestawienia (permutacje, wariacje, kombinacje) bez powtórzeń, pobieramy zawsze (bez zwracania) z jakiegoś zbioru. Elementy, z których tworzyć będziemy zestawienia z powtórzeniami, pobieramy z jakiegoś multizbioru (w przypadku wariacji i kombinacji możemy pobierać ze zbioru, zwracając pobrane elementy; w przypadku permutacji z powtórzeniami nie jest to możliwe). Jest to drugi powód, dla którego opieranie definicji poszczególnych rodzajów zestawień na pojęciu zbioru nie jest najszczęśliwsze.

W szkolnych podręcznikach matematyki definiuje się k-
wyrazową wariację bez powtórzeń zbioru Y = {1,2, …, n} jako każdą z funkcji różnowartościowych określonych na zbiorze X = {1,2, …, k} o wartościach w zbiorze Y, przy czym k ≤ n. Wariację z powtórzeniami definiuje się podobnie, z wyjątkiem usunięcia słowa „różnowartościowych”. Podobnie jak wariację bez powtórzeń definiuje się także permutację bez powtórzeń, zakładając jedynie równoliczność obu zbiorów, czyli k = n. Pojęcia permutacji z powtórzeniami najczęściej nie definiuje się w ogóle i jedynie tłumaczy na przykładach, albo też wprowadza się pojęcia grup elementów i permutacji równoważnych. Kombinację bez powtórzeń definiuje się natomiast jako każdy k-
elementowy podzbiór zbioru n-
elementowego. O kombinacjach z powtórzeniami część podręczników milczy, inne dodają do definicji kombinacji bez powtórzeń, że elementy mogą się powtarzać, co przecież narusza rozumienie pojęcia „zbiór”. Tylko najodważniejsi wprowadzają wcześniej określenie multizbioru.

Proponuję Czytelnikowi porównać te podręcznikowe definicje z określeniami podanymi wyżej przeze mnie. Które z nich są bardziej zrozumiałe? Autorzy podręczników usiłują za wszelką cenę wtłoczyć kombinatorykę do matematyki, i nie wykraczać poza pojęcia znane z innych dziedzin tej nauki. Wprowadzenie kolejnego pojęcia pierwotnego, jakim jest zestawienie, byłoby dla tych autorów naruszeniem postulatu zwartości matematyki, a więc czymś niegodnym. Pozostaje jednak pytanie, czy podejście takie jest słuszne dydaktycznie. Czy nie lepiej jednak wprowadzić najpierw pojęcie zestawienia, na jego podstawie zdefiniować poszczególne pojęcia omówione wyżej, a dopiero później zwrócić uwagę, że znane z innych działów matematyki zbiory i ciągi są po prostu szczególnymi typami zestawień? Zresztą, „konkretne” rozumienie ciągu jako rodzaju zestawienia jest znacznie bardziej przystępne dla przeciętnego ucznia niż „abstrakcyjne” rozumienie ciągu jako funkcji. Podobnie odrywanie kombinacji (podzbiorów) od wariacji (funkcji) przeciętnego ucznia wprawia w zdumienie.

Na zakończenie części definicyjnej należy zwrócić uwagę na następujące sprawy:

1. Permutacje określane są też jako przestawienia, wariacje jako przemiany albo rozmieszczenia, kombinacje jako połączenia.
2. W języku potocznym określenie „kombinacja” określa często wariację z powtórzeniami (np. gdy mowa o zamku cyfrowym walizki).
3. W literaturze międzynarodowej nie wyróżnia się w odrębną klasę permutacji. Angielskie słowo „permutation” oznacza na ogół wariacje.
4. W nowszej literaturze permutacje bez powtórzeń są typem wariacji bez powtórzeń. Warunek k < n zastępuje się warunkiem k ≤ n.
5. Permutacje z powtórzeniami są bardzo szczególnym typem wariacji z powtórzeniami. Np. czteroelementowe permutacje z powtórzeniami są w dalszym ciągu jedynie podtypem czteroelementowych wariacji z powtórzeniami, a ilość takich permutacji jest inna niż ilość odpowiednich wariacji. W przypadku permutacji z powtórzeniami określamy bowiem z góry, ile razy wystąpić ma dany element. W przypadku wariacji z powtórzeniami nie określamy, ile razy wystąpić ma dany element, byle ogólna ilość elementów była zachowana.

Rozpoznawanie rodzaju zestawień

Właściwości poszczególnych typów zestawień obrazuje tabela:

Uwaga! Słowo „element” ma tu inne znaczenie niż w szkolnej teorii mnogości (nauce o zbiorach), i dlatego w pięciu przypadkach dodano określenie „różny”. Dopóki mowa tylko o zbiorach (i ciągach), elementy identyczne uważamy za ten sam element – na przykład cztery identyczne trójkąty i dwa identyczne prostokąty tworzą zbiór dwuelementowy, a nie sześcioelementowy. Wprowadzenie pojęcia „multizbiór” sprawia, że konieczne staje się także liczenie powtórzeń elementów rozumianych w sposób klasyczny. Dla uniknięcia nieporozumień najlepiej mówić wówczas, że cztery identyczne trójkąty i dwa identyczne prostokąty to łącznie dwa elementy różne, ale sześć elementów, wliczając powtórzenia.

Koniecznie zwróćmy uwagę, że w wypadku permutacji z powtórzeniami znaczenie symbolu n jest inne niż dla pozostałych zestawień. Jeżeli mamy na przykład dane dwa (nierozróżnialne) trójkąty, trzy kwadraty i cztery koła, i mamy z takiego multizbioru ułożyć wariacje z powtórzeniami lub kombinacje z powtórzeniami, wówczas n oznacza ilość elementów rozumianych klasycznie, a zatem przyjmujemy n = 3. Jeśli jednak chodzi o ułożenie permutacji z powtórzeniami, wówczas musimy n potraktować jako sumę powtórzeń każdego z (różnych) elementów, a więc wówczas n = 9.

W przypadku wariacji z powtórzeniami i kombinacji z powtórzeniami sumaryczna liczba powtórzeń nie musi być (i zwykle nie jest) podana – bo też nie jest nam do niczego potrzebna. Można sobie wówczas wyobrazić, że dysponujemy dostatecznie dużą ilością kopii każdego z zestawianych elementów, co najmniej tyloma kopiami, ile wynosi długość konstruowanego zestawienia (k). Na przykład rozważmy zadanie, które polega na ułożeniu wszystkich możliwych trójwyrazowych wariacji z powtórzeniami z trójkątów, czworokątów i pięciokątów, przy czym figury mogą się powtarzać (k = 3, n = 3). Zauważmy przy okazji, że choć k = n, w zadaniu tym mowa jest o wariacjach z powtórzeniami, a nie o permutacjach z powtórzeniami, choćby dlatego, że nie wiemy, ile mamy trójkątów, ile czworokątów, a ile pięciokątów. Powiedzmy, że dysponujemy trzema fizycznymi modelami trójkąta (np. wyciętymi z papieru), trzema czworokąta i trzema pięciokąta, i tworzymy z nich zestawienia w ten sposób, że wykorzystujemy tylko 3 dowolne modele spośród posiadanych dziewięciu. Możemy jednak dysponować równie dobrze setką trójkątów, setką czworokątów i setką pięciokątów. Jest nieistotne, ile tak naprawdę posiadamy fizycznych kopii zestawianych obiektów, ważne jedynie, by było ich co najmniej 3 – tyle, ile wynosi długość konstruowanego zestawienia. Zresztą możemy nawet dysponować tylko jedną kopią każdej figury, i zwracać ją do puli po każdym wyciągnięciu, a powstające zestawienie rysować na kartce papieru.

Zadanie na tworzenie permutacji z powtórzeniami musiałoby wyglądać zupełnie inaczej, na przykład tak, że dysponowalibyśmy dokładnie dwoma nierozróżnialnymi trójkątami i jednym czworokątem, i mielibyśmy ułożyć z tego ciągi o długości 3, czyli wykorzystać wszystko, co mamy. Choć mamy do czynienia z dwoma typami figur, tym razem operujemy nie na zbiorze, lecz na multizbiorze, i dlatego przyjmujemy n = 3 (oraz n₁ = 2, n₂ = 1).

Aby ustalić rodzaj zestawień, które będziemy analizować, należy postępować według następującego algorytmu:

1. Ustalamy, czy kolejność elementów w zestawieniach jest istotna, czy też nie. Jeżeli nie jest istotna, a zestawienia różnią się tylko składem, mamy do czynienia z kombinacjami i omijamy punkt b.
2. Ustalamy, czy zestawienia różnią się tylko kolejnością elementów. Jeżeli tak, mamy do czynienia z permutacjami. Jeżeli różnią się nie tylko kolejnością elementów, ale także składem, nasze zestawienia to wariacje.
3. Ustalamy, czy w zestawieniach elementy powtarzają się, czy też nie.

O jakich zestawieniach mowa w poniższych zadaniach? Rozwiązania podano na dole strony.

1. Bierzemy 3 prostokąty, 2 koła i 4 trójkąty, i układamy je kolejno jeden za drugim w różnej kolejności.
2. Z 32 liter polskiego alfabetu układamy dowolne, 5-literowe wyrazy.
3. Spośród sześciu osób, tylko cztery mogą otrzymać zaproszenia.
4. 10 osób ustawiamy w szeregu na różne sposoby.
5. W urnie znajduje się 2 kule żółte i 5 zielonych. Wyciągamy 3 kule bez zwracania, notujemy ilość wyciągniętych kul żółtych i zielonych.
6. W urnie znajdują się 2 kule żółte i 5 zielonych. Wyciągamy kolejno wszystkie kule bez zwracania i notujemy ich kolory w kolejności ciągnienia.
7. W urnie znajduje się 7 kul, każda w innym kolorze. Wyciągamy kolejno wszystkie kule bez zwracania i notujemy ich kolory w kolejności ciągnienia.
8. Losujemy 6 ponumerowanych kul z 49 (Duży Lotek).
9. Z cyfr 1,2,3,4,5 układamy różne liczby pięciocyfrowe tak, aby żadna cyfra się nie powtarzała.
10. Z cyfr 1,2,3,4,5 układamy różne liczby czterocyfrowe tak, aby żadna cyfra się nie powtarzała.
11. Z cyfr 1,2,3,4,5 układamy różne liczby pięciocyfrowe. Cyfry mogą się powtarzać.
12. Z cyfr 1,2,3,4,5 układamy różne liczby czterocyfrowe. Cyfry mogą się powtarzać.

Obliczanie ilości zestawień

Ilość zestawień zadanego typu obliczamy według następujących wzorów:

Uwagi do wzorów:

• n! oznacza iloczyn liczb naturalnych od 1 do n, np. 6! = 1·2·3·4·5·6 = 720, nadto umawiamy się, że 0! = 1! = 1,
• znaczenie symbolu Newtona (n nad k) wyjaśniono we wzorze na kombinacje bez powtórzeń,
• n oznacza ilość elementów, z których tworzymy zestawienie (z ilu?),
• k oznacza ilość elementów w zestawieniu (po ile?),
• dla permutacji z powtórzeniami: n₁ to ilość powtórzeń elementu pierwszego, n₂ – elementu drugiego, itd., n = n₁ + n₂ + … + n_k; n jest tu więc sumą powtórzeń (i jednocześnie długością permutacji), a nie ilością różnych (typów) elementów – mowa o tym wyżej.

Ilość permutacji z powtórzeniami oznacza się też symbolem P_n(n₁, n₂, …, n_k). W mianowniku można pominąć elementy, które występują tylko jeden raz, gdyż 1! = 1, a dzielenie przez 1 nie zmienia wyniku.

Ilość wariacji bez powtórzeń wyraża równoważny wzór V_n^k = n (n − 1) (n − 2) … (n − k + 1). W dobie kalkulatorów z wbudowaną funkcją silnia (n!) wygodniej jest jednak posługiwać się wzorem podanym w tabeli. Zauważmy, że istotnie P_n = V_nⁿ, a więc permutacje bez powtórzeń można uznać za rodzaj wariacji bez powtórzeń. Jednak ilość permutacji z powtórzeniami wcale nie jest równa ilości wariacji z powtórzeniami. Dlatego lepiej przyjąć określenie klasyczne, w myśl którego permutacje i wariacje to jednak pojęcia rozłączne.

Zauważmy również, że ilość k-
elementowych kombinacji bez powtórzeń z n elementów równa jest stosunkowi liczby k-
elementowych wariacji bez powtórzeń z n elementów do liczby permutacji z k: C_n^k = V_n^k / P_k.

Przykłady (z rozdziału „Podstawowe pojęcia”):

• ilość permutacji bez powtórzeń z 3 elementów wynosi P₃ = 3! = 1·2·3 = 6,
• ilość 4-elementowych permutacji z 3 elementów, z których pierwszy bierzemy 2 razy, wynosi P₄(2,1,1) = 4!/(2!·1!·1!) = (1·2·3·4)/(1·2) = 12,
• ilość dwuelementowych wariacji bez powtórzeń z trzech elementów wynosi V₃² = 3!/(3 − 2)! = (1·2·3)/1 = 6,
• ilość dwuelementowych wariacji z powtórzeniami z trzech elementów wynosi W₃² = 3² = 9,
• ilość dwuelementowych kombinacji bez powtórzeń z trzech elementów wynosi C₃² = 3!/(2!·(3 − 2)!) = 6/2 = 3,
• ilość dwuelementowych kombinacji z powtórzeniami z trzech elementów wynosi C̅₃² = C₄² = 4!/(2!(4 − 2)!) = (1·2·3·4)/(1·2·1·2) = 12/2 = 6.

Rozwiązania zadań

1. Za każdym razem możemy tworzyć zestawienia różniące się tylko kolejnością figur, są to więc permutacje z powtórzeniami.
2. W tym wypadku liczy się zarówno kolejność, jak i skład. Litery mogą się naturalnie powtarzać, badane zestawienia to wariacje z powtórzeniami.
3. Zestawienia złożone z zaproszonych osób różnią się tylko składem, nie kolejnością. Są to kombinacje bez powtórzeń.
4. Zestawienia różnią się tylko kolejnością osób, są to więc permutacje bez powtórzeń.
5. Tutaj kolejność nie gra roli, ważna jest tylko ilość. Badane zestawienia to kombinacje z powtórzeniami.
6. Zestawienia różnią się wyłącznie kolejnością kolorów, są to więc permutacje z powtórzeniami.
7. Tym razem mamy permutacje bez powtórzeń.
8. W losowaniu Dużego Lotka kolejność wylosowanych liczb nie gra roli. Wyniki są więc kombinacjami bez powtórzeń.
9. Liczby 5-cyfrowe utworzone z pięciu niepowtarzających się cyfr różnią się tylko ich kolejnością. Mamy tu permutacje bez powtórzeń.
10. Skoro liczby są 4-cyfrowe, różnią się składem, a nie tylko kolejnością cyfr. Kolejność cyfr jest istotna. Mamy tu wariacje bez powtórzeń.
11. Otrzymane liczby różnią się kolejnością cyfr, ale także składem (np. 12345 i 11234). Mamy tu więc wariacje z powtórzeniami. Nie są to permutacje z powtórzeniami, ponieważ nie wiemy z góry, ile razy powtórzy się każdy z elementów.
12. Otrzymane liczby różnią się kolejnością cyfr i składem (np. 1234 i 1123). Mamy tu więc wariacje z powtórzeniami.

Linki

• Wzory – kombinatoryka
• Kombinatoryka: polska Wikipedia
• Combinatorics: angielska Wikipedia
• Combinatorics: MathWorld

Artykuł został opublikowany także na witrynie autora pod adresem http://grzegorj.5v.pl/kombin/kombin.html