Zero Silnia – czyli dlaczego 0!=1?

Wyróżnione

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

Czytaj dalej

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

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\leq k\leq n$). Naturalnie pojawia się pytanie kombinatoryczne.

Losowanie ze zwracaniem

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?

Liczba sposobów otrzymania k-unikalnych rezultatów

Liczbę takich sposobów oznaczmy przez $B_n^k$.

„Kombinowanie” czas start! Początkowo wyszedłem od losowania $k$ różnych elementów, w kolejnym kroku planując losowanie $n-k$ z wylosowanych wcześniej $k$. Tego typu podejście prowadziło do bardzo skomplikowanych rozważań, szczegóły pominę. Na rozwiązanie wpadłem po około 2 dniach.

Wariacja bez powtórzeń

Pierwszy krok – 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$.

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

Liczba Stirlinga II rodzaju

Drugi krok – zapominamy, ż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$, w tym $k$ unikalnych. Trick polega na zauważeniu, że mając $k$ różnych elementów w zbiorze $n$-elementowym, dokonaliśmy jego podziału na $k$-podzbiorów.

Podział zbioru

Ile mamy sposobów podziału $n$-elementowego zbioru na $k$ podzbiorów? Jest to właśnie liczba Stirlinga II rodzaju oznaczona $S_2(n,k)$. Zatem finalnie

$$B_n^k = V_n^k\cdot S_2(n,k)$$

$$S_2(n,k)=\begin{cases}kS_2(n-1,k)+S_2(n-1,k-1)\quad\text{dla}~k<n\\S_2(n,1)=1\\S_2(n,n)=1\\S_2(n,0)=0\\S_2(0,0)=1\\S_2(n,k)=0\quad\text{dla}~k>n\end{cases}$$

Dlaczego w kroku pierwszym zwracałem uwagę na kolejność? Chętnych zapraszam do komentowania 🙂

Pozdrowienia,

Mariusz Gromada