Tag: combination formula

Posted in Combinatorics, High school mathematics

Linking combination and permutation with repetition

Posted on by

Combinatorial problems are difficult because it’s hard to  know which formula to use in a particular problem and when you need to ‘tweak’ or totally abandon the formula. In this post I share two solutions to a problem which connects the multiplication  principle, the combination formula and the formula for counting the number of permutation with repetition. Knowledge of connections among concepts help in problem solving. The problem is generated from the rook puzzle presented in my post Connecting Pascal’s Triangle and Permutation with identical objects.

Find the number of different ways of arranging 14 letters 7 of which are E’s and 7 are N’s, in a row. Here is one arrangement:

The first solution shows how the formula for counting permutation with identical objects can be deduced from the solution involving the multiplication principle and the second connects permutation and combination.

Solution 1

The idea behind this solution is to initially treat each letter as distinct. There are 14 letters to be arranged in a row. If these letters are distinct from one another then by the Multiplication Principle, there are 14! different arrangements in all.

But the letters are not all distinct. In fact there are only two kinds – N’s and E’s. This means an arrangement, for example, consisting of 7 N’s followed by 7 E’s,

N E N E N E N E N E N E N E 

has been counted 7!7! times in all in 14!. The same is true for this arrangement:

N N N E E N N E E N N E E E.

Thus, to find the number of ways of arranging 14 letters where 7 of which are identical and the remaining 7 are also identical, 14! need to be divided by 7!7!

If the problem had been In how many ways can you arrange 10 N‘s and 4 E‘s?, the solution will be \frac {14!}{10!4!}.

Notice that this solution uses the technique of counting the number of permutations (arrangements) of n objects, r1 of which are identical, r2 are identical, . . . , and rn are identical, where r1 + r2 + . . . ri = n. The number of different permutations is denoted by

In the problem, n = 14, r1 = 7 and r2 = 7. Hence, the total number of arrangements is  \frac{14!}{7!7!} = 3432.

Solution 2

This solution simplifies the original problem to How many different ways can 7 N’s be arranged in a row of 14 spaces? Now, why is this problem equivalent to the original problem? What happened to the 7 E‘s? Why aren’t they not considered anymore? This is because for a particular arrangement of 7 N‘s in 14 spaces, there is one and only one way the 7E‘s can be arranged.

To solve, count the number of possible positions for the 7 N’s. You have 14 positions to choose from for the first N. For the next N you only have 13 positions to choose from, for the next N, 12 and so on until the 7th N. By the Multiplication Principle you have  14.13.12.11.10.9.8.7 different possible positions where you consider each N to be distinct.

But the N’s are identical. That is, in the arrangement for example

_ N _ N N N _ N N _ _ _ _ N

N has been counted 7! times in 14.13.12.11.10.9.8.7. So you have to divide this by 7!

Thus, there are  different positions for N (all N are identical). This can be written in as shorter way using factorial notation by multiplying it by \frac{7!}{7!}.

If there were 10N‘s and 4 E‘s, the problem would have been In how many ways can I arrange 10 N’s in 14 spaces?

In general, if there were n possible positions for arranging r objects, the formula is \frac {n!}{r!(n-r)}. Note that this looks like the combination formula which is used to solve problems for the number of combination and indeed it is. You just got used to applying nCr = \frac {n!}{r!(n-r)} to problems like In how many way can you arrange n different objects taken r objects at a time?

Posted in Combinatorics

Pascal’s triangle and Counting Permutations

Posted on by

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: P = \frac{n!}{a!b!c!...}. So,
P = \frac{14!}{7!7!} = 3432.
Click here to see solutions to this problem using the multiplication principle and combination formula.
If you want to practice your skill in solving permutation and combination problems, Examrace Permutation & Combination Made Easy (Examrace Aptitude Series) will be useful.