Basic Counting Principles in Discrete Mathematics: Sum Rule and Product Rule

Learn fundamental counting principles—the sum rule and the product rule—used to determine the number of possibilities in various scenarios. This guide explains when to apply each rule with clear examples to master basic counting techniques.

Basic Counting Principles in Discrete Mathematics

Sum Rule

The sum rule helps us count the number of ways to do one thing or another when the events are mutually exclusive (they can't happen at the same time). If event E has m possibilities and event F has n possibilities, and E and F cannot occur together, then the total number of ways either E or F can happen is m + n.

Example: Sum Rule

If there are 8 male professors and 5 female professors teaching Discrete Mathematics, a student has 8 + 5 = 13 choices for selecting a professor.

Product Rule

The product rule helps us count the number of ways to do one thing and another when the events are independent (the outcome of one doesn't affect the outcome of the other). If event E has m possibilities and event F has n possibilities, then the total number of ways both E and F can happen is m x n.

Example: Product Rule

In a class with 4 boys and 10 girls, if we need to select one boy and one girl for a role, there are 4 x 10 = 40 possible selections.

Mathematical Functions Used in Counting

Factorial Function

The factorial of a non-negative integer n (written n!) is the product of all positive integers from 1 to n. Formally:

n! = n × (n - 1) × (n - 2) × ... × 2 × 1

We define 0! = 1 and 1! = 1.

Example: Factorial

5! = 5 × 4 × 3 × 2 × 1 = 120

Binomial Coefficients

A binomial coefficient, written C(n, r) or sometimes as nCr or ⁿCr, represents the number of ways to choose r items from a set of n items (where r ≤ n). The formula is:

C(n, r) = n! / (r! × (n - r)!)

Example: Binomial Coefficient

C(8, 2) = 8! / (2! × 6!) = 28

Conclusion

The sum and product rules, along with factorial and binomial coefficient calculations, are fundamental tools for solving many counting problems in discrete mathematics.