Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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

1 Answer 1

up vote 11 down vote accepted

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

share|improve this answer
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
1  
@quantumelixir See updated version. –  Grigory M Oct 23 '11 at 11:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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