Combinatorics/Multisets problem 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
 A: 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. 
