Select r items from a set with multiplicity k and total items n.

Question

Let N be a set of n distinct objects having the same multiplicity k. For instance,

   N={1,1,2,2,3,3}

where n=3 and k=2.

Now I want to select r numbers from this set.

For example if r = 2, then I can select

  (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)

i.e. there are 9 possible ways. I was thinking if I can find a formula that computes this.

Links to problems similar to this : link 1, link2

Answer 1

If $r/2 < k$ then if you simply consider all $n^r$ combinations of numbers you can form with no restrictions, then the only combinations that will violate your property will have just one number chosen more than $k$ times. You can use simple counting to get a summation formula for how many ways this kind of violation can happen, and subtract from $n^r$ to get your answer. For $k$ asymptotically much smaller than $r$, it seems like a much a harder problem.