Prediction of index in Lexicographical ordering of binary sequences? Suppose all $n$ sequences of 0's and 1's were displayed in Lexicographical order. Can the index of sequences that sum to $k$ be predicted?
 A: $\textbf{Better stated question}$: given all possible sequences of $n$ coin flips (a total of $2^n$ many), arrange them lexicographically. Can we find the index of those sequences that have $k$ heads?
$\textbf{Solution}:$ First let us consider a small case example where $n = 10$ and $k = 4$:
\begin{cases}
0000001111 & = 2^{3} + 2^{2} + 2^1 + 2^0 \quad (\text{all $k$ 1's are at the end})\\
0000010111 & = 2^{4} + 2^{2} + 2^1 + 2^0 \quad (k-1\text{ 1's are at the end; one 1 popped to the left})\\
0000011011 & = 2^{4} + 2^{3} + 2^1 + 2^0 \quad (k-2\text{ 1's are at the end; one 1 popped to the left})\\
0000011101 & = 2^{4} + 2^{3} + 2^2 + 2^0\\
0000011110 & = 2^{4} + 2^{3} + 2^2 + 2^1\\
0000100111 & = 2^{5} + 2^{2} + 2^1 + 2^1\\
0000101011 & = 2^{5} + 2^{3} + 2^1 + 2^0\\
& \vdots\\
1111100000 &= 2^{10} + 2^{9} + 2^8 + 2^7 \quad (\text{all} \ k \ \text{1's are to the left})
\end{cases}
Note for the equality I'm just translating binaries into decimals. For the general case, if $k > n$ then no such sequence exist, so assume $k \leq n$. Then the sequence we desire is
\begin{cases}
0....01...1 & = 2^{k-1} + 2^{k-2} + 2^{k-3} +... 2^0 \quad (\text{all $k$ 1's are at the end})\\
0...01011...1 & = 2^{k} + 2^{k-2} + 2^{k-3} + ... + 2^0 \quad (k-1\text{ 1's are at the end; one 1 popped to the left})\\
& \vdots\\
1...10....0 &= 2^n + 2^{n-1} + ... + 2^{n-k+1}
\end{cases}
so the answer is yes. 
