Unit 5 Summary

Math for CS · Axiom Academy

Complete review of counting techniques Combinatorics answers the question: how many? Every counting problem reduces to identifying the right model, then applying the corresponding formula. The four key questions to ask are: Does order matter? (permutation vs. combination) Is repetition allowed? (with replacement vs. without) Are the objects identical or distinct? Are we distributing objects into bins? (stars and bars) If a procedure has stages with independent choices, the total count is . CS example: IP addresses have 4 octets, each 0-255: billion addresses. 2. Permutations and Combinations Permutations count ordered selections: P(n,k) = n!/(n-k)! Combinations count unordered selections: CS example: Choosing 3 of 8 servers for a task force (combination) vs. ranking their priority (permutation). Arranging n objects where groups of size are identical: CS example: Scheduling 3 high-priority, 5 medium-priority, and 2 low-priority tasks in a queue. Distributing n identical items into k distinct bins: . CS example: Distributing 20 identical workload units across 5 containers. For overlapping sets: add individual sizes, subtract pairwise intersections, add triple intersections, and so on. CS example: Counting strings that contain at least one of several forbidden patterns. Count what you don't want and subtract: . Works beautifully with "at least one" problems. Permutations where nothing stays in its original position:

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