Number of paths that can be taken

  • Thread starter Thread starter Punkyc7
  • Start date Start date
Click For Summary
SUMMARY

This discussion focuses on calculating the number of paths from point A to point B in a grid, specifically addressing three scenarios: total paths, paths without consecutive downward moves, and paths avoiding a designated orange region. The participants suggest using combinatorial mathematics, specifically binomial coefficients, to derive the number of paths. For the total paths, the initial estimate is 10C4, while for paths avoiding consecutive downward moves, estimates include 4C3 or 5C3. The calculations for paths avoiding the orange region involve breaking down the problem into shaded and non-shaded areas, with suggested coefficients of 7C3 and (8C4)/2.

PREREQUISITES
  • Understanding of combinatorial mathematics and binomial coefficients
  • Familiarity with grid-based pathfinding problems
  • Basic knowledge of permutations and combinations
  • Ability to analyze and break down geometric regions in mathematical problems
NEXT STEPS
  • Study combinatorial path counting techniques in grid problems
  • Learn about the application of binomial coefficients in combinatorial mathematics
  • Explore restrictions in pathfinding, such as avoiding specific regions
  • Investigate advanced counting techniques, including the principle of inclusion-exclusion
USEFUL FOR

Mathematicians, computer scientists, and students studying combinatorial optimization or pathfinding algorithms will benefit from this discussion.

Punkyc7
Messages
415
Reaction score
0
In this problem we want to count the paths that go from point A to point B in the following diagram, moving along the lines and in each step moving either one unit down or one unit to the right.

In the picture the boxes should be evenly spaced.
1.) The number of paths is___________________

2.) How many paths are there that include no two consecutive downward move?

3.) How many paths are there that do not enter the orange region? For number one I was thinking that there are 10 different paths we could take and at most we could only take 4 so I'm thinking it 10C4.

For number 2 I was thinking that it is going to be something like 4C3 or 5C3 but I am not sure.

For number 3 I decided to break it up into the shaded region and the none shaded region. For the none shaded region I think there is 7C3 paths and for the shaded I think there (8C4)/2. I don't think that is right because 7C3 +8C4 does not equal 10C4 that I said for one.

Any help would be greatly appreciated.
 

Attachments

  • Triangle.jpg
    Triangle.jpg
    10.8 KB · Views: 394
Last edited:
Physics news on Phys.org
of what?
 
Sorry about that I hit enter after the title thinking it would go down to the next text box
 

Similar threads

  • · Replies 8 ·
Replies
8
Views
1K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 1 ·
Replies
1
Views
961
  • · Replies 21 ·
Replies
21
Views
4K
  • · Replies 15 ·
Replies
15
Views
3K
  • · Replies 24 ·
Replies
24
Views
2K
  • · Replies 20 ·
Replies
20
Views
4K
  • · Replies 12 ·
Replies
12
Views
3K
  • · Replies 15 ·
Replies
15
Views
3K