# counting multi-combinations?

I'm trying to derive a result for the number of possible combinations of r objects from n, when we have unlimited numbers of objects to select from. (Wikipedia suggests that these are called multi-combinations). My current line of reasoning is like this:

Suppose we can choose 4 letters from an unlimited set containing {A, B, C, D, E}. Then we can partition this into choices where 4 are identical, 3 are identical, 2 are identical and all are different, like so:

combs like AAAA + combs like AAAB + combs like AABB + combs like AABC + combs like ABCD

Now, it seems to me that to go this route, I'll have to start enumerating the partitions of r (here 4) to ensure that I'll get all possible combinations with r, r-1, r-2, ... objects. This looks tricky to me.

Can someone tell me a) if this is not a fruitful approach and b) suggest a hint (and no more than a hint please) as to a more straightforward method, as at the moment I don't see one ?

• It's much easier not to do this. – Qiaochu Yuan Mar 15 '11 at 12:13
• I suspected as much. I'll try to look for another approach. Thanks. – user7597 Mar 15 '11 at 12:43

As an illustration of calculating how many ways of getting a pattern like AABB, you are choosing 0 letters four times, 0 letters three times, 2 letters twice, 0 letter one time and 3 letters 0 times so the number of ways is $$\frac{5!}{0! \, 0! \, 2! \, 0! \, 3!} = 10$$ while if different orders make distinct patterns then you getter a larger number $$\frac{5!}{0! \, 0! \, 2! \, 0! \, 3!} \, \frac{4!}{2! \, 2! \, 0! \, 0! \, 0!} = 60$$