11
$\begingroup$

Walking on a lattice. The number of various paths from $(0,0)$ to $(m,n)$ using north and east steps is binomial coefficient

$C(m+n,m)$

if he needs to go back $(0,0)$ using south and west steps, and doesn't pass by the passed points. Then what is the number of various loops walking from $(0,0)$ to $(m,n)$ then returning to $(0,0)$? Any algebraic expression for this? alt text btw:i asked this question before, but had not get an answer yet. Maybe I can get a good answer at here.

  • 0
    Do you mean a *square* lattice?2010-08-26
  • 0
    @a-boy: "and doesn't pass by the passed points": Do you mean, the returning path does not cross the first path? So the result is a simple polygon?2010-08-26
  • 1
    Yes, square lattice! Yes, the returning path does not cross the first path!2010-08-26
  • 0
    In representation theory these things are called skew Young diagrams; searching with that keyword might give you something.2010-08-26

1 Answers 1

12

The number of loops is just the number of pairs of non-intersecting paths s.t. first one goes from (0,1) to (m-1,n) and the second one goes from (1,0) to (m,n-1).

Non-intersecting paths on a lattice are counted by some determinant formula. In this case it's just $\det\left(\begin{matrix}\binom{m+n-2}{m-1}&\binom{m+n-2}{m-2}\\\\\binom{m+n-2}{n-2}&\binom{m+n-2}{n-1}\end{matrix}\right)=\binom{m+n-2}{m-1}^2-\binom{m+n-2}{m-2}\binom{m+n-2}{n-2}$.

It's not hard to prove this formula directly: a pair (path from (0,1) to (m-1,n); path from (1,0) to (m,n-1)) either forms a loop without intersection or (if paths intersect) can be (canonically) identified with a pair (path from (0,1) to (m,n-1); path from (0,1) to (m,n-1).


Upd. quantumelixir asked for more detailed explanation. Here it is.

  1. The number of (monotonic) lattice paths from $(a,b)$ to $(a',b')$ is $\binom{(a'-a)+(b'-b)}{a'-a}$.

  2. Any loop can be decomposed into 2 paths: first one, going from $(0,1)$ to $(m-1,n)$, and second one, going from $(1,0)$ to $(m,n-1)$.

  3. There are $\binom{m+n-2}{m-1}$ paths of each type.

  4. But not every such pair gives a loop: we need to count only pairs that don't interesect; or, equivalently, we need to count the number $I$ of pairs of such paths s.t. they do intersect — the answer to the original question will be $\binom{m+n-2}{m-1}^2-I$.

  5. There is an obvious bijection between the set of intersecting pairs (path $(0,1)\to(m-1,n)$, path $(1,0)\to(m,n-1)$) and the set of intersecting pairs (path $(1,0)\to(m-1,n)$, path $(0,1)\to(m,n-1)$) — namely, “go by the first path (of the pair) till the (first) intersection point, then go by the second path”.

  6. So $I$ is the number of intersecting pairs (path $(1,0)\to(m-1,n)$, path $(0,1)\to(m,n-1)$). But any such pair is intersecting!

  7. So $I$ is just $\binom{m+n-2}{m-2}\binom{m+n-2}{n-2}$. And the final answer is $\binom{m+n-2}{m-1}^2-\binom{m+n-2}{m-2}\binom{m+n-2}{n-2}$.

  • 3
    Ah, I can't believe I didn't notice that! Nice solution.2010-08-26
  • 0
    I don't understand the non-determinantal explanation that you gave for the solution to the problem. Could you please explain in more words?2011-10-21
  • 1
    @quantumelixir See updated version.2011-10-23
  • 0
    very interesting, thanks for the detailed explanation2018-09-12