Combinatorics

The study of counting, arrangement, and selection of discrete structures.

• permutations count ordered arrangements; combinations count unordered selections
• pigeonhole principle:: if n items are placed in m containers with n > m, at least one container holds more than one item
• generating functions encode sequences as coefficients of formal power series
• Ramsey theory:: sufficiently large structures inevitably contain ordered substructures
• graph enumeration counts distinct graphs and connects to graph theory
• binomial coefficients and Pascal’s triangle arise in probability and algebra
• inclusion-exclusion principle computes sizes of unions via alternating sums of intersections
• Related: number theory, set theory, logic, information theory, game theory