Combinatorics

Combinatorics is the branch of mathematics that studies counting, arrangement, and combination of objects, as well as the properties and structures that arise from discrete systems. It seeks to determine how many configurations are possible under given constraints and to understand patterns that emerge when objects are organized in different ways. The field is foundational for many areas of mathematics and computer science because discrete choices arise in a wide range of problems.

Core subfields include enumerative combinatorics, which counts objects such as subsets, sequences, and tilings; graph theory, which analyzes networks of vertices connected by edges; and design theory and coding theory, which apply combinatorial ideas to information transmission and experimental design. Key concepts include permutations, combinations, binomial coefficients, partitions, compositions, and various special numbers such as Stirling and Catalan numbers. Principles such as the pigeonhole principle and inclusion-exclusion provide simple, powerful counting tools.

Methods used in combinatorics include bijective proofs that establish one-to-one correspondences, generating functions that encode combinatorial data into algebraic objects, and recurrence relations and dynamic programming for counting and optimization. The probabilistic method uses randomness to prove existence or to bound quantities. Group actions and Burnside's lemma or Polya's enumeration help count objects up to symmetry.

Applications span computer science, cryptography, coding theory, experimental design, scheduling, and network design. Combinatorial techniques also interact with algebra, geometry, and topology, giving rise to areas such as algebraic combinatorics and geometric combinatorics. The subject has roots in early work by Fermat, Pascal, and Euler and has developed into a broad, collaborative field with continuing relevance across mathematics and science.