Zero Silnia - czyli dlaczego 0!=1?

Artykuł "Mnożenie liczb ujemnych - czyli dlaczego minus razy minus daje plus?" cieszy się ogromnym zainteresowaniem (np. w piątek 21.10.2016 został pobity rekord, mianowicie tylko w tym jednym dniu 350 unikalnych użytkowników zapoznało się z treścią wpisu). Będąc świadomym, że dla wielu z Was ważne jest zrozumienie motywacji stojącej za podstawowymi definicjami, postanowiłem rozpocząć nowy cykl "Dlaczego?". Nowa seria skupi się na powszechnie znanych zagadnieniach, których wyjaśnienie nie jest już takie oczywiste. 🙂 Dziś na tapetę idzie zero silnia! Przedstawię kilka argumentacji - w tym coś dla mniej i coś dla bardziej zaawansowanych! Będzie hardcorowo 🙂

Zero silnia równa się jeden / 0!=1

Silnia - definicja

W celu przypomnienia

n!=n\times (n-1)\times (n-2)\times \ldots \times 2\times 1

Przykłady

4!=4\cdot 3\cdot 2\cdot 1=24

3!=3\cdot 2\cdot 1=6

2!=2\cdot 1=2

1!=1

0!=??? - no właśnie 🙂 - do tego wrócę za chwilkę!

Silnia jako liczba permutacji

W uproszczeniu permutacja zbioru (mówimy o zbiorach skończonych) to funkcja wyznaczająca kolejność jego elementów. Np. {1,2,3,4}, {2,4,1,3}, {4,3,2,1} ... są różnymi permutacjami zbioru {1,2,3,4}.

W ogólnym przypadku - jeśli mamy do czynienia ze zbiorem n-elementowym otrzymujemy:

  • n sposobów wyboru elementu 1 (bo mamy do dyspozycji cały zbiór)
  • n-1 sposobów wyboru elementu 2 (bo pierwszy jest już wybrany, pozostało n-1)
  • n-2 sposobów wyboru elementu 3 (bo 2 pierwsze są już wybrane, pozostało n-2)
  • ...
  • n-(k-1) sposobów wyboru elementu k (bo k-1 pierwszych jest już wybranych, pozostało n-(k-1) )
  • ...
  • 2 sposoby wyboru elementu n-1 (bo n-2 elementy wybrano, pozostały wolne 2)
  • 1 sposób wyboru elementu n (bo n-1 elementów wybrano, pozostał wolny tylko 1)

i finalnie liczba różnych uporządkowań zbioru n-elementowego wynosi:

{\small n\times (n-1)\times (n-2)\times \ldots \times 2\times 1=n!}

Zatem interpretacja n! to liczba permutacji (czyli liczba różnych uporządkowań) zbioru n-elementowego.

No dobrze - ale jak to pomaga w ustaleniu 0! (zero silnia)? Przecież ciężko mówić o kolejności elementów zbioru pustego... Do tego wrócę również nieco później 🙂

Wariacja bez powtórzeń

Brrr - paskudna ta nazwa - ale ok - spróbujmy. Mówimy, że wybór dokładnie k-różnych elementów, zwracając uwagę na kolejność, ze zbioru n-elementowego, jest k-elementową wariacją bez powtórzeń zbioru n-elementowego. Przykłady różnych 3-elementowych wariacji bez powtórzeń zbioru {1,2,3,4,5} to: {1,2,3}, {3,2,1},{4,5,2},...

Liczbę V_n^k k-elementowych wariacji bez powtórzeń zbioru n-elementowego wyznaczymy na bazie:

  • n sposobów wyboru elementu 1
  • n-1 sposobów wyboru elementu 2
  • n-2 sposobów wyboru elementu 3
  • ...
  • n-(k-1) sposobów wyboru elementu k

i finalnie

{\large V_n^k}={\small n\times (n-1)\times (n-2)\times\ldots\times \bigg(n-(k-1)\bigg)}

ale

{\small n\times (n-1)\times (n-2)\times \ldots\times \big(n-(k-1)\big)}=...

={\small\frac{n\times (n-1)\times (n-2)\times \ldots\times \big(n-(k-1)\big)\times (n-k)\times \ldots \times 2\times 1}{(n-k)\times \ldots \times 2\times 1}}=...

...=\frac{n!}{(n-k)!}

Zatem

{\large V_n^k=}{\Large\frac{n!}{(n-k)!} }

0! = 1 (słownie: zero silnia równa się jeden)

Zauważmy, że n-elementowa wariacja bez powtórzeń zbioru n-elementowego jest w zasadzie jego permutacją, zatem liczba takich wariacji będzie równa liczbie permutacji, co zapisujemy:

{\large V_n^n=n!}

ale

