Discrete Math: Permutations, Combinations & Counting

If a task is a sequence of steps with m ways and then n ways, there are m × n ways in total.

If a task can be done in one of m ways or one of n other ways (no overlap), there are m + n ways.

n! = n(n-1)(n-2)\cdots 1 , and 0! = 1 by definition.

P(n, r) = \dfrac{n!}{(n - r)!} : ordered arrangements of r items from n

\dbinom{n}{r} = \dfrac{n!}{r!\,(n - r)!} : unordered selections of r items from n

Ask whether order matters. Ranking, seating, passwords or distinct roles: permutation. Committees, hands of cards, groups: combination.

10

720

2598960

12

\dfrac{11!}{1!\,4!\,4!\,2!} = 34{,}650

256

The number of nonnegative integer solutions of x_1 + x_2 + \cdots + x_k = n is \dbinom{n + k - 1}{k - 1} .

66

n people can sit around a round table in (n - 1)! distinct ways (rotations count as the same).

If n + 1 or more objects go into n boxes, some box holds at least two. In general, some box holds at least \lceil N/k \rceil of N objects in k boxes.

(x + y)^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k

\dbinom{n}{k} = \dbinom{n - 1}{k - 1} + \dbinom{n - 1}{k}

2^n , because \sum_k \binom{n}{k} counts every subset of an n -element set.