The Fundamental Counting Principle

Sometimes you wonder why they bother to teach you the formula for counting combination and permutation when most of the problems can’t be solved by any of them anyway. My advise when studying counting arrangements problem? Understand the multiplication principle, as in really understand it, before you get used to formulas.

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.

Here’s an example of a counting/arrangement problem:

Problem

There are ten chairs in a row.

Question 1 – In how many ways can two people be seated?

Question 2 – In how many of these will the two people be sitting in adjacent chairs?

Question 3 – In how many ways will they have at least one chair between them?

Solution for Question 1

One way to solve this problem is to make a simple one. Suppose there were only 3 chairs. The two persons A and B can be seated in six different arrangements.

So how would you count the number of seating arrangements without listing or making the above diagram? Here’s how you can reason: The first person to sit has three choices where he wants to sit on.  After having chosen the chair, the second person has only two chairs to choose from. By the multiplication principle, the two people can sit in 3 x 2 = 6 different arrangements. Notice that this is the same thing as arranging 3 persons A, B, and C in a row. So in this case you can use the permutation formula P(n,r) = n!/(n-r)!

For ten chairs, the number of distinct arrangement of two people in a row of 10 chairs is P(10,2) = 10!/8! = 90. The first person has 10 chairs to choose from and having chosen it the second person 9 choices left. By the multiplication principle the number of arrangements is 10×9 = 90.

Solution for Question 2

The two arrangements can either be AB or BA. Let’s count the number of ways AB can sit on the 10 chairs. Because they have to sit together, they only have 9 positions to choose from. For BA there are also only 9. All in all there are 18 arrangement. Try this reasoning with the three chairs and you will get 2 + 2. Some would call this the Addition Principle.

Solution for Question 3

From question 1, there are 90 possible ways A and B can sit on the 10 chairs. From question 2, there are 18 possible ways they can sit together. So the number of ways they can be seated that is at least one chair apart is 90-18=72 ways.

If you want to practice and know more strategies for counting combinations and arrangements I recommend A Path to Combinatorics for Undergraduates: Counting Strategies.