Let $1 \leq m \leq n \in \mathbb{N}$. Consider the string $$ b = \underbrace{0\dots0}_{n-m} \underbrace{1\dots1}_m $$ A step on $b$ changes a combination of $01$ into a combination of $10$. (e.g. $0011 \to 0101$) A path on $b$ is a ordered collection of steps so that the net result of the steps is $$ b' = \underbrace{1\dots1}_m \underbrace{0\dots0}_{n-m} $$ Let $\sigma(n,m)$ be the number of paths on $b$ for $n,m$. Is there an expression (recursive or not) for $\sigma$ in terms of $n,m$?
What I have observed: $$ \sigma(n,0) = \sigma(n,1) = 1, \qquad \sigma(n,m) = \sigma(n,n-m) $$ I am trying to come up a relation between $\sigma(n,m)$ and $\sigma(n,m-1)$ but don't know a way to achieve this.
This problem is closely related to Hook Length Formula.
The formula gives a way how to compute the number of fillings of a matrix $m\times n$ with distinct numbers $1, 2, \ldots, mn$ in such a way that all rows and all columns are increasing. Whenever you have such a matrix, you can translate it into a process of $m$ zeros jumping to the right to the position of $n$ ones. And because zeros sounds too bad, from now on I will call them heroes :-)
At first, imagine the heros on the left of the matrix, on every row there is a hero at the "starting" position. Now you are saying the sequence $1, 2, 3, \ldots, mn$ and every time a hero has the pronounced number in front of them, he jumps behind it. So on the end, heroes are on the right of the matrix. Now, to make the original jumping process out of it, you just shear it to the right and flatten columns. So for instance $$ \matrix{1 & 2 \\ 3 & 4} $$ is translated into "the first hero makes two jumps and then the second hero makes two jumps", so it corresponds to $$0011\to0101\to0110\to1010\to1100$$ and matrix $$ \matrix{1 & 3 \\ 2 & 4} $$ is translated into "First hero, second hero, first hero, second hero", so $$ 0011\to0101\to1001\to1010\to1100. $$
The statement of hook length formula (see the Wiki) is very pretty but unfortunately there is no simple proof of it. For our case it is $$ (mn)\;\cdot\;!1!2!\cdots(m-1)!\over n!(n+1)!(n+2)!\cdots(n+m-1)! $$ Notice that I am using $m$ zeros and $n$ ones instead of $n-m$ so you have to substitute it to get the exact answer.