Combinatorics Formula Sheet

Math for CS · Axiom Academy

All counting formulas in one place Fundamental Counting Principles If task A can be done in m ways and task B in n ways, then A followed by B can be done in ways. If task A can be done in m ways or task B in n ways (mutually exclusive), the total is m + n ways. Permutations of n distinct objects: k -permutations from n objects: Circular permutations of n objects: Choose k from n (order doesn't matter): (sum of row in Pascal's triangle) Arrangements of n objects with identical groups: n identical objects into k distinct bins (zeros allowed): n identical objects into k distinct bins (each bin ): Number of permutations of n elements with no fixed points: First few values: D_1 = 0 , D_2 = 1 , D_3 = 2 , D_4 = 9 , D_5 = 44 CS Application: Random shuffles where nothing stays in its original position (e.g., secret Santa assignments). Axiom Academy | Discrete Math for Computer Science

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