Approaches to Counting Paths
Idea · Intermediate
Combinatorics
Idea 1. Placing Numbers
1) Origin = 1.
2) Number at each position = the sum of the numbers at exactly the previous positions.
At each step, we can jump 1 or 2 units to the right or one unit upward.
# ways from \(A\) to \(B\)
Idea 2. Permutation
At each step, we can jump 1 unit to the right or one unit upward.
# ways from \(A\) to \(B\)
Each path corresponds to a permutation of \(5\) \(R\)'s and \(3\) \(U\)'s.
Idea 3. Levels
At each step, we can jump 1 unit to the right, one unit upward, or 1 unit to the left.
We can't pass through a point more than once.
# ways from \(A\) to \(B\)
There are 4 levels (horizontal lines). If we only determine the places where we go to the next level, then the path will be determined.
Starting at \(A\), you want to reach \(B\). At each step, you may move either \(1\), \(2\), or \(3\) units to the right or either \(1\) or \(2\) units upward. How many paths are possible?
Starting at \((0,0)\), you want to reach \((7,5)\).
You may move \((1,0)\), \((0,1)\), or \((1,1)\).
How many paths use exactly one diagonal move?
The diagonal move accounts for one right unit and one up unit.
Therefore, the remaining moves consist of \(6\) right moves and \(4\) up moves.
So every path contains \(6R,\ 4U,\ 1D\).
There are 11 moves altogether.
Therefore, the number of paths is
Thus
Starting at 0, you want to reach 12. At each step, you may move 1, 2, or 3 units to the right.
How many paths are possible?
Starting at \(A\), you want to reach \(B\). At each step, you may move one unit to the right, left, or upward. You cannot pass through the same cell more than once. How many paths are there?
One such path is shown below.
There are 6 levels. Once we determine where the path moves upward from one level to the next, the entire path is determined.
From Level 1 to Level 2, there are 6 possible places to move upward. Similarly, there are 6 choices for each of the other transitions:
These 5 choices are independent, so the total number of paths is