I have an orthogonal basis of dimension $d \gg n$, and I want to generate $x$ samples using the smallest subset of that basis with a sparsity level $p$.
How to find the smallest $n$ in $$\left \lvert {n \choose k} - x \right \rvert\leq \epsilon,$$ for a given $x$, a small $\epsilon > 0$, $k= p\times n$, and $0.1 \leq p \leq 0.3$.
If a closed-form solution is not possible, is there any math result that can be used to solve this using on a computer program?
It's doubtful that there is a closed-form. That said, using, say, Stirling's expansion, one has $$ {n \choose pn}\approx 2^{(1+o(1))H(p)n}, $$ where $H(p)=-p\log_2(p)-(1-p)\log_2(1-p)$ is the binary entropy function. Setting this equal to $x$ tells you that \begin{equation} n\approx \frac{\log_2 x}{H(p)}, \end{equation} so if you need an exact answer, you can search for values of $n$ close to this to simplify the brute force search.