Wstęp
W artykule wyszczególnionym na początku artykułu, udało nam się pokazać, jak dużo będzie wszystkich możliwych podzbiorów zbioru. Doszliśmy do wniosku, że będzie to:
Czyli dwa do potęgi liczebności zbioru, czy też mocy zbioru. Wyszliśmy tam z metodą podejmowania decyzji, czy podzbiór ma zawierać, czy nie zawierać element. Opiszmy tę metodę na początku, dla osób które trafiły tutaj nie z owego artykułu.
Metoda zawierania/odrzucania.
Metoda ta z grubsza poprowadzi nas przez proces wrzucania elementów do zbioru, bądź ich odrzucania i ilości możliwości podjęcia takiej decyzji. Ale spróbujmy na przykładzie.
Weźmy sobie zbiór. Jakikolwiek, którego elementy oznaczymy sobie dla ułatwienia liczbami i będzie on długości
Teraz przypomnijmy sobie czym jest podzbiór. Jest to zbiór elementów, który wyciągamy z jakiegoś zbioru. Może być tak, że wyciągamy część, a może być tak, że wyciągniemy wszystkie. Procesem wyciągania właśnie, sprawimy, że wzór pojawi się nam w głowach za moment.
Skoro mamy zbiór
Mamy jeden podzbiór. Ok, ale czy możemy wyrzucić też drugi? No tak. Wyrzućmy drugi.
Mamy drugi podzbiór. Ok, ale czy możemy wyrzucić drugi, ale zostawić pierwszy? No tak. Wyrzućmy drugi, zostawmy pierwszy.
Mamy trzeci podzbiór. Teraz trzeba zadać sobie pytanie, do czego to nas prowadzi.
Otóż prowadzi nas do tego, że idąc od pierwszego elementu zbioru, do ostatniego po kolei, nad każdym elementem możemy podjąć decyzję, czy owy element usunąć, czy może go zostawić. Po kolei więc.
Zastanawiając się nad pierwszym elementem, mamy dwie możliwości, wywalamy, albo zostawiamy.
Idąc do drugiego elementu, znów mamy dwie możliwości, wywalamy, albo zostawiamy. Będąc jednak na drugim elemencie, pamiętamy, że to jaki zbiór powstanie teraz, zależy od decyzji jaką podjęliśmy wcześniej. Skoro więc przy pierwszym elemencie mieliśmy
Idąc do trzeciego elementu znów mamy
I tak dalej, aż do
Można ten sposób porównać do tego, jak działają liczby.
Tak, liczby.
Bo weźmy np. liczbę
Ale w przypadku tego zapisu mamy
Jeżeli zapiszemy liczbę dwójkowo, perspektywa zmienia się nieco. Bo ile kombinacji ma liczba 3 cyfrowa, dwójkowo? No
I tak doszliśmy do potęgi dwójki, jako symbolu podejmowanej decyzji. Porównaliśmy również tę metodę do liczb binarnych, żeby delikatnie podkreślić przyczynę podnoszenia tej dwójki do potęgi.
Dociekliwy umysł jednak, lub taki, który miał już kombinatorykę, może dojść do innych metod wyznaczania liczności zbiorów. Spróbujmy więc poszukać innych sposobów dojścia do tego, jak tę liczność wyliczyć.
Metoda kombinacji krotek.
Poćwiczmy dla przykładu na fizycznym zbiorze, na razie bez abstrakcji.
Weźmy zbiór
- zbiór pusty
- wszystkie pojedyncze elementy
- wszystkie pary
- wszystkie trójki
- wszystkie czwórki
- wszystkie piątki, czyli cały nasz zbiór
Podliczmy więc:
- pusty
- pojedyncze elementy
- pary
- trójki
- czwórki
- piątki
A więc sumarycznie mamy:
Na początku weźmy pary. Załóżmy na początku, że elementy mogą się powtarzać, więc w takiej parze będziemy mieli
Teraz...
Musimy zacząć trochę podokładać założeń, bo ostatecznie chcemy dość do wyniku, który da nam rzeczywistą wartość. Załóżmy więc teraz, że elementy nie mogą się powtórzyć. W takiej parze więc mamy na pierwszej pozycji
Ok. Już trochę skroiliśmy ten zbiór, ale musimy sobie przypomnieć jedną własność zbioru. Zbiór identyfikujemy poprzez jego elementy. Te kombinacje, które wygenerujemy w tym przypadku, nie będą wrażliwe na kolejność elementów. Więc musimy jeszcze bardziej obciąć te kombinacje.
Dołóżmy więc kolejne założenie. Kombinacje są wrażliwe na kolejność, więc kombinacje typu
Teraz będzie trochę zagmatwane, więc proszę o skupienie.
Na pierwszej pozycji wybieramy jeden z
I to są pary.
Teraz, czy można to podejście przenieść na trójki? Owszem można.
Mamy więc trójki. Zakładamy że elementy się nie powtarzają, więc mamy
Lustrzane odbicie pary, to nic innego, jak jej "permutacja" czyli jedna z możliwości ustawienia elementów tej pary w kolejności. Więc skoro likwidowaliśmy lustrzane odbicia, to teraz możemy spróbować zlikwidować permutacje i zostawić tę jedną jedyną kombinację, na której nam zależy. Bo skoro nie zważamy na kolejność, a kolejności różnych będzie np.
No to jedziemy. Ile więc będzie takich permutacji?
Skoro możemy ustawić na pierwszej pozycji
Mamy więc
Teraz, czy można z tym iść do czwórek? Ano można. Zakładamy że elementy się nie powtarzają, więc mamy
Teraz, czy można z tym iść do piątek? Można. A do szóstek? Można. A do siódemek? Również. Można iść z tym nawet do
Skoro wiemy jak konstruować wzór dla poszczególnych liczności kombinacji, spróbujmy uogólnić ten wzorek, na
Zakładamy że elementy się nie powtarzają, więc mamy:
Jeżeli przyjrzymy się temu wzorowi, zauważymy, że to tak naprawdę
to żeby z powrotem wrócić do pierwotnej formy, trzeba pozbyć się wszystkich czynników, aż do samego
Mamy liczbę podzbiorów, z elementami, które się nie powtarzają. Teraz musimy wywalić permutacje. Ile jest więc permutacji
Cudownie! Jesteśmy asami. Wyprowadziliśmy wzór na ilość kombinacji
Z artykułem naukowym na ten temat jednak spóźniliśmy się tak z 400 lat, bo za jego autora uznaje się Izaaka Newtona. W Polsce nazywamy ten wzór współczynnikiem dwumianowym bądź symbolem/dwumianem Newtona. A jego oznaczenie wygląda następująco:
I równa się dokładnie temu co wyznaczyliśmy, czyli:
Teraz mając już dokładny wzór na ilość kombinacji
Czyli mocą zbioru potęgowego zbioru
Ale zaraz.
Mamy sumę kombinacji, ale jak z tego wzoru wyjść na
Jako ciekawostkę dodam, że jak będziemy sobie taki dwumian rozpisywać dla zbiorów od
[Zaawansowane] Dwumian Newtona.
Otóż. Sam dwumian nie wywodzi się z teorii zbiorów, ani na początku nie miał ze zbiorami nic wspólnego. Dwumian Newtona na samym początku miał opisywać współczynniki wielomianu
Teraz jeżeli użyjemy tego wzoru zręcznie uda nam się go odrobinę przekształcić. W naszym wzorze na ilość kombinacji mieliśmy liczbę samych dwumianów. Nie było mowy o żadnych
Czyli:
Ot cała filozofia.
Podsumowanie
A więc tak się to wszystko prezentuje. Wzory na pozór dziwne i wyjęte z czapki mają swoje idealne uzasadnienie. Postaram się tak robić z większością, jak nie wszystkimi wzorami jakich będziemy używać.
Dziękuję za uwagę i zapraszam na kolejne artykuły.
Komentarze