Counting is one of the most basic yet powerful activities in mathematics. When the number of possible arrangements or selections is huge, direct enumeration is impossible, and we need systematic methods. This chapter develops the fundamental principles of counting, the factorial notation, and the two central tools of combinatorics: permutations (arrangements) and combinations (selections).
The chapter begins with the fundamental principle of counting in its addition and multiplication forms. It then introduces factorial notation and develops formulas for the number of permutations of distinct objects, permutations with repetition, and permutations when some objects are alike. It defines combinations, establishes the relationship between permutations and combinations, and presents the standard properties of combination numbers.
Permutations and combinations are the backbone of probability theory, which is studied later in this very class. They also appear in geometry, algebra, and computer science, for instance in counting paths, forming committees, and analysing algorithms. A clear understanding of when to multiply and when to add, and when order matters, is the essence of this chapter.
If one event can occur in m ways and a second independent event can occur in n ways after the first, then the two events together can occur in m x n ways.
Example: If a person has 3 shirts and 2 trousers, the number of ways of choosing one shirt and one trouser is 3 x 2 = 6.
If one event can occur in m ways and another event can occur in n ways, and the two events cannot occur simultaneously, then one of them can occur in m + n ways.
Example: If a library has 4 books on mathematics and 5 books on physics, the number of ways of choosing one book of either subject is 4 + 5 = 9.
The product of the first n natural numbers is denoted by n! and read as "n factorial":
n! = 1 x 2 x 3 x ... x (n - 1) x n
By convention, 0! = 1. Also note that n! = n x (n - 1)!.
Some values: 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5040.
The number of permutations (arrangements) of n distinct objects taken r at a time is:
nPr = n!/(n - r)! = n(n - 1)(n - 2)...(n - r + 1)
In particular, the number of permutations of n distinct objects taken all at a time is nPn = n!.
Example: The number of ways of arranging 3 letters A, B, C taking all 3 is 3! = 6.
If a set of n objects contains n1 objects of one kind, n2 objects of another kind, and so on, where n1 + n2 + ... + nk = n, then the number of distinct permutations is:
n!/(n1! n2! ... nk!)
Example: The number of distinct permutations of the letters of the word "APPLE" is 5!/2! = 60, because the letter P occurs twice.
If repetition of objects is allowed, then the number of permutations of n distinct objects taken r at a time is n^r, because each of the r positions can be filled in n ways.
Example: The number of 3-digit numbers that can be formed using the digits 1, 2, 3, 4 with repetition allowed is 4^3 = 64.
A combination is a selection of objects in which order does not matter. The number of combinations of n distinct objects taken r at a time is:
nCr = n!/(r!(n - r)!)
nPr = nCr x r!
Each selection of r objects can be arranged among themselves in r! ways, giving r! times as many permutations as combinations.
Example: The number of ways of choosing a committee of 2 from 5 people is 5C2 = 5!/(2!3!) = 10.
These properties make the calculation of combination values much easier.
When selections involve identical objects, the counting is different. The number of ways of selecting r objects from n distinct objects is nCr. If identical objects are present, problems are typically approached by direct case analysis or by considering the number of objects taken from each type.
For example, to find the number of ways of selecting any number of objects (from 0 to n) from n distinct objects, the answer is 2^n, since each object can either be chosen or not.
Word problems on permutations and combinations require careful reading:
Example: The number of ways in which 5 boys can be seated in a row is 5! = 120. The number of ways in which 5 boys can be seated around a circular table is (5 - 1)! = 4! = 24, since rotations are considered identical in a circle.
| Situation | Formula | Example |
|---|---|---|
| Permutations of n objects taken r | nPr = n!/(n-r)! | 5P3 = 60 |
| Permutations of n objects all at once | nPn = n! | 5! = 120 |
| Permutations with repetition | n^r | 4^3 = 64 |
| Permutations with alike objects | n!/(n1!n2!...nk!) | APPLE: 5!/2! = 60 |
| Combinations | nCr = n!/(r!(n-r)!) | 5C2 = 10 |
| Property | Statement |
|---|---|
| Symmetry | nCr = nC(n-r) |
| Boundary values | nC0 = 1, nCn = 1 |
| Single selection | nC1 = n, nC(n-1) = n |
| Pascal's identity | nCr + nC(r-1) = (n+1)Cr |
| Total subsets | nC0 + nC1 + ... + nCn = 2^n |
Permutations and combinations provide a systematic way to count arrangements and selections without listing them. The fundamental principles of counting give the logical basis, the factorial notation supplies the computational engine, and the formulas for nPr and nCr, together with the properties of combination numbers, make the counting process efficient. The distinction between order-sensitive arrangements and order-insensitive selections is the key conceptual hurdle, and once it is mastered, word problems become straightforward. These tools are essential for probability, and they find application across mathematics, computer science, and every field that deals with counting and selection.