= Solution
Use <uniform balanced binary sequence sampling> by choosing the positions of the heads. Number the $2n=2^m$ positions from zero to $2n-1$. Start with no selected positions. Repeatedly toss the fair coin $m$ times, interpret the resulting <bits> as a position, and select that position if it has not already been selected; otherwise discard this block of tosses and retry. Stop when $n$ distinct positions have been selected. Put heads at those positions and tails everywhere else.
After $s$ positions have been selected, every one of the remaining positions has the same <probability> of being the next new position. This follows either by summing a <geometric series> over rejected blocks or by conditioning a <uniform distribution on a finite set> on avoiding the selected positions. Every ordered list of $n$ distinct selected positions consequently has <probability>
$$
\frac1{(2n)(2n-1)\cdots(n+1)}.
$$
Each fixed $n$-element <subset> has $n!$ such orders, so its <probability> is
$$
\boxed{\frac{n!}{(2n)(2n-1)\cdots(n+1)}=\frac1{\binom{2n}{n}}.}
$$
Thus every balanced <binary sequence> is equally likely.
When $s$ positions are selected, a block succeeds with <probability> $(2n-s)/(2n)$, so the <geometric distribution> gives <expectation> $2n/(2n-s)$ blocks until the next new position. By <linearity of expectation>, the total expected toss count is
$$
\boxed{m\sum_{s=0}^{n-1}\frac{2n}{2n-s}<2nm=O(n\log n),\qquad n\geq1.}
$$
The strict inequality holds since $s<n$, making each term less than two. A Boolean <array> records membership of each position; initializing it and constructing the output require $O(n)$ additional work. The scheme terminates with <probability> one, since every stage has positive success <probability>.
Back to article page
