Pascal’s triangle and Counting Permutations

This is the second in my series of posts in combinatorics. The first post links the Fundamental  Counting Principle, Powers of 2, and the Pascal Triangle. This second post connects the Pascal’s Triangle and the formula for counting the number of permutations with identical objects. The context for connections is a puzzle about counting the total routes of a rook to squares in a chessboard.

The Puzzle

Trace the shortest route the rook can traverse from its corner position to the opposite corner. How many such routes are there?

Solution 1

A useful problem solving strategy here is to simplify the problem: Count the number of distinct paths the rook will land to the nearest square.

To determine the shortest path, the rook should either go north or east or left or right only. That is, the rook has only two choices each time it moves through a square as shown in the figure below. You will not reach the third or fourth line before you figure out that the pattern generates the Pascal’s Triangle.

Thus there are 3432 distinct shortest paths the rook can traverse from one corner to the opposite corner.

Solution 2

Another way to solve puzzle 2 is shown below. The arrows trace some possible shortest paths for the rook.

The paths of the arrows in the figure can be represented this way: (N = North, E = East)

1. N N N E N E E N E N E N E E
2. E E E E N N N E E N N N N E
3. E E E E E E E N N N N N N N

Each shortest path from one corner square to the opposite corner square is made up of 7 N’s and 7 E’s. Thus, counting the total number of shortest paths is the same as counting the total number of distinct arrangements of 7 N’s and 7 E’s in a row. The formula for counting the permutation of n objects a, b, c, … of which are identical will be useful here. This is given by the formula: . So,

.

If you want to practice your skill in solving permutation and combination problems, Examrace Permutation & Combination Made Easy (Examrace Aptitude Series) will be useful.