5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I was knowing this as leapfrog with black and white sheeps. It has been mathematized meanwhile... $\endgroup$ – zwim Mar 1 '17 at 0:48
  • 1
    $\begingroup$ Looks like this could possibly be the number of Standard Young's Tableaux for a $m\times (n-m)$ Young diagram. The general formula for the number of such Tableaux $T$ with $N$ cells is $|T|=\frac{N!}{\prod_{i=1}^{N}h_i}$ where $h_i$ is the hook length for the $i^{\text{th}}$ cell. In our case $N=m(n-m)$ and the largest hook length $h_1=n$ etc. This can be seen by relating binary sequences first to monotonic lattice paths then to partitions of the rectangle. $\endgroup$ – N. Shales Mar 1 '17 at 1:42
  • 1
    $\begingroup$ $\sigma(n,2)$ are Catalan numbers. $\endgroup$ – user58697 Mar 1 '17 at 1:45
  • 1
    $\begingroup$ $\sigma(n,2)$ being Catalan numbers would agree with the Young Tableaux generalisation. $\endgroup$ – N. Shales Mar 1 '17 at 1:50
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice presentation! (+1) $\endgroup$ – Markus Scheuer Mar 4 '17 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.