1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Difficult Brain Teaser: Combinatorics Problem on Selection with Replacement

  1. Dec 16, 2007 #1
    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,

    Last edited: Dec 16, 2007
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted

Similar Discussions: Difficult Brain Teaser: Combinatorics Problem on Selection with Replacement
  1. Combinatorics problem (Replies: 6)

  2. Combinatorics problem (Replies: 3)

  3. Combinatorics problem (Replies: 8)

  4. Combinatorics problem (Replies: 4)