Hi ,

Suppose that you pick N numbers . What is the minimum number of "k-combinations" needed to cover all "m-combinations." ( m < k < N )

What is the formula to find out this ?

Example

We picked up 5 numbers from 1 to 5 . And we want to list enough 3-combinations to cover all 2-combinations.

2-combinations are C(5,2) = 10

-------------------

1-2

1-3

1-4

1-5

2-3

2-4

2-5

3-4

3-5

4-5

3-Combinations are C(5,3) = 10

------------------

1-2-3

1-2-4

1-2-5

1-3-4

1-3-5

1-4-5

2-3-4

2-3-5

2-4-5

3-4-5

Minumum Number of 3-combinations needed to cover all 2-combinations is 4.

----------------------------------------------

1-2-3 ( Covers 1-2,1-3,2-3)

1-4-5 ( Covers 1-4,1-5,4-5)

2-4-5 ( covers 2-4,2-5 and also 4-5)

3-4-5 ( Covers 3-4,3-5 and also 4-5)