Computational Aspects of Ordered Integer Partition with Upper Bounds

Kurzfassung/Abstract

We propose a novel algorithm for computing the number of ordered integer partitions with upper bounds. This problem’s task is to compute the number of distributions of z balls into n urns with constrained capacities i1,\hdots,in (see [10]). Besides the fact that this elementary urn problem has no known combinatoric solution, it is interesting because of its applications in the theory of database preferences as described in [3] and [9]. The running time of our algorithm depends only on the number of urns and not on their capacities as in other previously known algorithms.