# the number of loops on lattice?

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? btw:i asked this question before, but had not get an answer yet. Maybe I can get a good answer at here.

-
Do you mean a square lattice? – kennytm Aug 26 '10 at 13:46
@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? – Joseph O'Rourke Aug 26 '10 at 14:03
Yes, square lattice! Yes, the returning path does not cross the first path! – a boy Aug 26 '10 at 14:06
In representation theory these things are called skew Young diagrams; searching with that keyword might give you something. – Qiaochu Yuan Aug 26 '10 at 16:24

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}$.

-
Ah, I can't believe I didn't notice that! Nice solution. – Qiaochu Yuan Aug 26 '10 at 21:10
I don't understand the non-determinantal explanation that you gave for the solution to the problem. Could you please explain in more words? – quantumelixir Oct 21 '11 at 6:38
@quantumelixir See updated version. – Grigory M Oct 23 '11 at 11:35