1.5 Counting and Combinatorics

Basic Principles

Addition Principle

If a task can be done in either of two disjoint ways, then the total ways are summed: |A∪B|=|A|+|B| when A∩B=∅.

Multiplication Principle

If a task consists of two steps with m ways for step 1 and n ways for step 2, then m×n total ways.

Permutations and Combinations

Permutations

Distinct: Number of ways to arrange n distinct items: n!.

Partial: Number of ways to choose and order k from n: P(n,k)=n!/(n-k).

With Repetition: nk sequences of length k from n types.

Combinations

Without Repetition: Number of ways to choose k from n: ([n],[k])=n!/(k!(n-k)!).

With Repetition: Number of multisets of size k from n types: ([n+k-1],[k]).

Binomial Theorem

For any integer n≧0:

(x+y)n=(∑_k=0^n)(([n],[k])*x(n-k)*yk)

Pigeonhole Principle

If n pigeons are placed into m holes and n>m, then some hole contains at least two pigeons. More generally: at least one hole has at least ⌈n/m⌉ pigeons.