Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
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! –  Ricard Dec 4 '12 at 10:14
    
$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. –  Gerry Myerson Dec 4 '12 at 11:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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