{\large V_n^n=}{\Large \frac{n!}{(n-n)!}}={\Large \frac{n!}{0!}}

w konsekwencji

n!={\large \frac{n!}{0!}}

{0!\cdot n!=n!}

{\Large 0!=1}

Powyższe uzasadnia, że przyjęcie 0!=1 jest wygodne, gdyż zapewnia "spójność" podstawowych wzorów. Ale czy stoi za tym coś więcej?

!!! Dalsza część dla nieco bardziej zaawansowanych czytelników !!!

Funkcja jako odwzorowanie zbiorów

Funkcja "- schemat

Funkcja f:A\to B, gdzie dla każdego a \in A istnieje f(a)=b\in B wyznacza tak naprawdę relację pomiędzy elementami a i b. Przy takim podejściu możemy powiedzieć, że elementy a\in A oraz b\in B są w relacji f wtedy i tylko wtedy gdy f(a)=b.

Funkcja jako podzbiór iloczynu kartezjańskiego

Funkcję f:A\to B możemy potraktować jako podzbiór iloczynu kartezjańskiego zbiorów A i B, co symbolicznie zapiszemy f\subseteq A\times B

(a,b)\in f \subseteq A\times B \iff f(a)=b

Dobrym przykładem jest wykres funkcji rzeczywistej, który jest podzbiorem płaszczyzny.

Iniekcja - czyli funkcja różnowartościowa

Funkcja "1-1" różnowartościowa - Iniekcja

Iniekcja to inaczej funkcja różnowartościowa, tzn. funkcja f:A\to B jest różnowartościowa wtedy i tylko wtedy, gdy dla dowolnych elementów x,y\in A spełniony jest warunek

x\neq y \implies f(x) \neq f(y)

Surjekcja - czyli funkcja "na"

Funkcja "na" - Surjekcja

Surjekcja to taki przypadek funkcji f:A\to B, że każdy element zbioru B ma swój odpowiednik w zbiorze A. Formalnie zapiszemy to tak

{\large \displaystyle\forall_{b \in B} \quad\displaystyle\exists_{a\in A}\quad}f(a)=b

Bijekcja - czyli funkcja odwracalna (wzajemnie jednoznaczna)

Funkcja odwracalna "1-1" i "na" - Bijekcja

Bijekcja to funkcja f:A\to B, która jednocześnie spełnia warunek iniekcji oraz surjekcji, tzn. jest różnowartościowa oraz "na". Bijekcja jest funkcją odwracalną i wyznacza odwzorowanie wzajemnie jednoznaczne zbioru A na zbiór B (każdy element zbioru A jest jednoznacznie przypisany do elementu zbioru B, oraz każdy element zbioru B ma jednoznaczny odpowiednik w zbiorze A).

Bijekcja vs Permutacja

Permutacja jest funkcją zwracająca uporządkowanie zbioru, tzn. jeśli rozważamy n-elementowy zbiór {1, 2, ..., n} to permutacja będzie funkcją

p:\{1, 2, ..., n\}\to\{1, 2, ..., n\}

spełniającą warunek bijekcji. Pytając o liczbę permutacji możemy równoważnie pytać o liczbę różnych bijekcji z danego zbiory w samego siebie.

Funkcja pusta f:\emptyset\to B

Funkcją pustą nazywamy każdą funkcję, której dziedziną jest zbiór pusty.

f:\emptyset\to B

Wykres funkcji pustej jest zbiorem pustym, gdyż iloczyn kartezjański \emptyset\times B=\emptysetFunkcja pusta jest różnowartościowa, gdyż w dziedzinie (czyli w zbiorze pustym) nie istnieją takie dwa różne elementy, dla których wartość funkcji jest równa.

Funkcja pusta f:\emptyset\to \emptyset

Funkcja pusta f:\emptyset\to \emptyset jest bijekcją, gdyż nie istnieje element przeciwdziedziny (przeciwdziedzina jest zbiorem pustym) nie będący w relacji z elementem dziedziny. Zauważmy, że istnieje dokładnie jedna bijekcja f:\emptyset\to \emptyset, co wynika z faktu, że funkcja jest podzbiorem iloczynu kartezjańskiego dziedziny i przeciwdziedziny. W przypadku rozważanej funkcji pustej f:\emptyset\to \emptyset wspominany iloczyn kartezjański to zbiór pusty \emptyset\times\emptyset=\emptyset, który ma dokładnie jeden podzbiór - również zbiór pusty.

0! = 1 vs funkcja pusta f:\emptyset\to \emptyset

Pisałem wyżej, że liczbę permutacji zbioru n-elementowego można utożsamiać z liczbą bijekcji z tego zbioru w samego siebie. Tym samym permutacjom zbioru 0-elementowego odpowiadają bijekcje ze zbioru pustego w zbiór pusty - a taka funkcja jest dokładnie jedna! 🙂 Trochę abstrakcyjne, ale się zgadza 🙂

