Rekurencja z dwoma zmiennymi.

[KaerbEmEvig]

Witam,

mam do rozwiązania nieliniową (?) rekurencję z dwoma zmiennymi:

\(\displaystyle{ \begin{cases}f(n;k) = k \cdot f(n-1;k) + f(n-1;k-1)\\
f(0;k) = 0\\
f(n;0) = 0\\
f(1;1) = 1\end{cases}}\)

Da się to doprowadzić do postaci ogólnej (closed form)? Przeszukałem jakieś 30 stron Google (bivariate generating function, two-dimensional recurrence, two-variable recurrence, etc.) i nie znalazłem żadnej metody postępowania w tego typu przypadkach.

Rozwiązywanie trywialnych rekurencji (np. ciąg Fibonacciego) nie stanowi jakiegoś wyzwania, ale tu muszę przyznać, że skończyły mi się pomysły.

[Qń]

Zapewne powinno być \(\displaystyle{ f(0,0)=1}\).

Taka rekurencja definiuje nam liczby Stirlinga drugiego rodzaju. Wzoru zwartego (czyli Twojej "closed form" ) nie ma.

Q.

[KaerbEmEvig]

Nie, nie - warunek początkowy podałem dobry. Właściwie Twoja zmiana nie wpłynie jakkolwiek na powstałą "tablicę". Po prostu ładniej to wygląda w Excelu, gdy nie ma tej jedynki w punkcie (0;0).

Skąd w ogóle wziął się problem? Rozważałem chemiczne reakcje następcze [pierwszego rzędu] A->B->C->D->... (studiuję na Wydziale Chemicznym PWr) i zauważyłem, że zależność i-tego reagenta może być zadana n postaciami funkcji stężenia od czasu. Dokładna ich liczba zależy od ilości dostępnych parametrów niezależnych.

Każde przejście jednego reagenta w drugi jest scharakteryzowane tzw. stałą reakcji i zależy od stężenia substratu w pierwszej potędze (stąd rząd pierwszy). Wychodząc od pierwszego reagenta mamy:

- 1 postać funkcji stężenia od czasu dla reagenta A,
- 2 postaci dla c_B,
- 5 postaci dla c_C,
- 15 dla c_D, itd.

Można ten proces zapisać w postaci grafu. Wychodzimy od kółka (węzła) z wpisaną wartością 1. Z każdego węzła o wartości n wychodzi n+1 rozgałęzień - jedno prowadzi do węzła o wartości n+1, a pozostałe (tj. n rozgałęzień) do węzła o wartości n.

Czyli się nie da tego zapisać za pomocą wzoru zwartego? Dzięki. Tyle mi wystarczy.

EDIT: Z Excela: