Thread: Very difficult combinatorics problem

Problem Statement:

Assume that there are n items (numbered from 1 to n) in an urn.
We select b items from the urn and record their numbers.
We return the selected b items into the urn and perform another selection.
We do in total m such selections.

At the end of the m selections we check the recorded numbers. For every unit number chosen in the first selection, if it is also chosen in any of the rest m-1 selections we have a loss of 1 unit (the loss is 1 unit irrespectively if the same item has been re-chosen more than 1 times).

Example: n=10,b=4,m=3

Selection 1 | Selection 2| Selection 3
item1 | item1 | item3
item5 | item7 | item1
item8 | item2 | item9
item7 | item3 | item10

In this example item1 is re-chosen in Selection 2 and Selection 3 so we loose 1 unit from it. Also item7 is re-chosen in Selection 2 so we loose another 1 unit from it. In total we have lost 2 units.


We want to compute:
a) the formula that gives the average loss that we will have.
b) the average number of times that an item is re-chosen.

Actually I think the formula must be of the form:

Probability(1 unit re-chosen in >=2 selections)*(-1)+Probability(2 units re-chosen in >=2 selections)*(-2)+...+Probability(b units re-chosen in >=2 selections)*(-b)= ???




Thank you,

Christopher

Why are you multiplying the probabilities by negative coefficients?

Originally Posted by colby2152

Why are you multiplying the probabilities by negative coefficients?

Since we are trying to find the average loss, so the coefficients must be negative. In any case you can compute it also with positive coefficients.