CampusLearn
← CSC 113 Discrete Mathematics

Combinatorics and Counting Principles

Notes

PRINCIPLES OF COUNTING Combinatorics is the branch of discrete mathematics focused on counting, arrangement, and operational complexity. It is critical for determining algorithm time complexity, network addressing capacity, and data encryption strength. The two elementary foundations of counting are the Product Rule and the Sum Rule. The Product Rule states that if a procedure can be broken into two successive tasks, where task one can be performed in m ways and task two in n ways, the overall procedure can be performed in m multiplied by n ways. The Sum Rule states that if an action can be performed in m ways and a second mutually exclusive action in n ways, then doing either task can occur in m plus n ways. PERMUTATIONS, COMBINATIONS, AND THE PIGEONHOLE PRINCIPLE When selecting items from a finite set: Permutations consider order significant, calculating arrangements of r items chosen from n elements. Combinations disregard order, counting subsets where element sequence does not distinguish outcomes. The Pigeonhole Principle asserts that if k items are placed into n containers where k exceeds n, at least one container must inevitably hold two or more items. In hashing algorithms, this guarantees that hash collisions are mathematically unavoidable when keys exceed bucket slots. PRACTICAL EXAMPLE Consider the National Transport and Safety Authority (NTSA) generating civilian motor vehicle registration numbers in Kenya under a defined format. A standard registration series uses the format K followed by two uppercase English letters, three digits, and one trailing uppercase letter (for example, KDA 123A). NTSA rules specify that: The first letter is always fixed as K. The letters I and O are excluded from the second, third, and trailing positions to avoid confusion with digits one and zero, leaving 24 allowable letters. The numeric section consists of three digits running strictly from 001 to 999, which provides exactly 999 unique digit combinations per series letter block. To compute the total license plate capacity for a specific series block, such as the KD series (where the first two letters are fixed as KD): The third letter has 24 possibilities. The three-digit integer has 999 possibilities. The trailing fourth letter has 24 possibilities. Applying the product rule: Total plates in KD series = 24 * 999 * 24 Total plates = 575,424 vehicles. This calculation allows NTSA systems engineers to project exhaustion rates of vehicle plates.

Quiz

1. How many distinct 4-digit PIN numbers can be created for an ATM system if digits 0 through 9 can be repeated without restriction?

2. What is the key structural difference between a permutation and a combination?

3. According to the Pigeonhole Principle, what is the minimum number of students required in a lecture hall to guarantee that at least two share the exact same birthday month?

Sign in to submit and securely grade your quiz.