## Ishaan94 Group Title The streets of a city are arranged like the lines of a chess-board. Let the dimensions be $$m \times n$$. Find the number of ways in which a man can travel from the North-West corner to the South-East corner, going the shortest possible distance. 2 years ago 2 years ago

1. karatechopper Group Title

thts a lot of turns i can take x(

2. experimentX Group Title

Kinda sounds like problem asked by FFM

3. karatechopper Group Title

who know when i could get lost :/ @Diyadiya will drive me! then no need to worry!

4. Ishaan94 Group Title

It is similar to FFM's problem.

5. experimentX Group Title

then it must be related to this http://en.wikipedia.org/wiki/Motzkin_number

6. experimentX Group Title

n+1th Mozkin's no

7. karatechopper Group Title

8. karatechopper Group Title

o wait not yet!

9. experimentX Group Title

|dw:1339345895603:dw| seems to be six int this case

10. Zarkon Group Title

yes...six..$${4\choose 2}$$

11. Zarkon Group Title

maybe I should write it ${2+2\choose 2}$

12. experimentX Group Title

|dw:1339346361572:dw|

13. experimentX Group Title

|dw:1339346637952:dw|

14. experimentX Group Title

so for 2x3 ...we have 10

15. Zarkon Group Title

${5 \choose 2}$

16. experimentX Group Title

so adding one segments ... $\binom {4 + 1}{2}$

17. Zarkon Group Title

${3+2\choose 2}$

18. experimentX Group Title

|dw:1339346850772:dw|

19. Zarkon Group Title

for your 3x2 you will have to go 3 units up and 2 units to the right in total to get to the upper right hand corner UUURR the number of ways to arrange these letters is $${3+2\choose 2}$$

20. experimentX Group Title

|dw:1339346924974:dw|

21. experimentX Group Title

2*4+2*10+6*3 = $$\binom{9}{2} = \binom{3 + 3 + 3}{2}$$

22. Zarkon Group Title

there are only 20 ways for a 3x3

23. Zarkon Group Title

${m+n\choose n}$

24. goxenul Group Title

Yeah, because you take m+n steps and you must decide which n of them will be right, or which m of them will be down (it's equivalent).

25. Zarkon Group Title

yes

26. experimentX Group Title

isn't there 36 steps in 3x3??

27. Zarkon Group Title

show me a path that requires 36 steps

28. experimentX Group Title

something wrong with draw app here ... can't copy my own drawing!!

29. Zarkon Group Title

only 6 steps are needed to get to the bottom right

30. experimentX Group Title

|dw:1339348259654:dw|

31. Zarkon Group Title

there are 6 ways to do a 2x2 not 10

32. experimentX Group Title

Oh .. i made mistake then ... it must be 3x2

33. experimentX Group Title

|dw:1339348688431:dw|

34. Zarkon Group Title

yes

35. experimentX Group Title

shouldn't it be 2*3*3+2*4+2*6 = 38 ??

36. Zarkon Group Title

try and draw 38 minimum distance paths using that graph

37. siddhantsharan Group Title

I'm getting ( m + n -2)!/(m-1)!(n-1)! ??????

38. siddhantsharan Group Title

|dw:1339384651187:dw|

39. siddhantsharan Group Title

Let each square formed be a unit square. Therefore if a man needs to get from NW to south east, He basically needs to cover "n-1" units on the east line. And "m-1" units south. --- For the Shortest possible path when he decides to never turn back. Now in order to do this each street taken by him must be in the South or east direction. Every time he goes east Lets call that turn/ street taken E. Every time he turns south we call that S. So any path followed by him can be written as: SSESESESSSSEEE........... ----- Meaning the man goes first south then south again without turning at next intersection Then turns east at the next turn.......... Here number of S's = m-1 No. of E's = n-1. So the problem has become an equivilant of Finding the permutations of n-1 E's and m-1 S's. = ( m -1 + n -1)! ----------------- (m-1)!(n-1)!

40. Zarkon Group Title

|dw:1339422624581:dw| this is a 1x1 block so m=1 and n=1 using your formula $\frac{(1-1+1-1)}{(1-1)!(1-1)!}=\frac{0!}{0!0!}=1$ but there are 2 paths to the end

41. siddhantsharan Group Title

My formula deals with streets. => lines. => m = 2, n=2 in this caase

42. Zarkon Group Title

mine does not

43. Zarkon Group Title

I go by the number of blocks created and the number of steps to go from one corner to the other for a 1x1 block you have to go down 1 and to the right 1

44. experimentX Group Title

should have never doubted @Zarkon http://math.stackexchange.com/questions/103470/how-can-i-find-the-number-of-the-shortest-paths-between-two-points-on-a-2d-latti