Fundamental Counting Principle
The Fundamental Counting Principle (FCP) states that
If task 1 can be accomplished in n1 ways,and for each of these ways, task 2 can be accomplished in n2 ways, . . . and for each of these ways, task r can be accomplished in nr ways,then all tasks can be accomplished in(n1)(n2) . . . (nr) ways.The FCP is also known by other names, such as the Multiplication Principle and the Counting Principle.
One common application of the FCP is in counting the number of strings that can be formed from a given set of characters. A string of characters is just a list of those characters, often written with a space between them but sometimes written like a word. The length of a string is the number of chacters in it. For example, the possible length-2 strings from the sequence of letters a, b, c are
a a
a b
a c
b a
b b
b c
c a
c b
c c
The FCP allows counting the strings without listing them. You consider that you're filling two slots. You can fill the first in 3 ways (with a, b, or c). For each way that the first slot is filled, there are 3 ways of filling the second. So, by the FCP, there are 3 x 3 = 9 ways of filling the two slots. That is, there are 9 strings of length 2.
The FCP can also be used to count strings in the special case in which repetition is limited, called permutations.
Copyright © 1999-2000 SciMathMN