szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Funkcja PI
PostNapisane: 26 sty 2015, o 23:20 
Użytkownik
Avatar użytkownika

Posty: 1472
Lokalizacja: Trójmiasto
Witam
jutro o 14 mam egzamin ustny (zerowy) z kombinatoryki i nie było mnie na jednych zajęciach a w notatkach z nich pojawia się coś, czego nie rozumiem
przy zagadnieniu podziału n nierozróżnialnych kul do k nierozróżnialnych pudełek nie dopuszczając pustych pudełek pojawia się funkcja \pi(n,k)
określona w taki sposób:
\begin{cases}
\pi(n,k) = 1 \quad n=k\\
\pi(n,k) = 0 \quad n<k\\
\pi(n,k) = \pi(n-1, k-1) + \pi(n-k, k)\end{cases}

o ile dwa pierwsze rozumiem (bo jak są równe to jest 1 sposób - po 1 kuli do każdego, jak kul jest za mało to zostają puste pudełka a tego nie dopuszczamy) o tyle tej rekurencji nie mam pojęcia skąd się wzięła. Ktoś mógłby mi to nakreślić?
Góra
Mężczyzna Offline
 Tytuł: Funkcja PI
PostNapisane: 26 sty 2015, o 23:44 
Gość Specjalny

Posty: 2628
Lokalizacja: Warszawa
Takich podziałów jest tyle, co rozwiązań równania
x_1+x_2 + \ldots + x_k=n \quad \quad 1\le x_1\le x_2 \le \ldots \le x_k

Liczba x_i mówi ile jest kul i-tym pudełku(najpierw pudełka sortujemy względem liczby kul, które w nich są).

Wtedy rekurencja jest prosta, bo
\pi(n-1,k-1) - te rozwiązania, w których x_1=1, bo liczby x_2,\ldots, x_k spełniają równanie
x_2 + \ldots + x_k=n-1 \quad \quad 1\le  x_2 \le \ldots \le x_k

\pi (n-k,k) - te rozwiazania, w których x_1\ge 2,a zatem \forall_{1\le i\le k} x_i\ge 2. Oznaczmy a_i=x_i-1. Widać, że nowe zmienne są rozwiązaniem równania
a_1+a_2 + \ldots + a_k=n-k \quad \quad 1\le a_1\le a_2 \le \ldots \le a_k
Góra
Kobieta Offline
 Tytuł: Funkcja PI
PostNapisane: 27 sty 2015, o 00:00 
Użytkownik
Avatar użytkownika

Posty: 4419
Lokalizacja: Łódź
Poczytaj o liczbach Stirlinga II rodzaju. http://pl.wikipedia.org/wiki/Liczby_Stirlinga
Góra
Mężczyzna Offline
 Tytuł: Funkcja PI
PostNapisane: 27 sty 2015, o 00:07 
Użytkownik
Avatar użytkownika

Posty: 1472
Lokalizacja: Trójmiasto
dzięki
Czyli tak bardziej na chłopski rozum \pi(n-1,k-1) to wrzucamy jedną kulę do jednego pustego pudełka i rekurencyjnie rozkładamy resztę, a \pi(n-k,k) to dokładamy kule tam, gdzie już były?

żeby nie zakładać specjalnie drugiego tematu mam też wątpliwości co do pochodzenia dwóch wzorów, które się w w/w notatkach pojawiły:
\sum_{i=0}^\infty z^{ir} = \frac{1}{1-z^r}

oraz

\sum_{r=0}^n \left< \begin{array}{c}n\\r \end{array}\right> z^r = \sum_{i=0}^r \left(z^i\right)^n = \left(\frac{1}{1-z}\right)^n

czy ktoś mógłby potwierdzić, że te wzory są prawidłowe i ktoś nie popełnił błędu zapisując je
Góra
Mężczyzna Offline
 Tytuł: Funkcja PI
PostNapisane: 27 sty 2015, o 01:35 
Użytkownik
Avatar użytkownika

Posty: 3476
Lokalizacja: blisko
O ile pierwszy jest ok drugi mi całkiem nie pasuje nijak!


Czemu na podziały liczb używacie \pi a nie P
Góra
Mężczyzna Offline
 Tytuł: Funkcja PI
PostNapisane: 27 sty 2015, o 12:15 
Użytkownik
Avatar użytkownika

Posty: 1472
Lokalizacja: Trójmiasto
Nie do mnie to pytanie, tak profesor podal
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Mały problem z funkcją tworzącą  kogutto  1
 Ile jest liczb...; funkcja tworząca; wzór jawny.  marta81  1
 funkcja generująca  iwazach  0
 Dwa zadania: metoda wlaczen i wylaczen oraz funkcja tworzaca  Zajec  1
 Grafy, funkcja tworzaca  miglanc  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl