math - A very complex combinations task that has been bugging me for 7 months -

some 7 months ago went job interview @ big company. gave me task solve, , past 7 months can't seem able find solution.

---

here task: database has entries. how many combinations (without repetition) b amount (b < a) elements made out of there, given b (contained in a) different elements contain @ least x% of c entries (c < b) out of b given (c/b)? include pattern obtaining of them. in short, need:

1. formula calculation of how many combinations satisfy above conditions
2. formula listing of them. (any programming language or detailed descriptive , format)

note: both mandatory, need set in separate table in db.

---

after 2 hours of being totally clueless given simplified version: database has 50 entries. how many combinations (without repetition) 9 elements made out of 50 there, given 9 different elements (contained in 50) contain @ least 15% of 6 entries out of given 9 (6/9)? include pattern obtaining of them. in short, need:

1. formula calculation of how many combinations satisfy above conditions
2. formula listing of them. (any programming language or detailed descriptive , format)

note: both mandatory, need set in separate table in db.

---

edit: explain further. let result of (1.) d possible subsets (combinations without repetition) 9 elements a. , user of database (or software using it) enters random 9 elements (from |a| = 50 set). needs result in, @ least 15% of d subsets has 6 out of 9 user entered. doesn't matter how many of d has 1/9, 2/9, 3/9, 4/9, 5/9, 7/9, 8/9 , 9/9, thing matters 15% , above have 6/9, 9/50 entered. oh , d needs minimal possible.

edit2: further. example: set of a=50 entries given. need minimal amount of possible combinations/subsets without repetition b=9 elements 50, satisfy following: when user enters random 9 entries, 15%+ of resulting subsets must have 6 out of 9 user entered. , resulting subset must uniform 9 user can enter.

---

and still failed. , still clueless of how solve this.

i explain simplified version: let's name database a, |a|=50 elements in it. 6 elements of these 50 special somehow , want keep track of them. call set of these 6 elements c.

now our job: should count subsets x of 9 elements , @ least 15% of elements should come c. since 15% of 9 1.35 need @ least 2 elements of c in our sets x.

we know there binomial(50,9)=2505433700 subsets of 9 elements. lets count how many of them violate criteria: there 44 elements in not in c, there binomial(44,9) subsets of contain no elements c. next count how many 9-element-subsets of contain 1 element of c: take random 8-element-subset without c , put 1 element c it, 6*binomial(44,8) possibilities.

now can write our result, taking all 9-element-subsets , subtracting those, violate criteria: binomial(50,9) - binomial(44,9) - 6*binomial(44,8) = 733107430.

ok... know how there are. how list them? let's use pseude-code it:

aminc := setminus(a,c)  j in 2..6     x1 in subsets(c, j)         x2 in subsets(aminc, 9-j)             print(setadd(x1,x2)) 

this algorithm yields alternative way of counting sets:

binomial(6,2)*binomial(44,7) +...+ binomial(6,6)*binomial(44,3)=733107430.

hope helps..