Learn this distribution from samples? What is the sample complexity? $\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$
We have an $n$-variate distribution $X\in\{0,1\}^n | \sum_i^n X_i = k$. Or, in other words, we are guaranteed that only $k$ variables will be $1$ in any given trial. Therefore, there are only $n \choose k$ possible outcomes. We will call $P(X_i = 1) = p_i$, $P(X_i=1 ~\land~X_j=1) = p_{ij}$, and so on. 
We are given $m$ samples from this distribution. With the samples, we can estimate the true distribution using an empirical estimator (or MLE, maximum likelihood estimator). We call the estimated distribution $\hat{X}$. What is the smallest $m$ can be for which we can make sure that $\hat{X}$ is close to $X$? Specifically, how small can $m$ be such that $P(\norm{\hat{X} - X}_1 \geq \epsilon) \leq \delta$ for some $\epsilon$ and $\delta$? How small can $m$ be such that $P(\norm{\hat{X}-X}_2 \geq \phi) \leq \gamma$ for some $\phi$ and $\gamma$?
I'm interested in the case where $n$ is known and there is no restriction on $k$.
 A: *

*$\ell_2$ won't be "interesting." You can learn any discrete distribution to $\ell_2$ distance $\phi$ with probability $1-\gamma$ with $O( \log(1/\gamma)/\phi^2 )$ samples, with no dependence on the domain size. And this will be tight even with your constraint (pretty much any estimation, even on a single bit, will require that many samples).

*Now, in total variation/$\ell_1$. You basically have, as you say, an arbitrary distribution on $M = \binom{n}{k}$ elements. Learning this to total variation distance $\varepsilon$, w.p. $1-\delta$, can be done with
$$
O\left( \frac{M + \log(1/\delta)}{\varepsilon^2}  \right)
$$
samples, and this is tight (up to constants). So the answer is 
$$
\Theta\!\left( \frac{\binom{n}{k} + \log(1/\delta)}{\varepsilon^2}  \right)
$$
Note: the upper bound is not going to be efficient in $n$ (but is efficient in the number of samples, and achieved by the empirical estimator) if $k$ is not a constant, as then you have a sample complexity super-polynomial in $n$ (e.g., $k=n/2$ leads to roughly  a $2^{n}/\sqrt{n}$ dependence).
