Math.Combinatorics.Multiset

Just a quick note to say that I’ve just uploaded a new package, multiset-comb, to Hackage. It primarily has functions for generating all the distinct permutations and partitions of a multiset (a set where elements are allowed to occur multiple times). Efficiently generating distinct permutations and partitions of a multiset is nontrivial (generating all partitions and permutations as if all the elements were distinct, and then discarding duplicate results, is hopelessly inefficient). The permutations code is new; the partitions code is a slight generalization of the code from my article in Issue 8 of the Monad.Reader. I put this code together primarily because I need it for my combinatorial species library (look for a new release of that soon!), but it’s fairly independent, and I thought others might find it useful, so I’m releasing it as a separate library.

How to solve this differential equation?

How would you solve the differential equation

with the initial condition ? I know what the answer is supposed to be, but I don’t know how to directly solve it.

In case you’re wondering, is the exponential generating function for the Bell numbers, which count set partitions. The differential equation in question arises from noting that

(to make a partition of , you can put anywhere from to elements in the same set with ; there are ways to choose the elements to include, and ways to partition the rest).

Monad.Reader article (Multiset partitions)

I imagine that most who read this blog have already seen it, but for those who haven’t, my article Generating Multiset Partitions has been published in Issue #8 of The Monad.Reader.  In it, I discuss the problem of generating multiset partitions in a functional context, and give an implementation in Haskell.  The final published version contains many major improvements over the draft version I posted here a while ago; give it a read and let me know what you think if you’re interested!