Consider a N-d hypercube. All the nodes (cube corners) are connected with arches, and there are 2^N corners. If I begin at a specific node, to how many nodes can I reach if I make r moves along r different dimensions?
For example: on 3d:
1 step is 3
2 steps is 6
3 steps is 7(all possible corners)
Thanks,
There are $N$ possible dimensions we can move in, and we make $r$ moves. Also, notice that the order in which we move does not matter: it's only a matter of choosing the $r$ dimensions to move in out of $N$ total. So we will be able to reach $\left( \begin{array}{c} N \\ r \end{array} \right)$ more nodes on the $r$-th step than we were able to on the $r-1$ step.
Therefore, by the way you have counted it, on the $r$-th step we will reach $\left( \begin{array}{c} N \\ 1 \end{array} \right) + \left( \begin{array}{c} N \\ 2 \end{array} \right) + \dots + \left( \begin{array}{c} N \\ r \end{array} \right)$ nodes total.