# 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

It makes a difference as to whether you are counting AAAB as distinct from BAAA, or as the same.

If they are distinct, the easiest way is to count how many ways you can choose the first element, how many the second, ... etc. and then produce a number for all the possible choices combined. You can forget the patterns.

If you want to treat AAAB and BAAA as being the same, then it gests slightly more complicated, and you have to identify each type of pattern AAAA, AAAB, AABB, AABC and ABCD (corresponding to partitions of 4), and then work out how many patterns fit each type.

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$$ 

-
I don't entirely follow your argument. But I think that this can be solved by Feller's stars and bars method, can't it ? In which case, I'm not going to find a more elegant solution, I think. –  user7597 Mar 15 '11 at 17:51
(Grrrr. &!!£\$! carriage return nonsense !!!). Anyway, you've confused me: surely AAAB and BAAA are always the same in a combinations problem, aren't they ? And also, isn't what you've written in your 3rd para above simply describing the approach that I've already tried (i.e. partitions of r) ? –  user7597 Mar 15 '11 at 17:53
@ukmaths: Patterns with different orders are not always treated as being the same, particularly when you want to transfer the method to probability: e.g. with two dice, scoring a total of three (2+1 or 1+2) is twice as likely as scoring two (1+1). –  Henry Mar 15 '11 at 18:14