I. Counting
Counting, also known as combinatorics or enumerative combinatorics, is the first topic we learned on CMSC 57. On this topic we learned about the following:
A. Basics of Counting (Sum and Product Rule)
What it is: The Rule of Sum states if a task can be done in one of w1 ways or in one of w2 ways (mutually exclusive), there are w1 + w2 ways. The Rule of Product states if a procedure has two tasks, with w1 ways for the first and w2 for the second (after the first), there are w1 * w2 ways.
Real-life example:
Rule of Sum: Choosing between 3 bus routes or 2 train routes gives 3 + 2 = 5 ways to get to school.
Rule of Product: A restaurant with 5 main courses and 3 desserts offers 5 * 3 = 15 different two-course meals.
B. Pigeonhole Principle
What it is: If you have more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon.
Real-life example: In a group of 367 people, at least two must share the same birthday (as there are 366 possible birthdays).
C. Permutations and Combinations
What it is: Permutations count arrangements of items where order matters, while combinations count selections where order does not matter.
Real-life example:
Permutation: Arranging 3 books on a shelf (A, B, C) can be done in 6 ways (ABC, ACB, BAC, BCA, CAB, CBA).
Combination: Choosing 2 out of 5 fruits (apple, banana, cherry, date, elderberry) can be done in 10 ways (AB, AC, AD, AE, BC, BD, BE, CD, CE, DE).
D. Binomial Coefficients
What it is: Binomial coefficients count the number of ways to choose k items from n items, denoted as C(n, k) or "n choose k".
Real-life example: Choosing 2 toppings from 5 available pizza toppings can be done in C(5, 2) = 10 ways.
E. Generalized Permutation and Computation
What it is: Generalized permutations extend the concept of permutations to cases where items can repeat or have restrictions.
Real-life example: Arranging 3 letters from the set {A, B, C} with repetition allowed can yield arrangements like AAA, AAB, ABA, etc.
Where can all this be used?
Algorithm Analysis: Determining the number of steps an algorithm takes (its complexity).
Probability: Calculating probabilities often requires counting the number of favorable outcomes and the total number of possible outcomes.
Network Design: Counting paths, connections, or configurations in networks.
Database Design: Estimating the number of possible entries or states.
Cryptography: Counting keys, combinations, or configurations in cryptographic systems.
Game Theory: Analyzing strategies and outcomes in games often involves counting possible moves or configurations.
Problem Solving: Many logical puzzles and problems can be solved using counting techniques.