Counting & axioms formulas

Selecting and arranging r of n distinct objects. P(n,n) = n! is the number of orderings of all n, and P(n,0) = 1 because 0! = 1.

Selecting r of n distinct objects with no arrangement. Related to permutations by P(n,r) = r! times the binomial coefficient. The binomial coefficient is taken as 0 when r > n.

The sum counts all subsets of an n-element set, so there are 2^n - 1 non-empty subsets. Useful for 'at least one' style selections.

Putting x = y = 1 gives the sum 2^n. Putting x = -1, y = 1 shows that the alternating sum of the binomial coefficients is 0 for n >= 1.

For finite sets. The count of objects with NONE of the properties is the total minus the union. The same pattern for probabilities is in section 4.

The number of ways to split n distinct objects into LABELLED groups of sizes n_1, ..., n_k, and equally the number of arrangements of n objects with repeated types. If the groups are unlabelled, divide by m! for each set of m groups of the same size. For example, 6 distinct people split into three unlabelled pairs: 6!/(2! 2! 2! 3!) = 15.

Distributing n identical objects into k distinct boxes with no limit per box. For a lower bound x_i >= a, substitute y_i = x_i - a and reduce n by a. For an upper bound x_i <= b, count all solutions and subtract those with x_i >= b + 1, using inclusion-exclusion when several variables are bounded.

Also the number of ways to place m distinct objects into n distinct boxes with every box non-empty. It comes from inclusion-exclusion over the set of boxes left empty, and is 0 when m < n. Check: m = 4, n = 2 gives 16 - 2 = 14; m = 4, n = 3 gives 81 - 48 + 3 = 36.

Valid only when the sample space is finite and every outcome is equally likely. State this assumption before using it; the wording of the question (a fair die, chosen at random, uniformly) is what justifies it.

Every other rule is derived from these three. Axiom 3 applies to any finite or countably infinite sequence of events, but only if they are pairwise mutually exclusive.

Use it for 'at least one' events: compute the probability that none occurs and subtract from 1.

Holds for any two events. The subtraction removes the overlap, which was counted twice.

Holds for any three events.

Holds for any events. The signs alternate: singles plus, pairs minus, triples plus, and so on. S_k has C(n,k) terms.

The first formula holds for any A and B; the simpler form P(B) - P(A) needs A to be a subset of B. The union bound holds with no condition.

The lower bound follows from P(A union B) <= 1; the upper bound from monotonicity. It gives the possible values of the intersection when only the two marginal probabilities are known.

With the conditional probability P(A | B) = P(A and B)/P(B), defined for P(B) > 0, independence is equivalent to P(A | B) = P(A). If A and B are independent, so are A and B^c, A^c and B, and A^c and B^c.

All four equations are required; pairwise independence is only the first three. For n events, the product rule must hold for every sub-collection of two or more events, which is 2^n - n - 1 equations.

Valid when A_1, ..., A_n are mutually independent: their complements are then mutually independent too, and the probability that none occurs is the product.

An urn has R red and B blue balls, and n <= R + B balls are drawn at random without replacement. Order is ignored in both the numerator and the denominator.

Assumes N equally likely days and independent birthdays (N = 365, ignoring 29 February). For k > N the probability is 0. The probability that at least two people share a birthday is 1 minus this.

n letters are placed at random in n addressed envelopes, one per envelope. D_n counts the permutations with no fixed point: D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44. Recurrence: D_n = (n-1)(D_{n-1} + D_{n-2}) for n >= 3. As n grows, P(no match) tends to 1/e, about 0.3679.