Finding number of paths via combinatorics

In summary: This is what you have written above. In summary, to find the total number of paths from (0,0) to (a,b) with c reverse horizontal movements and d reverse vertical movements, we use the formula (a+b+2c+2d)! / (a+c)!(b+d)!c!d!.
  • #1
Sprooth
17
0
Hi,

I'm trying to figure out a variation of the problem where you determine the number of paths on a discrete grid from one point to another. For example, for the paths from (0,0) to (a,b), you can consider one path to be a rearrangement of a word with a x's and b y's, so the number of paths is (a+b)! / a!b!.

The variation I would like to figure out would allow a specified number of reverse movements in addition to the movements in the proper direction. I am representing a movement to the right by "x", a movement to the left by "w", a movement upward by "y", and a movement downward by "z". If I am finding a path from (0,0) to (a,b) with c reverse horizontal movements and d reverse vertical movements, then the number of paths I have so far would be:

(a + b + 2c + 2d)! / (a+c)!(b+d)!c!d!

since the paths could be considered as a rearrangement of a word made of a+c x's, b+d y's, c w's and d z's. (a+c x's since there must be an additional movement to the right for every allowed movement to the left.

I believe this is correct so far, but now I want to prevent paths where for example it goes right, then left, then right with a net result of just going right. To do this I want to find rearrangements of the word where there are no adjacent x's and w's and no adjacent y's and z's. I began by simplifying the problem to one where only reverse horizontal movements were allowed and I would then attempt to generalize to the case with reverse movements in both dimensions. However, I got stuck even in the simpler case.

I've tried thinking about the problem from several viewpoints, one of which included considering integer partitions, but I really haven't gotten anywhere.

Maybe someone could help me through the simpler case (where there would be x's for going right, y's for going up, and w's for going left)? Then I will try to generalize to the other case.

Thanks for your help.
 
Physics news on Phys.org
  • #2
The way I would approach this problem is by first figuring out how many paths there are without any reverse movements. In this case, it would be (a+b)! / a!b!, as you said. Then, we can subtract the paths where there is at least one reverse movement. For the simpler case, let's assume there are only reverse horizontal movements. To do this, we can break down the problem into two parts: 1) The number of paths with at least one reverse horizontal movement. 2) The number of paths with no reverse horizontal movements. For part 1, let's assume there are c reverse horizontal movements. Then, the total number of paths with at least one reverse horizontal movement is c * (a+b)! / (a+c)!b!. This is because, for each reverse horizontal movement, the total number of paths is (a+b)! / (a+c)!b!. For part 2, the total number of paths with no reverse horizontal movements is (a+b)! / a!b!, as you calculated earlier. Therefore, the total number of paths with c reverse horizontal movements is (a+b)! / (a+c)!b! - (a+b)! / a!b!. This is what you have written above. Now, to generalize to the case with reverse movements in both dimensions, let's assume there are c reverse horizontal movements and d reverse vertical movements. Then, the total number of paths with at least one reverse movement is c*(a+b+2d)! / (a+c+d)!(b+d)!d! + d*(a+b+2c)! / (a+c)!(b+c)!c!. This is because, for each reverse horizontal movement, the total number of paths is (a+b+2d)! / (a+c+d)!(b+d)!d! and for each reverse vertical movement, the total number of paths is (a+b+2c)! / (a+c)!(b+c)!c!. Therefore, the total number of paths with c reverse horizontal movements and d reverse vertical movements is (a+b+2c+2d
 

Related to Finding number of paths via combinatorics

What is combinatorics?

Combinatorics is a branch of mathematics that deals with the study of counting and arranging objects in a systematic way.

How is combinatorics related to finding number of paths?

Combinatorics can help in finding the number of paths by providing a systematic approach to counting the different possibilities and combinations of paths.

What are the different approaches in combinatorics for finding number of paths?

There are several approaches in combinatorics for finding number of paths, such as using permutations, combinations, and the inclusion-exclusion principle.

What factors influence the number of paths in a given scenario?

The number of paths in a given scenario is influenced by factors such as the number of starting points, the number of ending points, and any constraints or restrictions on the paths.

How can combinatorics be applied in real-life situations for finding number of paths?

Combinatorics can be applied in various real-life situations, such as finding the number of possible routes in a transportation system, the number of possible outcomes in a game, or the number of possible combinations of ingredients in a recipe.

Similar threads

  • Calculus and Beyond Homework Help
Replies
10
Views
741
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
18
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
569
  • Calculus and Beyond Homework Help
Replies
3
Views
571
  • Calculus and Beyond Homework Help
Replies
2
Views
798
  • Calculus and Beyond Homework Help
Replies
10
Views
669
  • Calculus and Beyond Homework Help
Replies
14
Views
873
  • Calculus and Beyond Homework Help
Replies
2
Views
657
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
Back
Top