<s>[INST] Minimum number of $k$-partitions of a set of size $n$ to enumerate all $n \choose k$ combinations Given a set $\mathcal{S}$ of size $n$, let a $k$-partition of $\mathcal{S}$ be a grouping into $k$ disjoint classes $$(S_1 ,S_2,...,S_k)$$ 
Where the $S_i$ do not necessarily contain the same number of elements.
Let $C(S_1, S_2, ... S_k)$ be the set of combinations which can be made by taking exactly one element of each class, (i.e. $C(S_1, S_2, ... S_k)$ is the Cartesian Product $S_1 \times S_2 \times ...\times S_k$). For a given $(n,k)$, what is the minimum number of k-partitions $N$ such that
$\bigcup\limits_{i=1}^{N} C(S_1^{(i)}, S_2^{(i)}, ...,S_3^{(i)}) = $ All Possible Combinations
Example:
for $n=4$ and $k=2$, $\mathcal{S} = \{1,2,3,4\}$ we can choose:
$$ S^{(1)} = \left\{\left\{ 1, 2\right\}, \left\{ 3, 4\right\}\right\}$$
$$ S^{(2)} = \left\{\left\{ 1, 3\right\}, \left\{ 2, 4\right\}\right\}$$
Then $$C_{1} = \left\{\left\{ 1, 3\right\} ,\left\{ 1, 4\right\},\left\{ 2, 3\right\},\left\{ 2, 4\right\}\right\}$$
$$C_{2} = \left\{\left\{ 1, 2\right\} ,\left\{ 1, 4\right\},\left\{ 2, 3\right\},\left\{ 3, 4\right\}\right\}$$
and $C_1 \cup C_2 =$ All possible combinations and $N=2$.
 [/INST] Rather than $N$ I'm going to use the OEIS convention $T(n, k)$ (for triangle, I think).
Misha Lavrov's answer gives the bound $$T(n, k) \ge \frac{\log n - \log(k-1)}{\log k - \log(k-1)}$$
Another, easier, lower bound uses the auxiliary function A152072 which gives the largest possible size of the Cartesian product $S_1 \times S_2 \times \cdots \times S_k$: then clearly $$T(n, k) \ge \frac{\binom n k}{\textrm{A152072}(n, k)} = \frac{\binom n k}{ \left\lceil n/k \right\rceil^{n \bmod k} \left\lfloor n/k\right\rfloor^{k-n \bmod k}}$$
Neither of these bounds is always better than the other. In fact, we can go further. Note that when $k = n-1$ Misha's bound is $2$, whereas my bound is $\left\lceil\frac n2\right\rceil$ (and this is tight: consider $S_1^{(i)} = \{2i, (2i+1) \bmod n\}$, all other $S_j^{(i)}$ are singletons). On the other hand, when $k=2$ Misha's bound is $\left\lceil \log_2 n\right\rceil$, whereas my bound is $2$. Therefore neither bound is asymptotically tight.

Looking at actual figures, we have (starting at $n=1$, $k=1$)
$$\begin{matrix}1 \\
1& 1 \\
1& 2& 1 \\
1& 2& 2& 1 \\
1& 3& 3& 2& 1 \\
1& 3& 3& 3& 2& 1 \\
1& 3& 4& 3& 3& 2& 1 \\
1& 3& 4& 4& 4& 3& 2& 1\end{matrix} \textrm{ vs }\quad \begin{matrix}1 \\
1& 1 \\
1& 2& 1 \\
1& 2& 2& 1 \\
1& 2& 3& 3& 1 \\
1& 2& 3& 4& 3& 1 \\
1& 2& 3& 5& 6& 4& 1 \\
1& 2& 4& 5& 7& 7& 4& 1
\end{matrix}$$
for a combined lower bound of
$$\begin{matrix}1 \\
1& 1 \\
1& 2& 1 \\
1& 2& 2& 1 \\
1& 3& 3& 3& 1 \\
1& 3& 3& 4& 3& 1 \\
1& 3& 4& 5& 6& 4& 1 \\
1& 3& 4& 5& 7& 7& 4& 1\end{matrix}$$

By brute force, the actual start of the table should be
$$\begin{matrix}1 \\
1& 1 \\
1& 2& 1 \\
1& 2& 2& 1 \\
1& 3& 3& 3& 1 \\
1& 3& 3& 5& 3& 1 \\
1& 3& 4& 6& 6& 4& 1 \\
1& 3& 4& 6& 8& 8& 4& 1\end{matrix}$$
</s>