**Fundamental Counting Principle
**

The *Fundamental Counting Principle* (FCP) states that

If task 1 can be accomplished inThe FCP is also known by other names, such as then_{1}ways,and for each of these ways, task 2 can be accomplished inn_{2}ways, . . . and for each of these ways, taskrcan be accomplished innways,then all tasks can be accomplished in(_{r}n_{1})(n_{2}) . . . (n) ways._{r}

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