Counting fundamentals

Addition: if a task can be done in one of two mutually exclusive ways with a and b options, there are a + b outcomes. Multiplication: if it takes a sequence of independent choices with a then b options, there are a × b outcomes.

A 4-character lowercase code has 26⁴ = 456,976 possibilities. Brute force over a binary string of length n takes 2ⁿ steps.

P(n, k) = n! / (n - k)! = n · (n - 1) · … · (n - k + 1) counts ordered selections of k items from n. Order matters: “first, second, third place” among 10 runners is P(10, 3) = 720.

Set n and k below to see the formula and the list of arrangements.

1static long perm(int n, int k) { long r = 1; for (int i = 0; i < k; i++) r *= (n - i); return r; }
2long podium = perm(10, 3);   // 720

1static void pick(int[] items, int r, boolean ordered, int start,
2                 List<Integer> current, boolean[] used, List<List<Integer>> out) {
3    if (current.size() == r) { out.add(new ArrayList<>(current)); return; }
4    for (int i = ordered ? 0 : start; i < items.length; i++) {
5        if (used[i]) continue;                  // each item at most once
6        used[i] = true;
7        current.add(items[i]);
8        pick(items, r, ordered, i + 1, current, used, out);
9        current.remove(current.size() - 1);     // backtrack
10        used[i] = false;
11    }
12}

C(n, k) = n! / (k! (n - k)!) counts unordered selections. It equals P(n, k) / k!, because each group of k items has k! orderings. C(n, k) = C(n, n - k), and Pascal's rule C(n, k) = C(n - 1, k - 1) + C(n - 1, k) builds all values additively, avoiding large factorials.

C(5, 2) = 10 handshakes among 5 people. Switch the animation to combinations to see the groups.

1static long comb(int n, int k) {
2    k = Math.min(k, n - k);
3    long r = 1;
4    for (int i = 1; i <= k; i++) r = r * (n - k + i) / i;   // exact at every step
5    return r;
6}
7long c = comb(52, 5);   // 2598960 poker hands

1static void pick(int[] items, int r, boolean ordered, int start,
2                 List<Integer> current, boolean[] used, List<List<Integer>> out) {
3    if (current.size() == r) { out.add(new ArrayList<>(current)); return; }
4    for (int i = ordered ? 0 : start; i < items.length; i++) {
5        if (used[i]) continue;                  // each item at most once
6        used[i] = true;
7        current.add(items[i]);
8        pick(items, r, ordered, i + 1, current, used, out);
9        current.remove(current.size() - 1);     // backtrack
10        used[i] = false;
11    }
12}

(x + y)ⁿ = Σ C(n, k) xⁿ⁻ᵏ yᵏ. The coefficients form row n of Pascal's triangle. Setting x = y = 1 gives Σ C(n, k) = 2ⁿ, the number of subsets of an n-element set.

For example (x + y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴ and the coefficients sum to 16 = 2⁴.

If more than n items go into n boxes, some box holds at least two items. In general some box holds at least ⌈items / n⌉. Consequences: any hash function into m buckets collides once there are m + 1 keys; any set of n + 1 integers contains two whose difference is divisible by n.

It proves existence without finding the item, so it is often used to show that a collision or repeat must happen.

To count the union of overlapping sets, add the sizes and subtract the overlaps: |A ∪ B| = |A| + |B| - |A ∩ B|, and for three sets |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|.

Example: how many numbers from 1 to 999 are multiples of 3 or 5? 333 + 199 - 66 = 466, where 66 counts the multiples of 15.

1int n = 999;
2int count = n / 3 + n / 5 - n / 15;   // 333 + 199 - 66 = 466
3int brute = 0;
4for (int i = 1; i <= n; i++) if (i % 3 == 0 || i % 5 == 0) brute++;   // 466