Combinatorics/Multisets problem question

Question

I wonder how a problem of the following type can be solved. I have looked for a solution but I am not to identify the kind of problem I am facing. I would like to know if there is a close formula or if it has to be solved with an algorithm.

I expose the problem through an specific example:

I have N=7 bags. Each bag contains aways a single element, but elements can be repeated. For instances:

bag 1: Element 1
bag 2: Element 1
bag 3: Element 1
bag 4: Element 2
bag 5: Element 2
bag 6: Element 3
bag 7: Element 3

On how many ways I can withdraw for example i=4 elements from which S=3 are different. For example:

1 (Bag 1)
1 (Bag 2)
2 (Bag 4)
3 (Bag 6)

Or:

1 (Bag 1)
1 (Bag 3)
2 (Bag 4)
3 (Bag 6)

I think the problem is related to multisets since the elements of the set are repeated but I am not sure

Regards

Answer 1

Let's solve the particular problem, then see whether we can say anything more general.

To draw 4 elements, three different, you can draw 1123, 1223, or 1233.

The number of ways to draw 1123 is 3-choose-2 times 2-choose-1 times 2-choose-1, which is $3\times2\times2$, which is 12.

The number of ways to draw 1223 is 3-choose-1 times 2-choose-2 times 2-choose-1, which is $3\times1\times2$, which is 6.

1233 is the same, another 6. So the answer is $12+6+6=24$.

Now let's pose the general problem. You have $n_1$ bags containing element 1, $n_2$ bags containing element 2, and so on, to $n_r$ bags containing element $r$. You want to take $i$ elements, with $s$ of them being different. So we may assume $s\le i$, $s\le r$, $i\le n_1+\cdots+n_r$.

Since there are $r$ types of element, and you want exactly $s$ types of element, there are $r\choose s$ ways of choosing which types of element you get. For each such choice, you have $$x_{j_1}+x_{j_2}+\cdots+x_{j_s}=i,\quad1\le x_{j_m}\le n_{j_m},\quad m=1,2,\dots,s\tag1$$ Now there are standard ways of finding the number of solutions of (1), then you have to add that up over the $r\choose s$ ways of choosing which types of element you get. No doubt one could make a formula out of that, but there would be little to distinguish such a formula from an algorithm.