Funkcja Gamma (zwana również gammą Eulera) - czyli silnia dla liczb rzeczywistych i zespolonych

Funkcja Gamma - źródło Wikipedia

Funkcja Gamma jest funkcją, która rozszerza pojęcie silni na cały zbiór liczb rzeczywistych, a nawet zespolonych!

\Gamma(z)=\displaystyle\int_0^{+\infty}t^{z-1}e^{-t}dt

 Okazuje się (po scałkowaniu przez części), że

\Gamma(z+1)=z\cdot\Gamma(z)

oraz

\Gamma(1)=\displaystyle\int_0^{+\infty}e^{-t}dt=...

...=\displaystyle\int_{-\infty}^{0}e^{t}dt=...

...=[e^{t}]_{-\infty}^{0}=...

...=e^0-e^{-\infty}=1-0=1

 \Gamma(1)=1

Z powyższego wynika, że dla wszystkich całkowitych liczb n\geq 0 zachodzi

 {\Gamma(n+1)=n!}

 {\large0!=\Gamma(1)=1}

Kolejne bardzo ciekawe spostrzeżenie, że {0!} ma związek z funkcją eksponencjalną!!

Funkcja eksponencjalna

Zwięzek liczby e oraz silni jest nawet większy!

e=\displaystyle\sum_{n=0}^\infty\frac{1}{n!}=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\ldots

Obiecałem, że będzie hardcorowo - i było 🙂

Pozdrowienia,

Mariusz Gromada

mXparser - wysoce elastyczny parser (interpreter) wyrażeń matematycznych dla JAVA oraz C# .NET

mXparser - parser matematyczny

Serdecznie zapraszam do zapoznania się z wysoce elastycznym interpreterem wyrażeń matematycznych. Oprogramowanie jest mojego autorstwa, powstało w 2010 roku i wtedy zostało opublikowane w serwisie SourceForge.net. Z racji, że teraz posiadam stronę o odpowiedniej tematyce, zdecydowałem się przygotować dedykowany opis, który znajdziecie pod tym linkiem. Dostępne są również tutorial oraz specyfikacja API.

Pozdrowienia,

Mariusz Gromada

Pobierz mXparser - parser matematyczny

Download mXparser

Download mXparser

Liczba Stirlinga II rodzaju i losowanie ze zwracaniem

Losowanie ze zwracaniem

Jakiś czas temu rozważałem problem losowania ze zwracaniem dokładnie n-elementów z n-elementowego zbioru (dla uściślenia w zbiorze wyjściowym znajduje się dokładnie n-różnych elementów). W wyniku takiej operacji w wylosowanej próbie mogą pojawić się duplikaty - załóżmy zatem, że otrzymaliśmy k unikalnych rezultatów (oczywiście 1 ≤ k ≤ n). Naturalnie pojawiło się pytanie kombinatoryczne.

Liczba sposobów otrzymania k-unikalnych rezultatów

Ile istnieje sposobów takiego wylosowania (ze zwracaniem) n-elementów spośród n-elementowego zbioru, że w wyniku otrzymamy dokładnie k-unikalnych rezultatów?

Liczbę takich sposobów oznaczmy przez B(n,k).

No i się zaczęło "kombinowanie", początkowo wychodziłem od losowania k różnych elementów, w kolejnym kroku planując dodanie losowania n-k z wylosowanych wcześniej k. Tego typu rozumowanie prowadziło do bardzo skomplikowanych rozważań, szczegóły pominę. Na rozwiązanie wpadłem po około 2 dniach.

Pierwszy krok - wariacja bez powtórzeń

Ddość standardowy - liczba sposobów wyboru k różnych elementów z n zwracając uwagę na kolejność - jest to wariacja bez powtórzeń - V(n,k).

Drugi krok - liczba Stirlinga II

przestajemy myśleć, że właśnie wylosowaliśmy k unikalnych i należy jeszcze dolosować n-k (choć to prawda). W zamian ustalamy, że mamy już n wylosowanych elementów, w tym k unikalnych. Zabieg myślowy polega teraz na uzmysłowieniu faktu, że mając k różnych elementów w zbiorze n-elementowym, dokonaliśmy jego podziału na k-podzbiorów. Ile mamy sposobów podziału n-elementowego zbioru na k-podzbiorów? Jest to właśnie liczba Stirlinga II rodzaju oznaczona S2(n,k). Zatem finalnie

B(n,k) = V(n,k)*S2(n,k)

Dlaczego w kroku pierwszym zwracaliśmy uwagę na kolejność? Chętnych zapraszam do komentowania 🙂

Pozdrowienia,

Mariusz Gromada