1
$\begingroup$

We have a pool of numbers 1 thru 22. We then draw four numbers. Once a number is drawn, it is out of the pool. We repeat the drawing until we have gone thru all the 7,315 combinations.

I used MATLAB function combntns(set,subset)

Now the hard part: Assume that you want to only keep combinations, where no more than 2 out of 4 numbers are the same.

What is the formula to find out how many valid combinations there are?

Here are the first few valid combinations: $(1,2,3,4):(1,2,5,6):(1,2,7,8):(1,2,9,10):(1,2,11,12):(1,2,13,14)...$

Thank you for the help - DJ

  • 0
    Other than the examples u gave of valid combinations, once we have picked your examples would (3,4,5,6);(3,4,7,8)... ;(3,4,21,22) be counted as valid picks ?2012-02-14
  • 0
    unless they appear in the 1,2,x,x thru 2,20,21,22 they would be valid2012-02-14
  • 1
    2,20,21,22 does n't appear in the sequence of 1,2,x,x2012-02-14
  • 0
    I just got all the answers (263) thanks to a programmer. Now if we can derive the formula to apply it to other sets. [[1, 2, 3, 4], [1, 2, 5, 6], [1, 2, 7, 8], [1, 2, 9, 10], [1, 2, 11, 12], [1, 2, 13, 14], [1, 2, 15, 16], [1, 2, 17, 18], [1, 2, 19, 20],2012-02-14
  • 0
    [1, 2, 21, 22], [1, 3, 5, 7], [1, 3, 6, 8], [1, 3, 9, 11], [1, 3, 10, 12], [1, 3, 13, 15], [1, 3, 14, 16], [1, 3, 17, 19], [1, 3, 18, 20], [1, 4, 5, 8], [1, 4, 6, 7], [1, 4, 9, 12], [1, 4, 10, 11],2012-02-14
  • 0
    [1, 4, 13, 16], [1, 4, 14, 15], [1, 4, 17, 20], [1, 4, 18, 19], [1, 5, 9, 13], [1, 5, 10, 14], [1, 5, 11, 15], [1, 5, 12, 16], [1, 5, 17, 21], [1, 5, 18, 22], [1, 6, 9, 14], [1, 6, 10, 13], [1, 6, 11, 16], [1, 6, 12, 15], [1, 6, 17, 22], [1, 6, 18, 21], [1, 7, 9, 15], [1, 7, 10, 16], [1, 7, 11, 13], [1, 7, 12, 14], [1, 7, 19, 21], [1, 7, 20, 22], [1, 8, 9, 16], [1, 8, 10, 15], [1, 8, 11, 14],2012-02-14
  • 0
    [1, 8, 12, 13], [1, 8, 19, 22], [1, 8, 20, 21], [2, 3, 5, 8], [2, 3, 6, 7], [2, 3, 9, 12], [2, 3, 10, 11], [2, 3, 13, 16], [2, 3, 14, 15], [2, 3, 17, 20], [2, 3, 18, 19], [2, 4, 5, 7], [2, 4, 6, 8], [2, 4, 9, 11], [2, 4, 10, 12], [2, 4, 13, 15], [2, 4, 14, 16], [2, 4, 17, 19], [2, 4, 18, 20], [2, 5, 9, 14], [2, 5, 10, 13], [2, 5, 11, 16], [2, 5, 12, 15], [2, 5, 17, 22],2012-02-14
  • 0
    and so on. There are 263 total.2012-02-14
  • 0
    You are using a greedy algorithm (taking the lowest terms not excluded so far). How do you know this is optimal?2012-02-14
  • 0
    It is a brute force computing method but it got the job done. The question is, is there a formula that we can use to know ahead how many unique combinations we will end up with?2012-02-15
  • 1
    There does n't seem to be any pattern in your sequence or is there ? like consider your example [1, 8, 12, 13], [1, 8, 19, 22], [1, 8, 20, 21], [2, 3, 5, 8]2012-02-15
  • 0
    @Hardy: There is a pattern. There is nothing of the form $[1,9,y,z]$ because for any $y,z$ with $9 \lt y \lt z \le 22$ he already has at least one of $[1,x,9,y]$, $[1,x,9,z]$ or $[1,x,y,z]$ from earlier for some $x$ with $1 \lt x \lt 9$.2012-02-16

0 Answers 0