Conference rusure::math

1936.0. "permutation problem" by CLARID::HOFSTEE (What would you do if it was YOUR company?) Thu Feb 16 1995 06:48

Since I didn't get an answer in the brain_bogglers file (too difficult?), 
I'll try it here...

I am having a question about permutations. It's a problem I posed myself, so for
which I don't have the answer. Maybe someone overhere knows how to solve it?

Problem:
---------
The number of permutations that are possible when selecting x items out of y, is
given by the formula:

	y!
p(x,y)=----------
	x! (y-x)!

For example , when selecting 5 items out of 8 , there are 56 permutations
(assuming that order is not important).

When selecting 4 items out of 8, there are 70 permutations.

Now when I look for example at the first '5-out-of-8' permutation
11111000, it covers the '4-out-of-8' permutations:

11110000
11101000
11011000
10111000
01111000

Question:


1.How many  x-out-of-y permutations  
does it take to cover all (x-p,y) permutations? For example, I figured out that
for y=7, x=5, p=1 (cover all 4-out-7 permutations with the minimum number of
5-out-of-7 permutations), the answer is 9. What is the general formula?

2.How does one generate these permutations. eg. How to figure out which 9
5-ou-of-7 permutations cover all 4-out-of-7 permutations? For this example, I
figured out by brute-force, that the following 9 combinations fit :

1111100
1110011
1101011
1100111
1011011
1010111
1001111
0111110
0111101

But is there a 'smart way' to generate these instead of brute force (eg.
comparing all combinations with each other).


First correct answer wins. I have the answers for y=5-10, x=3-5, p=1-3 but for
higher y the calculation time becomes prohibitive.

First correct answer wins .....:):)

Thanks


Timo 

    See topic 746.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.