What is the formula for permutations (ordered selection of k from n)?
P(n, k) = n! / (n-k)! — order matters.
What is the formula for combinations (unordered selection of k from n)?
C(n, k) = n! / (k! × (n-k)!) — order doesn’t matter. Also written as “n choose k”.
What is the difference between a permutation and a combination?
Permutation: order matters (arrangements). Combination: order doesn’t matter (selections).
What is the pigeonhole principle?
If n items are placed into m containers and n > m, at least one container must hold more than one item.
What is Pascal’s triangle relationship to combinations?
Each entry equals C(n, k). Each entry = sum of the two above: C(n, k) = C(n-1, k-1) + C(n-1, k).
How many ways can you arrange n distinct objects?
n! (n factorial) — the number of permutations of n items.
What is counting with repetition? (combinations)
Choosing k items from n with repetition allowed (order doesn’t matter): C(n+k-1, k).
What is conditional probability P(A|B)?
P(A|B) = P(A ∩ B) / P(B) — probability of A given that B occurred.
What is expected value?
E[X] = Σ x · P(X = x) — the probability-weighted average of all possible outcomes.
What is modular arithmetic?
Arithmetic where numbers wrap around at a modulus m: a mod m is the remainder of a ÷ m. Example: 7 mod 3 = 1.
How does the Euclidean algorithm compute GCD?
Recursive: gcd(a, b) = gcd(b, a mod b), base case: gcd(a, 0) = a.
What is LCM in terms of GCD?
LCM(a, b) = (a × b) / GCD(a, b).
What are the key powers of 2 to memorize?
2^10 = 1,024 (~1K) · 2^20 ≈ 1M · 2^30 ≈ 1B · 2^32 ≈ 4B
What does XOR do at the bit level?
Returns 1 if bits differ, 0 if same. Key properties: a XOR a = 0, a XOR 0 = a, commutative and associative.
How do you check if a number is a power of 2 using bit manipulation?
n > 0 && (n & (n - 1)) == 0 — powers of 2 have exactly one bit set, so subtracting 1 clears it and all lower bits become 1.
How do you isolate the lowest set bit of an integer n?
n & (-n) — two’s complement makes -n flip all bits and add 1, so the AND isolates the lowest set bit.
What is a left bit shift (<<) equivalent to?
Multiplying by 2 per shift: n << k = n × 2^k (for non-negative n with no overflow).
What is a right bit shift (>>) equivalent to?
Dividing by 2 per shift (integer division): n >> k = ⌊n / 2^k⌋.
What is mathematical induction?
Base case: prove for n=0 (or n=1). Inductive step: assume true for n, prove for n+1. Concludes the statement holds for all n ≥ base.
What is proof by contradiction?
Assume the negation of what you want to prove; derive a logical contradiction; conclude the original statement must be true.
What is proof by contrapositive?
Instead of proving P → Q, prove the equivalent ¬Q → ¬P — sometimes easier.
What is a primality test for a number n?
Check divisibility by all integers from 2 to √n. If none divide n evenly, n is prime. O(√n).
What is log₂(n) approximately equal to for powers of 2?
log₂(1024) = 10, log₂(1M) ≈ 20, log₂(1B) ≈ 30 — log₂ = number of bits needed to represent n.
What is the relationship between log base 2 and log base 10?
log₂(n) = log₁₀(n) / log₁₀(2) ≈ log₁₀(n) × 3.32.
