Number of Paths Using Permutations

  • Thread starter Thread starter Mandelbroth
  • Start date Start date
  • Tags Tags
    Permutations
Click For Summary
SUMMARY

The discussion centers on calculating the number of distinct paths in a grid from point α to point β and then to point γ. The first segment of the journey from α to β involves 4 downward and 4 rightward moves, yielding a total of 70 unique paths calculated using the formula 8!/(4! * 4!). The second segment from β to γ consists of 2 upward and 2 leftward moves, resulting in 6 unique paths calculated using the formula 4!/(2! * 2!). The overall total number of distinct paths from α to β to γ is confirmed to be 420.

PREREQUISITES
  • Understanding of combinatorial mathematics
  • Familiarity with factorial notation
  • Knowledge of grid-based movement constraints
  • Ability to apply binomial coefficients in path counting
NEXT STEPS
  • Study combinatorial path counting techniques
  • Learn about binomial coefficients and their applications
  • Explore grid movement problems in discrete mathematics
  • Investigate advanced combinatorial algorithms for pathfinding
USEFUL FOR

Students in mathematics, particularly those studying combinatorics, educators teaching grid-based movement problems, and anyone interested in solving pathfinding challenges in discrete structures.

Mandelbroth
Messages
610
Reaction score
23
I'm pretty sure I'm right, but I'd appreciate it if I could obtain some verification.

Homework Statement


Consider the following grid:
2ij0xw6.jpg


The goal is to move from point [itex]\alpha[/itex] to point [itex]\beta[/itex] to point [itex]\gamma[/itex] by moving along the edges of the grid from point to point. You can only move to the right or down from [itex]\alpha[/itex] to [itex]\beta[/itex], and you can only move left or up from [itex]\beta[/itex] to [itex]\gamma[/itex]. You cannot move outside the grid.

How many distinct paths are there from [itex]\alpha[/itex] to [itex]\beta[/itex] to [itex]\gamma[/itex]?

2. The attempt at a solution
I split this into two parts. The first part, [itex]\alpha[/itex] to [itex]\beta[/itex], consists of some combination of moves, but always consists of moving down 4 times and to the right 4 times. Thus, the total number of paths will be [itex]\frac{8!}{4! \cdot 4!} = 70[/itex].

The second part is from [itex]\beta[/itex] to [itex]\gamma[/itex]. It's the same thing, but with 2 moves up and 2 moves left. Thus, the number of paths will be [itex]\frac{4!}{2! \cdot 2!} = 6[/itex].

Thus, the total number of paths is [itex]70 \cdot 6 = 420[/itex]. Am I correct?
 
Physics news on Phys.org
Mandelbroth said:
I'm pretty sure I'm right, but I'd appreciate it if I could obtain some verification.

Homework Statement


Consider the following grid:
2ij0xw6.jpg


The goal is to move from point [itex]\alpha[/itex] to point [itex]\beta[/itex] to point [itex]\gamma[/itex] by moving along the edges of the grid from point to point. You can only move to the right or down from [itex]\alpha[/itex] to [itex]\beta[/itex], and you can only move left or up from [itex]\beta[/itex] to [itex]\gamma[/itex]. You cannot move outside the grid.

How many distinct paths are there from [itex]\alpha[/itex] to [itex]\beta[/itex] to [itex]\gamma[/itex]?

2. The attempt at a solution
I split this into two parts. The first part, [itex]\alpha[/itex] to [itex]\beta[/itex], consists of some combination of moves, but always consists of moving down 4 times and to the right 4 times. Thus, the total number of paths will be [itex]\frac{8!}{4! \cdot 4!} = 70[/itex].

The second part is from [itex]\beta[/itex] to [itex]\gamma[/itex]. It's the same thing, but with 2 moves up and 2 moves left. Thus, the number of paths will be [itex]\frac{4!}{2! \cdot 2!} = 6[/itex].

Thus, the total number of paths is [itex]70 \cdot 6 = 420[/itex]. Am I correct?

Seems fine to me.
 

Similar threads

  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 10 ·
Replies
10
Views
2K
  • · Replies 20 ·
Replies
20
Views
3K
  • · Replies 17 ·
Replies
17
Views
4K
  • · Replies 5 ·
Replies
5
Views
3K
Replies
7
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 10 ·
Replies
10
Views
2K
Replies
3
Views
2K
Replies
46
Views
7K