multiplication principle Archives - Mathematics for Teaching

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, r₁ of which are identical, r₂ are identical, . . . , and r_n are identical, where r₁ + r₂ + . . . r_i = n. The number of different permutations is denoted by

In the problem, n = 14, r₁ = 7 and r₂ = 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 7^th 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?

Combinatorics

What makes counting problems difficult

Posted on by

I don’t have the numbers but I think not many will disagree with me that among those who like mathematics and find joy in the challenge of solving math problems, only very few will also like to solve combinatorial or counting problems. And if I may be allowed to push my observation a bit further, those who are more inclined to algebra are the ones who have more aversion to problems that asks them to count.

Indeed, combinatorial problems are odd. Unlike other mathematics problems, these type of problems cannot easily be categorized and solved with predictable algorithms. Each problem always seems to be a case in itself. Knowing all the formulas for different cases of permutations and combinations is not a guarantee that one will be able to solve these problems. For many, these are only useful if the problem already explicitly asks for number of permutations and combinations. And when indeed the problem says so, one still has to decipher other conditions and the assumptions embedded in the context. Knowing when to add or multiply is also difficult, if not the most difficult part. Knowing when one already double counted also requires depth of understanding not only of the formulas but also of the context of the problem. Of course for some these are also the very reason why they love to solve counting problems.

Take the case of this family of problems:

How many three-digit numbers can you form from the digits, 5, 6, 7, 8, and 9? (This requires direct application of the permutation formula or better, the multiplication principle.)
How many three-digit numbers are there in all? (That you will choose from 0 to 9 is implied only plus you ask yourself how about 027? Is it a 3-digit number of a 2-digit number?)
How many numbers can be formed from 5, 6, 7, 8, and 9?
How many three-digit numbers greater that 600 can be formed from the digits 5, 6, 7, 8, and 9? (Oops … so what formula is applicable now?)
How many numbers greater than 3,000,000 can be formed by arrangements of the digits 1, 2, 2, 3, 6, 6, 6? (More Ooops…)

Having identified some of the difficulties inherent to counting problems, what teaching tip can I propose?

Ask for different ways of solving the problem, slowly discouraging students’ reliance to listing. Thinking in terms of tree diagrams and empty boxes are great help.
Defer introduction of formulas before students can solve the problems like the ones above using the fundamental counting principle. Permutations and combination formulas are only powerful to the extent to which students understand the multiplication principle.
Another pedagogical tip is to ask students to identify what makes a problem similar and different in structure from the problems they previously solved. If they can specify which problem, the better.
As a consequence of tip#3, problems are best given per family with family defined in terms context (e.g., the family of problems given in the example above) and not in terms of similarity in solution structure.

Please add yours. Thanks.

You may want to read my two other posts on combinatorics:

Some useful references:

Combinatorics

The Counting Principle, Pascal’s Triangle, and Powers of 2

Posted on by

This post shows how we can help students make connections among counting principle, the Pascal’s triangle, and powers of 2. I have tried this lesson in an in-service training program but I’ve yet to test it with students in high school. The lesson uses the strategy Teaching thru Problem Solving.

A piece of knowledge is powerful to the extent to which it is connected to other piece of knowledge. The more connections there are, the more powerful it becomes. Mathematics teaching therefore should always aim to help students make connections among the different concepts of mathematics. You may want to read my article about understanding as making connections.

The Problem: Trace the paths that will spell “MATHEMATICS” starting from the letter M on top moving only downwards, either to the immediate letter to its right or to the immediate letter to its left. How many different paths are there in all?

After a few minutes and the class is seem getting nowhere you may suggest to students to try simpler case first like trying the word MATH. Trying simpler case is a good problem solving strategy and habit students need to learn.

Solution 1

Suppose we spell the word “MATH” only. From M we can move downwards and may either choose the A at the left or the A at the right. Having chosen an A we can either choose the T down left or the T down right. And having chosen one we can either choose the H down right or the H down left. Each time we only have two choices. Thus, the number of ways of tracing the word “MATH” in the above figure is

2·2·2 =2³=8

Using the same line of thinking, the total number of paths which spells “MATHEMATICS” is

2·2·2·2·2·2·2·2·2·2=2¹⁰=1024.

Solution 2

Notice the number of arrows that converges to a particular letter. It tells the number of paths that pass through it. Thus, to count the number of ways of tracing the word “MATH” we only have to add the total number of arrows that point to the H’s. There are

1 + 3 + 3 + 1 = 8.

Count the number of arrows converging to each letter in MATHEMATICS . You will generate the triangular array of numbers below.

The number of arrows converging to S is

1 + 10 + 45 + 120 + 210 + 252 + 210 + 120 + 45 + 10 + 1 = 1024 or 2¹⁰.

The solutions showed two important principles of counting.

The Multiplication Principle. If one task can be done in m ways and then another task can be done in n ways, the pair of tasks, first one and then the other, can be performed in

m • n ways.

The Addition Principle. If one task can be done in m ways and another task in n ways, then one task or the other can be done in

m + n ways.

Anyone who wants to understand permutations, combinations and anything that involves counting should first understand these principles.

The triangular array of numbers generated above is one of the most influential number patterns in the history of mathematics. It is called Pascal’s triangle after the renowned French mathematician Blaise Pascal (1623-1662) who discovered it. The triangle is also called Yang Hui’s triangle in China as the Chinese mathematician Yang Hui discovered it much earlier in 1261. The same triangle was also in the book “Precious Mirror of the Four Elements” by another Chinese mathematician Chu-Shih-Chieh in 1303.

The Pascal triangle yields interesting patterns and relationships. Some of the obvious ones are:

To generate the next row, you will have to add the two numbers above it.
Another striking property of this array of numbers is its symmetry. Note the numbers on both sides of the middle number in each row.
The sum of the numbers in each row can be expressed in powers of two.

Share!

Share!

Solution 1

Solution 2

Share!