Number of Paths Using Permutations

  • Thread starter Mandelbroth
  • Start date
  • Tags Tags
    Permutations
1 reply · 2K views · last reply
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:
Square 4 by 4 grid with point alpha in red at the top left corner, point gamma in green at the centre, and point beta in blue at the bottom right corner.


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?
 
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:
Four-by-four square grid with a red point alpha at the top-left corner, a green point gamma at the center, and a blue point beta at the bottom-right corner.


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.