Consider a set S1 composed by all the possible combinations of N elements given K, $\binom{N}{K}$, $N > K$.
Now let's consider another set, S2, composed by all the possible combinations of N elements given H, $\binom{N}{H}$, when $N > H > K$.
For each element of set S2 it is possible to generate all the combinations of its items, given K, $\binom{H}{K}$. Let's call this operation applied on these items "OP1".
How to calculate the minimum number of elements from S2 that generates the set "R", resulting from the union of the outcomes of the operation "OP1" applied to each of the selected elements, so that R equals S1?
Is there a "formula" that would return the result, with the variables N, H and K ?
I can calculate this by "brute-forcing" by hand (small enough numbers), or in a computer, but I am having a hard time deriving a formula for that.
Simple examples:
- If N=6, H=5 and K=4, the minimum number of elements of "S2" that satisfies the conditions is 5.
- If N=6, H=4 and K=3, the minimum number of elements of "S2" that satisfies the conditions is 8.
Best Answer
What you ask is in general an open problem, there are definitely no formulas.
A collection of $H$-element subsets of an $N$-element set which cover all $K$-element subsets is known as a covering design. The size of the smallest covering design is denoted $C(N,H,K)$. You can see the best known bounds on $C(v,k,t)$ as the La Jolla covering repository. For example, the table entry for $C(6,4,3)$ (link) shows that your collection of $8$ sets is suboptimal, and you can actually get away with only $6$ sets.
The Schonheim bound (mentioned in the first paragraph of this paper) provides the following general lower bound on $C(v,k,t)$: $$ C(v,k,t)\ge \left\lceil\frac vk\left\lceil \frac {v-1}{k-1}\cdots\left\lceil \frac{v-t+1}{k-t+1}\right\rceil\right\rceil\right\rceil $$ For example, $C(6,4,3)\ge \left\lceil\frac 64\left\lceil \frac 53\left\lceil \frac42\right\rceil\right\rceil\right\rceil=6$. In this case, the lower bound is achievable, but not always.
There are a large variety of methods to find covering designs, usually involving a mix of brute force and cleverness. There is too much on the topic to go into in this answer, but hopefully this is enough to get you started on your research.