Hi all,
Just in case you also belong to the people who dot the i's and cross the
t's like me, you might enjoy the following a little bit "tidier" version of
my STIRLING1(n,k):
STIRLING1(n, k) := IF(k >= n, MAX(1 - k + n, 0), IF(k, 0, IF(k = 1, (n -
1)!, IF(k = n - 1, COMB(n, 2), IF(k > n/2, (ITERATE([n_ DELETE_ELEMENT(v_)
+ DELETE_ELEMENT(v_, 1 - n_ + n), n_ + 1], [v_, n_], ITERATE([n_
APPEND(DELETE_ELEMENT(v_), [0]) + v_, n_ + 1], [v_, n_], ITERATE([n_
APPEND(v_,[0]) + INSERT_ELEMENT(0, v_), n_ + 1], [v_, n_], [[1], 0], n -
k), 2k - n), n - k))SUB1SUB1, (ITERATE([n_ DELETE_ELEMENT(v_, 1 - n_ + n) +
DELETE_ELEMENT(v_), n_ + 1], [v_, n_], ITERATE([n_v_ +
APPEND(DELETE_ELEMENT(v_),[0]), n_ + 1], [v_, n_], ITERATE([n_
INSERT_ELEMENT(0, v_) + APPEND(v_, [0]), n_ + 1], [v_, n_], [[1], 0], k), n
- 2·k), k))SUB1SUB1)))))
Numerical experiments seem to indicate that the asymptotic growth of
computation times for Stirling numbers of the first kind is much better
than that for Stirling numbers of the second kind, though the latter can be
given explicitly by the simple formula
STIRLING2(n, k) := 1/k! SUM(COMB(k, j_)(-1)^(k - j_)j_^n, j_, 1, k)
This leads to the following interesting question: Is this inevitable or
does there exist an implementation for Stirling numbers of the second kind
as well that is asymtotically faster than the one above?
Cheers, Johann
_______________________________________________________________________
Johann Wiesenbauer
Institut f. Algebra und Computermathematik
der Technischen Universitaet Wien
Wiedner Hauptstrasse 8-10,
A1040-Vienna, Austria
Tel.: +43 1 58801 11813
Fax: +43 1 58801 11899
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|