Funkcja PI

[Gouranga]

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 \(\displaystyle{ n}\) nierozróżnialnych kul do \(\displaystyle{ k}\) nierozróżnialnych pudełek nie dopuszczając pustych pudełek pojawia się funkcja \(\displaystyle{ \pi(n,k)}\)
określona w taki sposób:
\(\displaystyle{ \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ć?

[frej]

Takich podziałów jest tyle, co rozwiązań równania

\(\displaystyle{ x_1+x_2 + \ldots + x_k=n \quad \quad 1\le x_1\le x_2 \le \ldots \le x_k}\)

Liczba \(\displaystyle{ 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
\(\displaystyle{ \pi(n-1,k-1)}\) - te rozwiązania, w których \(\displaystyle{ x_1=1}\), bo liczby \(\displaystyle{ x_2,\ldots, x_k}\) spełniają równanie

\(\displaystyle{ x_2 + \ldots + x_k=n-1 \quad \quad 1\le x_2 \le \ldots \le x_k}\)

\(\displaystyle{ \pi (n-k,k)}\) - te rozwiazania, w których \(\displaystyle{ x_1\ge 2}\),a zatem \(\displaystyle{ \forall_{1\le i\le k} x_i\ge 2}\). Oznaczmy \(\displaystyle{ a_i=x_i-1}\). Widać, że nowe zmienne są rozwiązaniem równania

\(\displaystyle{ a_1+a_2 + \ldots + a_k=n-k \quad \quad 1\le a_1\le a_2 \le \ldots \le a_k}\)

[kropka+]

Poczytaj o liczbach Stirlinga II rodzaju.

[Gouranga]

dzięki
Czyli tak bardziej na chłopski rozum \(\displaystyle{ \pi(n-1,k-1)}\) to wrzucamy jedną kulę do jednego pustego pudełka i rekurencyjnie rozkładamy resztę, a \(\displaystyle{ \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:
\(\displaystyle{ \sum_{i=0}^\infty z^{ir} = \frac{1}{1-z^r}}\)

oraz

\(\displaystyle{ \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

[arek1357]

O ile pierwszy jest ok drugi mi całkiem nie pasuje nijak!


Czemu na podziały liczb używacie \(\displaystyle{ \pi}\) a nie \(\displaystyle{ P}\)

[Gouranga]

Nie do mnie to pytanie, tak profesor podal