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:
\(2^{|A|}\)
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 \(n\), czyli:
\(A = \{1, 2, 3, 4, \space...\space, n\}\)
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 \(A\) i on ma \(n\) elementów, to podzbiór może mieć \(n\) elementów, bądź mniej, więc skoro może mieć \(n\) bądź mniej, to to mniej może oznaczać, że usuniemy sobie jakiś element. Np. pierwszy.
\(A = \{␣, 2, 3, 4, \space...\space, n\}\)
Mamy jeden podzbiór. Ok, ale czy możemy wyrzucić też drugi? No tak. Wyrzućmy drugi.
\(A = \{␣, ␣, 3, 4, \space...\space, n\}\)
Mamy drugi podzbiór. Ok, ale czy możemy wyrzucić drugi, ale zostawić pierwszy? No tak. Wyrzućmy drugi, zostawmy pierwszy.
\(A = \{1, ␣, 3, 4, \space...\space, n\}\)
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 \(2\) możliwości, i teraz znów mamy \(2\) możliwości, to ostatecznie powstają nam \(4\) możliwości ostatecznego podzbioru.
Idąc do trzeciego elementu znów mamy \(2\) możliwości, ale znów zależne od poprzednich, więc mamy już możliwości \(8\).
I tak dalej, aż do \(n\)-tego elementu idąc, mnożymy ilość możliwości przez \(2\) z każdym kolejnym elementem, przez co powstaje nam wzór:
\(2^n = 2^{|A|}\)
Można ten sposób porównać do tego, jak działają liczby.
Tak, liczby.
Bo weźmy np. liczbę \(3\) cyfrową. Ile liczb można zapisać liczbą \(3\) cyfrową? \(1000\). Na pierwszej pozycji możemy mieć \(10\) możliwości, na drugiej kolejne \(10\), i na trzeciej kolejne \(10\). W zależności od tego jaką cyfrę zapiszemy wcześniej, nasza liczba będzie inna.
Ale w przypadku tego zapisu mamy \(10\) możliwości wyboru. Ale...
Jeżeli zapiszemy liczbę dwójkowo, perspektywa zmienia się nieco. Bo ile kombinacji ma liczba 3 cyfrowa, dwójkowo? No \(2^3\). Na pierwszym bicie podejmujemy decyzję czy wstawiamy jeden, czy zostawiamy zero, na drugim znów podejmujemy decyzję czy wstawiamy jeden, czy zostawiamy zero i na trzecim znów to samo. Możemy zapisać więc \(8\) liczb, \(8\) kombinacji, \(8\) wybieranych podzbiorów.
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 \(A = \{1, 2, 3, 4, 5\}\) i spróbujmy odpowiedzieć sobie na pytanie, jak dużo podzbiorów różnej długości jesteśmy w stanie z niego wydobyć. Proponuje najpierw rozpisać to sobie na kartce w ramach ćwiczenia i potem porównać z tym co tutaj zaraz napiszemy. Pierwszym podzbiorem, jako że wiemy już o zbiorze pustym, będzie właśnie on. Potem kolejno pojedyncze elementy, zamknięte w zbiory jednoelementowe. Potem kolejno wszystkie pary (pamiętamy, że nie mamy kolejności więc para będzie jednocześnie parą i liczymy ją jako jedną), jakie jesteśmy w stanie znaleźć, potem trójki i czwórki, piątki, i jako że więcej elementów nie ma, na tym musimy zakończyć. Rozpiszmy to sobie dla ułatwienia:
- zbiór pusty \(\emptyset\)
- wszystkie pojedyncze elementy \(\{\{1\}, \{2\}, \{3\}, \{4\}, \{5\}\}\)
- wszystkie pary \(\{\{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 4\}, \{2, 4\}, \{3, 4\}, \{1, 5\}, \{2, 5\}, \{3, 5\}, \{4, 5\}\}\)
- wszystkie trójki \(\{\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}, \{1, 2, 5\}, \{1, 3, 5\}, \{2, 3, 5\}, \{1, 4, 5\}, \{2, 4, 5\}, \{3, 4, 5\}\}\)
- wszystkie czwórki \(\{\{1, 2, 3, 4\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}, \{1, 3, 4, 5\}, \{2, 3, 4, 5\}\}\)
- wszystkie piątki, czyli cały nasz zbiór \(\{\{1, 2, 3, 4, 5\}\}\)
Podliczmy więc:
- pusty \(= 1\)
- pojedyncze elementy \(= 5\)
- pary \(= 10\)
- trójki \(= 10\)
- czwórki \(= 5\)
- piątki \(= 1\)
A więc sumarycznie mamy: \(1 + 5 + 10 + 10 + 5 + 1 = 32\) . Widzimy co się kroi, ponieważ mieliśmy \(5\) elementów, a mamy \(32\) podzbiory. Ale spróbujmy dojść do tego wyniku.
Na początku weźmy pary. Załóżmy na początku, że elementy mogą się powtarzać, więc w takiej parze będziemy mieli \(n^2\) możliwości, ponieważ na pierwszej pozycji mamy dowolność, na drugiej też, \(2\) pozycje, \(n\) możliwości, mamy więc:
\(n \cdot n = n^2\)
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 \(n\) możliwości, bo możemy wybrać każdy element, ale na drugiej już, jako że jeden element mamy już wybrany, możemy wstawić o jeden mniej, czyli \(n - 1\), mamy więc:
\(n \cdot (n - 1) = n^2 - n\)
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 \(\{1, 2\}\) i \(\{2, 1\}\) są tą samą kombinacją.
Teraz będzie trochę zagmatwane, więc proszę o skupienie.
Na pierwszej pozycji wybieramy jeden z \(n\) elementów, na drugiej z \(n - 1\) elementów, żeby cyfry się nie powtarzały. Mamy więc \(n^2 - n\). Teraz Musimy zauważyć, że każda para, którą z tych kombinacji wygenerujemy, będzie miała swoje lustrzane odbicie, np. \(\{1, 2\}\) i \(\{2, 1\}\), albo \(\{4, 5\}\) i \(\{5, 4\}\), więc pozbywamy się owych lustrzanych odbić. Dzielimy więc liczbę wszystkich kombinacji przez \(2\). Mamy więc:
\(\displaystyle \frac{n \cdot (n - 1)}{2} = \frac{n^2 - n}{2}\)
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 \(n \cdot (n - 1) \cdot (n - 2)\). Teraz usuwamy lustrzane odbicia. Ale zaraz... Mamy tutaj trójkę, więc lustrzane odbicie przeniesie nam tylko dwa skrajne elementy. A co ze środkowym? No właśnie.
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. \(6\), to musimy pozbyć się \(5\) i zostawić sobie jedną, jako nasz podzbiór do zliczania.
No to jedziemy. Ile więc będzie takich permutacji?
Skoro możemy ustawić na pierwszej pozycji \(3\) elementy, na drugiej nie może powtórzyć się ten z pierwszej więc \(2\), a na trzeciej nie może się powtórzyć ten z pierwszej i drugiej, więc \(1\). A więc wszystkich permutacji takiej trójki będzie \(6\).
Mamy więc \(6\) permutacji każdej trójki, potrzebujemy jedną z każdej trójki, więc liczbę wszystkich trójek dzielimy na \(6\), a więc wzór na trójki, będzie wyglądał tak:
\(\displaystyle \frac{n \cdot (n - 1) \cdot (n - 2)}{6}\)
Teraz, czy można z tym iść do czwórek? Ano można. Zakładamy że elementy się nie powtarzają, więc mamy \(n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3)\). Likwidujemy permutację, których jest \(4 \cdot 3 \cdot 2 \cdot 1\) i mamy:
\(\displaystyle \frac{n \cdot (n - 1) \cdot (n - 2) \cdot (n - 3)}{24}\)
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 \(n\)-tek.
Skoro wiemy jak konstruować wzór dla poszczególnych liczności kombinacji, spróbujmy uogólnić ten wzorek, na \(n\)-tki właśnie. Ale \(n\)-tka nam nabrudzi trochę, bo utożsamiliśmy są już z licznością/mocą zbioru. Załóżmy więc teraz, że naszą krotką będzie \(k\). Spróbujmy więc wygenerować wzór, na ilość kombinacji \(k\) elementów zbioru, w zbiorze o mocy \(n\). Musimy tu poczynić ważną uwagę i założenie, że \(k\) musi być mniejsze bądź równe \(n\), dlatego że podzbiór zbioru musi być licznością mniejszy, bądź równy właśnie, nadzbiorowi.
Zakładamy że elementy się nie powtarzają, więc mamy:
\(\displaystyle n \cdot (n - 1) \cdot (n - 2) \cdot \space...\space \cdot (n- k + 1)\)
Jeżeli przyjrzymy się temu wzorowi, zauważymy, że to tak naprawdę \(\displaystyle \frac{n!}{(n - k)!}\). Ano dlatego że jak rozwiniemy sobie całość tego wzoru tak, żeby wyszła cała silnia, nie tylko mnożenie do \((n - k + 1)\) czyli:
\(\displaystyle n \cdot (n - 1) \cdot (n - 2) \cdot \space...\space \cdot 2 \cdot 1\)
to żeby z powrotem wrócić do pierwotnej formy, trzeba pozbyć się wszystkich czynników, aż do samego \((n - k + 1)\) właśnie. A że jako to jest silnia, to elementem do którego będziemy dążyć od jedynki, żeby zostawić na swoim miejscu \((n - k + 1)\), będzie element o jeden mniejszy, czyli \((n - k)\), czyli mówiąc ściślej:
\(\displaystyle \frac{n \cdot (n - 1) \cdot (n - 2) \cdot \space...\space (n- k + 1) \cdot (n - k) \cdot \space...\space \cdot 2 \cdot 1} {(n - k) \cdot (n - k - 1) \cdot \space...\space \cdot 2 \cdot 1} = \frac{n!}{(n - k)!}\)
Mamy liczbę podzbiorów, z elementami, które się nie powtarzają. Teraz musimy wywalić permutacje. Ile jest więc permutacji \(k\)-elementów? Ano \(k!\). A więc dzielimy:
\(\displaystyle \frac{ \frac{n!}{(n - k)!}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{k!(n - k)!}\)
Cudownie! Jesteśmy asami. Wyprowadziliśmy wzór na ilość kombinacji \(k\)-elementowych w zbiorze o mocy \(n\).
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:
\(\displaystyle \binom{n}{k}\)
I równa się dokładnie temu co wyznaczyliśmy, czyli:
\(\displaystyle \frac{n!}{k!(n - k)!}\)
Teraz mając już dokładny wzór na ilość kombinacji \(k\)-elementowych w zbiorze o mocy \(n\), możemy wyznaczyć wzór na ilość wszystkich podzbiorów zbioru, czyli po prostu zsumować wszystkie kombinacje. A więc:
\(\displaystyle |\mathcal{P}(A)| = \sum\limits_{k=0}^{n}\binom{n}{k}\)
Czyli mocą zbioru potęgowego zbioru \(A\), jest suma wszystkich jej podzbiorów od \(0\)-elementowych do \(k\)-elementowych.
Ale zaraz.
Mamy sumę kombinacji, ale jak z tego wzoru wyjść na \(2^n\), i czy w ogóle da się wyjść na \(2^n\). Ano da się. Będzie to temat troszkę bardziej zaawansowany i tak go oznaczę.
Jako ciekawostkę dodam, że jak będziemy sobie taki dwumian rozpisywać dla zbiorów od \(1\) do której tylko chcemy, liczby które wyjdą nam z owego dwumianu będą się układały symetrycznie. Mało tego, jak ułożymy je w postaci piramidy, to regularność pojawi się również w pionowej osi. Twór taki nazywamy trójkątem Pascala.
[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 \((x + y)^n\), więc z samego twierdzenia jakie zostało wystosowane dla tego dwumianu, swoją drogą przez samego Newtona, to:
\(\displaystyle (x + y)^n = \binom{n}{0}x^nk^0 + \binom{n}{1}x^{n - 1}k^1 + \binom{n}{2}x^{n - 2}k^2 + \space ... + \space + \binom{n}{n - 1}x^{1}k^{n - 1} + \binom{n}{n}x^{0}k^n\)
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 \(x\)-ach i \(y\)-ach. Jak sprawić, żeby mnożenie przez \(x\) i \(y\), oraz podnoszenie ich do różnych potęg zlikwidować w jakiś magiczny sposób? Ano wstawić za \(x\) jedynkę i za \(y\) jedynkę. Sprawdźmy co wyjdzie:
\(\displaystyle (1 + 1)^n = \binom{n}{0}1^n1^0 + \binom{n}{1}1^{n - 1}1^1 + \binom{n}{2}1^{n - 2}1^2 + \space ... + \space + \binom{n}{n - 1}1^{1}1^{n - 1} + \binom{n}{n}1^{0}1^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \space ... + \space + \binom{n}{n - 1}+ \binom{n}{n} = \sum\limits_{k = 0}^{n} \binom{n}{k}\)
Czyli:
\(\displaystyle (1 + 1)^n = 2^n = \sum\limits_{k = 0}^{n} \binom{n}{k}\)
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