Combinatorics

Cheat Sheet

Many Laplace Space calculations reduce to counting.

Choose $k$ times from $n$ options, order matters, repetition allowed:

n^{k}

Example: PIN codes, repeated die rolls.

Choose $k$ distinct objects from $n$ , order matters:

n (n - 1) \dots (n - k + 1) = \frac{n !}{( n - k )!}

This is the number of $k$ -permutations.

Choose $k$ distinct objects from $n$ , order does not matter:

(k n) = \frac{n !}{k ! ( n - k )!}

Example: 5-card hands from a deck.

Choose $k$ objects from $n$ types, order does not matter, repetition allowed:

(k n + k - 1)

This is the stars and bars formula.