Fundamentals Principle of Counting
In this article, We begin with the following basic principle.
Fundamental Principle of Counting: If some procedure can be performed in n1 different ways, and if, following this procedure, a second procedure can be performed in n2 different ways, and if, following this second procedure, a third procedure can be performed in n3 different ways, and so forth; then the number of ways the procedures can be performed in the order indicated is the product n~ n2 n3 . . . .
Example: Suppose a license plate contains two distinct letters followed by three digits with the first digit, not zero.
How many different license plates can be printed?
The first letter can be printed in 26 different ways, the second letter in 25 different ways (since the letter printed first cannot be chosen for the second letter), the first digit in 9 ways, and each of the other two digits in 10 ways.
Hence 26 25 9 10 10 = 585,000 different plates can be printed.
The product of the positive integers from 1to n. inclusive occurs very often in mathematics and hence is denoted by the special symbol n! (read “n factorial”): ~2!= 102.3.- – *(n-2)(n-l)n It is also convenient to define O! = 1.
Example: 2! = 1.2 = 2, 3! = 1.203 = 6, 4! = 18.104.22.168 = 24, 5! = 5*4! = 5.24 = 120, 6! = 6*5! = 6.120 = 720
Example: 8! – 8~7*6!- 6!/ 6! — — 8.7 = 56. 12*11*10 = 12-11*10*9!/9! = 12! /9!
An arrangement of a set of n objects in a given order is called a permutation of the objects (taken all at a time). An arrangement of any r Ln of these objects in a given order is called an r-permutation or a permutation of the n objects taken r at a time.
Example: Consider the set of letters a, b, c, and d. Then:
(i) bdca, dcba, and acdb are permutations of the 4 letters (taken all at a time);
(ii) bad, adb, cbd, and bca are permutations of the 4 letters taken 3 at a time;
(iii) ad, cb, da, and bd are permutations of the 4 letters taken 2 at a time.
(iv) The number of permutations of n objects taken r at a time will be denoted by P(n,r)
Before we derive the general formula for P(n,r) we consider a special case.
Permutations with Repetitions
Frequently we want to know the number of permutations of objects some of which are alike, as illustrated below. The general formula follows.
Theorem: The number of permutations of n objects of which nl are alike, n2 are alike, . . .,n+ are alike is n!/n1! n2!… nr!