Number of Paths Using Permutations

In summary, the formula for calculating the number of paths using permutations is n! / (n1! * n2! * n3! * ...), where n is the total number of steps and n1, n2, n3, etc. represent the number of steps in each direction. This differs from the number of paths using combinations as permutations take into account the order of steps, while combinations do not. The number of paths using permutations is always a positive integer and cannot be negative. If there are repeated steps, the total number of paths using permutations will decrease. This concept is useful in problems involving arranging or ordering a set of items, as well as in probability problems.
  • #1
Mandelbroth
611
24
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
  • #2
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.
 

FAQ: Number of Paths Using Permutations

What is the formula for calculating the number of paths using permutations?

The formula for calculating the number of paths using permutations is n! / (n1! * n2! * n3! * ...), where n is the total number of steps and n1, n2, n3, etc. represent the number of steps in each direction.

How is the number of paths using permutations different from the number of paths using combinations?

The number of paths using permutations takes into account the order in which the steps are taken, while the number of paths using combinations does not. This means that for permutations, the order of the steps matters, while for combinations, the order does not matter.

Can the number of paths using permutations be negative?

No, the number of paths using permutations is always a positive integer. It represents the total number of possible ways to arrange a given set of steps, and therefore cannot be negative.

How does the number of paths using permutations change if there are repeated steps?

If there are repeated steps, the number of paths using permutations will decrease. This is because when steps are repeated, the number of unique paths decreases, so the total number of paths will also decrease.

In what types of problems would the number of paths using permutations be useful?

The number of paths using permutations is useful in problems that involve arranging or ordering a set of items, such as finding the number of possible routes in a maze or the number of ways a group of people can stand in a line. It can also be used in probability problems, such as calculating the number of possible outcomes in a game with multiple choices.

Similar threads

Back
Top