Re: Combinations of a limited multiset

rorgg@xxxxxxxxx writes in article <1139941455.111137.222260@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> dated 14 Feb 2006 10:24:15 -0800:
Trying to work this out, but I've come up stumped. How do you find the
number of combinations for a limited multiset?

In particular, I'm trying to calculate taking, say, 40 choices from a
bag of 4000 elements, each having 4 copies.

Here's an answer in recursive pseudo-code. For your example, use
choose_multi(4000, 4, 40, 1).

choose_multi(element_count, copy_count, choices, copy_instance) {

if choices < 0 return 0;
if choices == 0 return 1;
if element_count <= 0 return 0;

combinations = 0;
for (i = 1; i < copy_count; i++) {
combinations += element_count *
choose_multi(element_count-1, i, choices-i, 2);
}
combinations += element_count *
choose_multi(element_count-1, copy_count, choices-copy_count,
copy_instance+1);

return combinations/copy_instance;
}

The intermediate return values are not always integers. For example,
choose_multi(1, 1, 1, 6) = 1/6.

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.
.

Relevant Pages