Wersja z 2013-05-05
Nieco bardziej zaawansowana kombinatoryka posługuje się pewną ilością pojęć, które poniżej zdefiniujemy. Aby nauczyć się podstaw sztuki rozwiązywania zadań z kombinatoryki, znajomość wielu definicji nie jest wcale niezbędna. Podanie ich w tym miejscu jest konieczne z uwagi na całość prezentowanego materiału, na początek można je jednak opuścić i przejść do rozwiązywania prostych zadań.
Element to pojęcie pierwotne, co oznacza, że nie jest formalnie definiowane. Również zestawienie (zwane czasem zestawem) to pojęcie pierwotne. Z niewiadomych powodów matematycy zajmujący się innymi działami niż kombinatoryka unikają tego pojęcia, i błędnie uważają zbiory za pojęcia pierwotne. Tymczasem zbioru nie można utożsamiać z zestawieniem. Jest to jeden z rodzajów zestawień, może być zatem zdefiniowany. Innymi rodzajami zestawień są multizbiory i ciągi.
Zbiór jest to zatem takie zestawienie, w którym:
Multizbiór jest innym typem zestawienia. Różni się 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. Podobnie jak w przypadku zbioru, kolejność elementów multizbioru nie jest istotna.
Ciąg to kolejny typ zestawienia. W innych działach matematyki najczęściej rozumie się ciąg jako rodzaj funkcji na danym zbiorze, wbrew jednak temu, czego uczą w szkołach, nie jest to rozumienie powszechne, a poza tym jest głęboko nieintuicyjne, a nawet niezgodne z logiką. Ciąg nie jest funkcją, ale rezultatem jej działania. Informatycy i niektórzy matematycy rozumieją to doskonale, i nawet jeśli nazywają ciąg funkcją, to dostrzegają potrzebę nazwania obiektu, który powstaje w wyniku jej działania. Upierając się niepotrzebnie przy traktowaniu ciągu jako funkcji, wprowadzają nowe pojęcia w rodzaju „n-
tka” lub „krotka” (dwójka, trójka, czwórka, piątka itd.), tworząc niepotrzebnie chaos nomenklatoryczny.
Zamiast bawić się w wymyślanie takich dziwacznych terminów, ciąg należy rozumieć jako zestawienie podobne do zbioru, w którym elementy (zwane tu wyrazami) ułożone są po kolei (to znaczy są ponumerowane liczbami naturalnymi dodatnimi, począwszy od 1). Nieściśle określa się ciąg jako „zbiór uporządkowany” (takie określenie jest 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). Ciąg może zawierać wyrazy identyczne lub nie.
Zatem zbiór i ciąg (a także multizbiór) to pojęcia należące do tej samej klasy pojęciowej. Jest to zgodne z intuicją, zdrowym rozsądkiem, pragmatyzmem, a wreszcie z całą resztą nauki zwanej kombinatoryką. Traktowanie zbioru jako pojęcia pierwotnego, mimo że jednocześnie podaje się jego atrybuty (cechy), jest nie tylko sprzeczne ze zdrowym rozsądkiem, ale jest także dowodem kompletnego niezrozumienia, czym jest definicja. Podobnie traktowanie ciągu jako pojęcia z całkiem innej kategorii, mianowicie jako rodzaju funkcji, także wiedzie na intelektualne manowce. Funkcja może być sposobem na utworzenia, a może nawet na przedstawienie ciągu, ale nie samym ciągiem.
W klasycznej kombinatoryce nawias klamrowy {} nie oznacza zbioru, ale zestawienie. Należy zwrócić uwagę na tę konwencję, gdyż zgodnie z nią nawias klamrowy może obejmować nie tylko zbiory, ale także multizbiory, a nawet ciągi. Autorzy podręczników przestrzegają jednak innych zasad. Skoro bowiem elementy ciągu noszą specjalną nazwę – wyrazy – to także i sam zapis ciągu może być inny niż zapis zbioru czy multizbioru. Dlatego dla ciągów używa się nawiasów zwykłych (). Innymi słowy, przyjmuje się, że zapisy {a, b} oraz {b, a} oznaczają dokładnie to samo (bo kolejność nie jest tu istotna), za to zapisy (a, b) i (b, a) oznaczają coś całkiem innego (bo kolejność jest istotna).
Rozkwit teorii mnogości i niezrozumiała demonizacja przez matematyków pojęcia zbioru (bardziej będąca wynikiem snobizmu niż wynikająca z rozwoju nauki) sprawiły, że pojęcia używane w kombinatoryce stały się niespójne. Na szczęście klasyczna kombinatoryka wypracowała swoją własną terminologię, całkiem inną terminologię.
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:
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:
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:
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.
Zauważmy więc, ż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 też, że kombinacje bez powtórzeń są zbiorami.
Zauważmy dalej, ż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.
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: