Subject GRE-Style: Counting Problem

GRE Math Subject · Axiom Academy

EXAMPLE Subject GRE-Style: Counting Problem 3 worked problems on combinatorics, counting functions, and inclusion-exclusion Key Tools: Multiplication principle, , and the Inclusion-Exclusion Principle: . Question: How many surjective (onto) functions are there from a 4-element set to a 3-element set? (A) 24 (B) 36 (C) 48 (D) 64 (E) 81 Inclusion-Exclusion for Surjections Total functions from a 4-set to a 3-set: . Subtract those that miss at least one element of the codomain. Let = functions missing element . Quick check: Alternatively, exactly one element of must share a target with another. Choose which 2 of 4 share a target: . Choose which of 3 targets they share: 3. Assign the other 2 elements to the remaining 2 targets: . Total: . Permutations with Restrictions Question: How many permutations of have no element in its natural position (i.e., how many derangements of 5 elements)? (A) 24 (B) 44 (C) 53 (D) 60 (E) 120 Derangements via Inclusion-Exclusion Let = permutations fixing element . We want . GRE Shortcut: The derangement formula gives . For quick approximation, . Here , and rounding to the nearest integer gives 44. Memorize . Question: How many ways can 10 identical balls be placed into 4 distinct boxes? (A) 40 (B) 120 (C) 210 (D) 286 (E) 10000 This is a classic stars and bars problem: distributing identical objects into distinct bins (empty bins allowed).

This is the written version of the interactive lesson above. See the full GRE Math Subject course.