Method wanted

Consider an m×nm\times n rectangular grid . Find the total number of paths one can reach from lower left corner to upper right corner .

Plz post ur method and other variations possible in such questions,

For example the number of shortest path possible from one corner to opposite corner is (m+n)!m!×n!\frac{(m+n)!}{m!\times n!}

I dont know how to solve if its asked number of paths possible to reach from one corner to the corner above it.

Note by Tanishq Varshney
4 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Assume person starts from lower left corner. To take the shortest path, one can travel only up or right in each step. And there are of course, m+nm+n steps to take. In the end, the person is at the top right corner, this means that he/she has traveled mm units up and nn units right. The order in which these steps were arranged is the thing that matters here and is the thing we have to count. Basically you need the coefficient of xnymx^ny^m in (x+y)m+n(x+y)^{m+n}.

Raghav Vaidyanathan - 4 years, 5 months ago

Log in to reply

if total number of possible paths are asked then??

Tanishq Varshney - 4 years, 5 months ago

Log in to reply

Then the answer is infinite, as one can keep going in loops around the grid.

Raghav Vaidyanathan - 4 years, 5 months ago

Log in to reply

@Raghav Vaidyanathan ok, if one is allowed to move p steps noth and q steps east, then

Tanishq Varshney - 4 years, 5 months ago

Log in to reply

@Tanishq Varshney I do not understand your question. How is it different from the one initially discussed in this note?

Raghav Vaidyanathan - 4 years, 5 months ago

Log in to reply

@Raghav Vaidyanathan I mean to say if one has the condition to move 3 steps right and 2 steps up

Tanishq Varshney - 4 years, 5 months ago

Log in to reply

@Tanishq Varshney It is still no different. If one is forced to move only three steps up, then one can take steps upward which are 3 blocks in size. This is same as saying that the person moves upwards one block when the total number of vertical blocks are divided by three.

eg: if there are thirty vertical blocks and person can take three steps only, this is same as 10 vertical blocks when the person is taking one step each.

Raghav Vaidyanathan - 4 years, 5 months ago

Log in to reply

@Tanishq Varshney Can u post solution for the problems ants on a cube

Tanishq Varshney - 4 years, 5 months ago

Log in to reply

well this set helps a lot

Tanishq Varshney - 4 years, 5 months ago

Log in to reply

Yes, I saw that set.. My friend gave me similar qs.. so I din't go for solving them again.

Raghav Vaidyanathan - 4 years, 5 months ago

Log in to reply

Can you add your explanation to Rectangular Grid Paths wiki? Thanks!

Calvin Lin Staff - 4 years, 5 months ago

Log in to reply

it's infinite if you said all path. Obviously, because you told all possible paths, and you can return to a point you started, that makes number of possible paths infinite. What's wrong?

Gian Sanjaya - 4 years, 5 months ago

Log in to reply

I think this problem would be more interesting if it asked for the number of ways to reach the opposite square, not being able to retrace your path, i.e. go on squares you have already been on.

Andrei Golovanov - 4 years, 5 months ago

Log in to reply

right. I guess that's what meant

Gian Sanjaya - 4 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...