Trace it. Derive it. Know it.
Every cluster below maps one schematic path — from first principles to the final equation. Expand a node to follow the full derivation trace.
Fundamental Principles of Counting: Multiplication & Addition Rules
3 concepts · 6.1When must branching possibilities be multiplied versus added, and how do decision trees and slot-filling systematically resolve complex multi-stage constraints?
Combinatorial enumeration begins with two fundamental counting axioms: (1) The Fundamental Principle of Multiplication (FPM / Product Rule): If a compound operation consists of two sequential stages such that Stage 1 can be performed in m distinct ways, and following this, Stage 2 can be performed in n distinct ways, then the combined two-stage operation can be executed in m × n distinct ways. By induction, for k sequential stages with n_1, n_2, ..., n_k independent choices, the total count is n_1 × n_2 × ... × n_k. FPM translates directly into filling 'slots' from left to right or by prioritizing the most constrained slots first (e.g., parity, non-zero leading digits, divisibility). (2) The Fundamental Principle of Addition (FPA / Sum Rule): If a task can be performed by choosing either Method 1 (which has m distinct ways) OR Method 2 (which has n distinct ways), and the two methods are mutually exclusive (disjoint, cannot occur simultaneously), then the total ways to execute the task is m + n. Geometrically, FPM is depicted by expanding branches in a Decision Tree where each leaf represents a unique sequential history, while FPA represents disjoint clusters of trees. Master the 'Priority of Constraints' rule: always satisfy the slot with the tightest restriction first (such as the units digit for even numbers or the highest place value for non-zero leading digits).
Multiplication Principle (FPM) & Sequential Multi-Stage Slot Filling
Addition Principle (FPA) & Mutually Exclusive Case Breakdown
Digit Formation with Constraints (Leading Zero & Divisibility)
Factorial Notation, Permutations of Distinct Objects & Slot / Gap / String Methods
3 concepts · 6.2What is the mathematical definition of P(n, r), and how do the String (Tie) Method and Gap Method enforce clustering and non-consecutive constraints?
Factorial notation n! (for n in N U {0}) denotes the product of the first n natural numbers: n! = n × (n-1) × ... × 2 × 1, with 0! = 1 by convention (or gamma function Gamma(1) = 1). A Permutation is an ordered arrangement of a specified number of objects selected from a given set. The number of permutations of n distinct objects taken r at a time (0 <= r <= n) without repetition is denoted by P(n, r) or ^n P_r = n! / (n-r)! = n(n-1)(n-2)...(n-r+1). When all n objects are arranged, P(n, n) = n!. When repetition of objects is allowed, each of the r positions can be filled in n ways, giving n^r permutations. In competitive problems, positional constraints require elite structural heuristics: (1) The String (Tie / Block) Method: When specific items MUST ALWAYS BE TOGETHER, tie them together into a single composite super-object. If k items among n must stay together, treat the cluster as 1 object. Arrange the (n - k + 1) objects in (n - k + 1)! ways, and multiply by k! for the internal permutations of the tied cluster: Total = (n - k + 1)! × k!. (2) The Gap Method: When specific items MUST NEVER BE TOGETHER (no two adjacent), arrange the unconstrained items first to create 'gaps' (including the two outer ends). If m unconstrained items are arranged in m! ways, they create (m + 1) distinct gaps. If k constrained items are to be placed such that no two are adjacent, they must be slotted into these (m + 1) gaps in P(m+1, k) ways, requiring k <= m + 1. Total = m! × P(m+1, k). (3) The Complementary Method: Total arrangements minus the unwanted arrangements (useful when 'at least two' are together).
Factorial Algebra & Fundamental Identity P(n, r) = n! / (n-r)!
The String (Tie / Block) Method for Mandatory Adjacency
The Gap Method for Complete Non-Adjacency (No Two Together)
Permutations of Multi-Sets (Identical Objects), Dictionary Rank & Circular Permutations
3 concepts · 6.3How does repetition of identical objects reduce permutation counts via multinomial dividing, how is dictionary rank computed, and why are circular arrangements reduced to (n-1)!?
When the objects to be arranged are not all distinct, identical objects cannot be distinguished when permuted among themselves. The Permutation of a Multi-Set Theorem states: The number of permutations of n objects, of which p are identical of type 1, q are identical of type 2, r are identical of type 3, and the rest distinct (where p + q + r <= n), is given by: n! / (p! × q! × r!). In word problems, this formula resolves anagram counts for words like 'MATHEMATICS' (11! / (2! 2! 2!)) and 'MISSISSIPPI' (11! / (4! 4! 2!)). The Dictionary Rank Algorithm determines the lexicographical position of a given word when all permutations of its letters are arranged alphabetically: list letters in alphabetical order, systematically count words starting with letters strictly preceding the target letter at each position, and sum them plus 1. Circular Permutations: When n distinct objects are arranged along a closed circle, there is no designated 'start' or 'end'. A rotational shift of all elements produces an identical configuration. Fixing 1 object to break rotational symmetry leaves (n - 1) positions to be filled linearly, giving (n - 1)! circular permutations. If clockwise and anticlockwise orientations are indistinguishable (e.g. flipping a necklace or garland of beads over in 3D space), the number of circular permutations is halved: (n - 1)! / 2.
Permutations of Multi-Sets with Repeated Elements
The Dictionary Rank Algorithm (Distinct & Repeated Letters)
Circular Permutations: Round Table vs Reversible Necklaces
Combinations: Selection Logic, Pascal's Identity & Core Combinatorial Theorems
3 concepts · 6.4What fundamental principles differentiate combinations from permutations, and what algebraic identities govern C(n, r)?
A Combination is a selection of objects where order or sequence is irrelevant. The number of combinations of n distinct objects taken r at a time (0 <= r <= n) is denoted by C(n, r), ^n C_r, or binom(n, r), and is defined by: C(n, r) = n! / (r! × (n - r)!). Because every unordered group of r objects can be arranged internally in r! ways, Permutations and Combinations are inextricably linked by the Fundamental Relation: P(n, r) = C(n, r) × r! <=> C(n, r) = P(n, r) / r!. Core Combinatorial Theorems: (1) Complementary Combination Identity: C(n, r) = C(n, n - r). Selecting r objects to include is equivalent to selecting (n - r) objects to exclude. Consequently, if C(n, x) = C(n, y), then either x = y or x + y = n. (2) Pascal's Identity: C(n, r) + C(n, r - 1) = C(n + 1, r). Combinatorial proof: Consider a specific object x in a set of (n + 1) items; any subset of size r either contains x (requiring r - 1 more from the remaining n items: C(n, r - 1)) or excludes x (requiring all r from the remaining n items: C(n, r)). (3) Ratio Identities: C(n, r) / C(n, r - 1) = (n - r + 1) / r, and C(n, r) / C(n - 1, r - 1) = n / r. (4) Total Number of Subsets: The total number of ways to select any number of objects (0, 1, 2, ..., n) from n distinct objects is sum_{r=0}^n C(n, r) = 2^n. If at least one object must be chosen, ways = 2^n - 1. (5) Selection from Identical Objects: The number of ways to select any number of objects from p identical objects is (p + 1) (choose 0, 1, ..., or p).
Definition of C(n, r) & The Fundamental Link P(n, r) = r! × C(n, r)
Symmetry & Pascal's Addition Identity C(n, r) + C(n, r-1) = C(n+1, r)
Total Selections from Distinct and Identical Collections
Geometric Combinatorics, Division into Groups & Sub-Factorial Derangements
3 concepts · 6.5How are combinations applied to geometry, how do group division symmetries resolve identical group counts, and what formula governs complete derangements?
This concept covers three high-yield advanced combinatorial strategies: (1) Geometric Combinatorics: (A) Straight Lines: From n points in a plane where no 3 are collinear, the number of straight lines formed is C(n, 2). If m points are collinear, lines = C(n, 2) - C(m, 2) + 1 (the +1 preserves the single line containing the m collinear points). (B) Triangles: Triangles formed = C(n, 3) - C(m, 3). (C) Diagonals of an n-sided Polygon: An n-gon has n vertices and C(n, 2) total connecting line segments. Since n of these segments form the perimeter edges, the number of internal diagonals is C(n, 2) - n = n(n - 1)/2 - n = n(n - 3)/2. (D) Points of Intersection: Maximum intersections of C(n, 2) lines (no two parallel, no three concurrent) is C(n, 2). (2) Division and Distribution into Groups: (A) Unequal Groups: The number of ways to divide (m + n + p) distinct objects into 3 unequal groups of size m, n, p is: (m + n + p)! / (m! n! p!). (B) Equal Groups: If groups are of EQUAL size, say dividing 2n distinct objects into 2 groups of size n each, the order of groups is irrelevant, so we must divide by 2! to avoid overcounting: (2n)! / ((n!)^2 × 2!). In general, dividing (mn) objects into m groups of size n each = (mn)! / ((n!)^m × m!). If these groups are subsequently distributed to m distinct persons, multiply back by m!, giving (mn)! / (n!)^m. (3) Derangements (Sub-Factorial !n): A derangement is a permutation of n distinct objects such that NO object appears in its original natural position. The number of derangements of n objects is given by de Montmort's formula: D_n = !n = n! [1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!]. Key base values: D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44, D_6 = 265. Recurrence relation: D_n = (n - 1)(D_{n-1} + D_{n-2}).
Geometric Combinations: Lines, Triangles, Collinearity & Polygon Diagonals
Group Division & Distribution (Equal vs Unequal Clusters)
Derangements (Sub-Factorials !n & de Montmort's Recurrence)
Multinomial Theorem, Beggar's Method (Stars & Bars) & Legendre's Formula
3 concepts · 6.6How does Beggar's Method distribute identical items into distinct containers, and how does Legendre's formula compute the prime exponent in n!?
This concept covers three pinnacle algebraic combinatorics tools: (1) Beggar's Method (Stars and Bars / Bose-Einstein Distribution): Used to find the number of integer solutions to the equation x_1 + x_2 + ... + x_r = n, which corresponds to distributing n identical items (stars) among r distinct recipients (beggars). (A) Non-Negative Integer Solutions (x_i >= 0): Placing n identical stars and (r - 1) identical dividers (bars) in a line yields total positions = n + r - 1. Choosing positions for the dividers gives: C(n + r - 1, r - 1) = C(n + r - 1, n). (B) Positive Integer Solutions (x_i >= 1): First give 1 item to each of the r recipients to satisfy the strictly positive constraint, leaving (n - r) items to be distributed freely: C((n - r) + r - 1, r - 1) = C(n - 1, r - 1). (2) Multinomial Expansion: The coefficient of x_1^{k_1} x_2^{k_2} ... x_r^{k_r} in the expansion of (x_1 + x_2 + ... + x_r)^n (where k_1 + k_2 + ... + k_r = n) is the multinomial coefficient: n! / (k_1! k_2! ... k_r!). The total number of terms in the expansion of (x_1 + x_2 + ... + x_r)^n is C(n + r - 1, r - 1). (3) Legendre's Formula (de Polignac's Formula): The highest power / exponent of a prime p that divides n!, denoted by E_p(n!), is given by the sum of floor quotients: E_p(n!) = sum_{k=1}^infty floor(n / p^k) = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ... where the sum terminates when p^k > n. This formula directly solves questions regarding the number of trailing zeros in n! (which equals E_5(n!) since 5 is rarer than 2 in prime factorizations).