JuliaLang/julia — pull request #8695 by davidavdav (2014-10-15 21:17:28+00:00)
Title: Use alternative for length(partitions(::Array)), bell(n::Int)

(Sorry about the messiness of my pull requests---I am obviously not very skilled in these matters).

I have a new PR, about the Bell number, a.k.a. bell(n) = length(partitions([1:n])).

I had this implementation after Wikipedia lying around, and I think it is more efficient than the current implementation (no recursion), and I believe there is no more need for a cache.

Also---the current implementation doesn't go beyond n=25, after which bell(n) > 1<<63 . In this PR the return type of bell(n) ups to Int128 or even Bigint for larger n.

You may not want to have such type instability and you may not want to depend on Bigint in combinatorics.jl, I can't tell.

Conversely, you may also consider to export bell() if you like the implementation, (see http://en.wikipedia.org/wiki/Bell_number), and similarly one could consider to export nfixedsetpartitions(n,k) as stirling2(n,k) (see http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Definition --- the current implementation of nfixedsetpartitions() ) . I have myself use Bigint versions of stirling2() as one runs out quickly of bits for representing these numbers...