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)


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



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.

  • $\begingroup$ Thank you very much for your explanation. Probably I am not very familiar with the notation for this kind of problems, so in eq. (1) I don't understant de meaning of $ x_{j_{m}} $ or $ n_{j_{m}} $. Also, if there is a standard way to solve eq. (1), could you point me to any reference? Thank you very much! $\endgroup$ – Ricard Dec 4 '12 at 10:14
  • $\begingroup$ $n_{j_m}$ is the number of bags containing element $j_m$. $x_{j_m}$ is how many of those bags you pick. Pretty much any introductory discrete math or combinatorics text will tell you how to solve (1), how to find the number of ways of getting $s$ numbers that add up to $i$, with inequality constraints on the numbers. Sometimes, it goes by the name "stars and bars," and it has been discussed many times on this website. $\endgroup$ – Gerry Myerson Dec 4 '12 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.