Counting Principles - Core Definitions
Counting is the foundation of discrete mathematics and combinatorics. The fundamental principles of counting provide systematic methods for determining the number of ways events can occur, which is essential for probability theory, algorithm analysis, and numerous applications across mathematics and computer science.
If a task can be performed in ways or in ways, where none of the ways is the same as any of the ways (mutually exclusive), then the task can be performed in ways. More generally, if there are mutually exclusive ways to perform a task with possibilities respectively, then the total number of ways is
The addition principle applies when we have a choice between different categories of outcomes. For instance, if a committee can be formed by selecting one person from department A (with 5 members) or department B (with 7 members), there are ways to form the committee.
If a procedure consists of two consecutive tasks, where the first task can be performed in ways and for each of these ways the second task can be performed in ways, then the entire procedure can be performed in ways. More generally, if a procedure consists of tasks performed sequentially with ways respectively, then the total number of ways is
Suppose license plates consist of 3 letters followed by 4 digits. How many distinct license plates are possible?
For each letter position, there are 26 choices (A through Z). For each digit position, there are 10 choices (0 through 9). By the multiplication principle:
Therefore, there are 175,760,000 possible license plates.
A permutation of distinct objects taken at a time is an ordered arrangement of objects from the set of objects. The number of such permutations is denoted or and is given by
When , we have , the number of ways to arrange all objects.
A combination of distinct objects taken at a time is a selection of objects from the set of objects where order does not matter. The number of such combinations is denoted , , or (binomial coefficient) and is given by
The relationship between permutations and combinations is fundamental: . This makes sense because each combination of objects can be arranged in different orders, giving us all permutations. Understanding when to use permutations (order matters) versus combinations (order doesn't matter) is crucial for solving counting problems correctly.
These core definitions provide the building blocks for more advanced counting techniques and are essential tools throughout discrete mathematics.