ConceptComplete

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.

DefinitionThe Addition Principle

If a task can be performed in n1n_1 ways or in n2n_2 ways, where none of the n1n_1 ways is the same as any of the n2n_2 ways (mutually exclusive), then the task can be performed in n1+n2n_1 + n_2 ways. More generally, if there are kk mutually exclusive ways to perform a task with n1,n2,,nkn_1, n_2, \ldots, n_k possibilities respectively, then the total number of ways is n1+n2++nkn_1 + n_2 + \cdots + n_k

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 5+7=125 + 7 = 12 ways to form the committee.

DefinitionThe Multiplication Principle

If a procedure consists of two consecutive tasks, where the first task can be performed in n1n_1 ways and for each of these ways the second task can be performed in n2n_2 ways, then the entire procedure can be performed in n1×n2n_1 \times n_2 ways. More generally, if a procedure consists of kk tasks performed sequentially with n1,n2,,nkn_1, n_2, \ldots, n_k ways respectively, then the total number of ways is n1×n2××nkn_1 \times n_2 \times \cdots \times n_k

ExampleCounting License Plates

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: 26×26×26×10×10×10×10=263×104=175,760,00026 \times 26 \times 26 \times 10 \times 10 \times 10 \times 10 = 26^3 \times 10^4 = 175,760,000

Therefore, there are 175,760,000 possible license plates.

DefinitionPermutations

A permutation of nn distinct objects taken rr at a time is an ordered arrangement of rr objects from the set of nn objects. The number of such permutations is denoted P(n,r)P(n,r) or nPr_nP_r and is given by P(n,r)=n!(nr)!=n(n1)(n2)(nr+1)P(n,r) = \frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1)

When r=nr = n, we have P(n,n)=n!P(n,n) = n!, the number of ways to arrange all nn objects.

DefinitionCombinations

A combination of nn distinct objects taken rr at a time is a selection of rr objects from the set of nn objects where order does not matter. The number of such combinations is denoted C(n,r)C(n,r), nCr_nC_r, or (nr)\binom{n}{r} (binomial coefficient) and is given by (nr)=n!r!(nr)!\binom{n}{r} = \frac{n!}{r!(n-r)!}

Remark

The relationship between permutations and combinations is fundamental: P(n,r)=r!C(n,r)P(n,r) = r! \cdot C(n,r). This makes sense because each combination of rr objects can be arranged in r!r! 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.