Combinatorics Examples

Math for CS · Axiom Academy

Combinatorics: Worked Examples Step-by-step counting problems for CS Problem: A system requires passwords that are exactly 8 characters long. The first character must be an uppercase letter (26 choices), the last must be a digit (10 choices), and the remaining 6 characters can be any of 62 alphanumeric characters (26 upper + 26 lower + 10 digits). How many valid passwords exist? We use the multiplication principle . Each character position is an independent choice: That is about 14.8 trillion valid passwords. Example 2: Forming a Committee Problem: A team of 12 developers must form a 4-person code review committee. How many distinct committees are possible? What if one specific senior engineer must be included? Order does not matter (a committee is a set), so we use combinations: If the senior engineer is fixed on the committee, we choose the remaining 3 from the other 11: Example 3: Arranging Processes on Cores Problem: A scheduler must assign 5 distinct processes to 5 distinct CPU cores, one process per core. How many possible assignments exist? What if 2 of the processes are identical (e.g., two instances of the same service)? This is a permutation of 5 objects: When 2 processes are identical, swapping them produces the same assignment. We divide out the overcounting: Example 4: Distributing Tasks (Stars and Bars)

This is the written version of the interactive lesson above. See the full Math for CS course.