Combinatorics: r-Combinations on a Multiset

[gbean]

Homework Statement

How many r-combinations are there of a multiset S = {1*a1, infinity*a2,...,infinity*ak}?

Homework Equations

The number of r-combinations on a multiset with k objects and infinite repetition number: (r+k-1) choose (r), or (r+k-1) choose (k-1).
The number of r-combinations on a multiset with k objects and finite repetition number is 1-to-1 with the number of positive integral solutions to x1 + x2 + ... + xk = r.

The Attempt at a Solution

I'm not sure how to solve this problem since there is a mix of infinite and finite supplies of k objects.

The answer is (n+k-2) choose (k-2) + (n+k-3) choose (k-2)...

 

[mighty2000]

+ (k-2) choose (k-2) = (n+k-1) choose (k-1), where n is the number of finite supplies. This is because we can think of the multiset as having a total of (n+k-1) objects (n finite supplies and k-1 infinite supplies), and we are choosing (k-1) objects from this total set. The formula for the number of r-combinations on a multiset with k objects and infinite repetition number can be applied to this total set, giving us the final answer.