What is the difference between a permutation and a combination?

Permutations count ordered arrangements of r items from n (order matters): P(n,r)=n!/(n−r)!. Combinations count unordered selections: C(n,r)=n!/(r!(n−r)!).

When should you use stars and bars?

Use stars and bars to count nonnegative integer solutions to x1+x2+...+xk=n (distributing n indistinguishable items into k distinct bins). The count is C(n+k−1, k−1).

What is the principle of inclusion-exclusion?

To count elements in the union of overlapping sets, add sizes of each set, subtract pairwise overlaps, add triple overlaps, and so on: |A∪B∪…|=Σ|Ai|−Σ|Ai∩Aj|+Σ|Ai∩Aj∩Ak|−….

What is the pigeonhole principle?

If n items are placed into m containers and n>m, at least one container contains more than one item. This yields existence results from simple counting.

How do binomial coefficients count subsets and relate to identities?

C(n,r) counts r-element subsets of an n-element set. They satisfy identities like C(n,r)=C(n−1,r−1)+C(n−1,r) and C(n,r)=C(n,n−r).