Combinatorics & Counting

If one choice can be made in m ways and an independent second choice in n ways, the pair of choices can be made in m × n ways. Extends to any number of independent stages by multiplying.

If two events are mutually exclusive (cannot both happen) with m and n ways respectively, the number of ways either occurs is m + n. Requires the option sets to be disjoint.

n! = n × (n−1) × ... × 2 × 1, the number of orderings of n distinct objects, with 0! = 1 by convention. Grows faster than any exponential.

The number of distinct orderings (arrangements) of n distinct objects is n!. Each ordering uses every object exactly once.

The number of ordered selections of k objects from n distinct objects is P(n, k) = n! / (n−k)! = n × (n−1) × ... × (n−k+1). Order matters, no repetition.

The number of unordered selections of k objects from n distinct objects is C(n, k) = n! / (k!·(n−k)!). Order does not matter, no repetition.