← all systems · see it in The System
Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures.
Properties published scienceour proposal
Sourced fields, and our own readings.
| aliases | Combinatorics |
| born at | 16th century BC (Rhind papyrus problem 79) |
| born precision | century; the start contested (C-3246) |
| boundary | Inside: the practice of counting, arranging, choosing and building finite structures (enumeration, existence, construction, optimisation), its methods (bijections, generating functions, the pigeonhole principle, the probabilistic method, computer search and SAT certificates), the people and machines that carry it, and the structures it works on (permutations, combinations, partitions, designs, graphs, set systems, words, polytopes). Outside: the objects counted when they belong to another system (molecules, microstates, bells, experiments), and the neighbouring branches it feeds and borrows from (probability, algebra, number theory, topology, computer science), which it touches but does not contain. The edge itself is contested: 'The full scope of combinatorics is not universally agreed upon.' |
| nested level | An area of mathematics (often grouped as discrete mathematics), 'an independent branch of mathematics in its own right' since the later twentieth century. Runs on people (from Sushruta, Mahavira and Pascal to Erdos and today's journals and conferences), on writing (notation, diagrams, papers) and, since the late twentieth century, on computers (case checks, SAT solvers, program search with language models). |
| scale | social |
Measures (20) published science
| characteristic clock: how long a central bound stands before its first exponential improvement (diagonal Ramsey upper bound, 1935 to 2023) | 88 years (derived from the two dates the source gives) |
| earliest recorded combinatorial technique | 16th century BC date (Rhind papyrus, problem 79) |
| combinations of six tastes (Sushruta) | 63 combinations (2^6 - 1) |
| ways to choose 2 from 4 | 6 subsets |
| partitions of 4, p(4) | 5 partitions |
| generating functions introduced | 1730 year (de Moivre) |
| pigeonhole principle first in print | 1622 year (Leurechon, Selectae Propositiones); Dirichlet's use 1842, often dated 1834 |
| R(3,3) | 6 people (vertices) |
| R(5,5) bounds | 43 <= R(5,5) <= 46 vertices (lower 1989, upper 2024) |
| R(4,5) | 25 vertices |
| diagonal Ramsey upper bound | (4 - e)^k with e = 2^-7 (2023); 3.8^k (Gupta, Ndiaye, Norin, Wei); 4^k (1935) vertices, as a function of k |
| diagonal Ramsey lower bound | 2^(k/2) (Erdos 1947), improved only by a factor of 2 (Spencer 1977) vertices, as a function of k |
| Boolean Pythagorean triples threshold | 7825 the least n for which every 2-colouring of 1..n has a monochromatic Pythagorean triple (7824 can be split) |
| size of the Pythagorean triples proof | almost 200 terabytes (DRAT format) |
| machine time for the Pythagorean triples problem | 800 cores, about 2 days cluster time |
| cap set search space at n = 8 | about 3^1600 candidate sets |
| cap set found by program search in dimension 8 | 512 vectors |
| wait for the existence of designs | 1853 to 2014 (Steiner's question to Keevash's proof) years: 161, derived from the two dates |
| orthogonal Latin squares of order d exist | every d except 2 and 6 orders |
| Boltzmann constant (the conversion from log of a count to entropy) | 1.380649 × 10−23 J/K |
Open contentions (6) open contention
Where sources or readings disagree. Both stay on the map.
- C-413 Where do thoughts come from?
booked: No theory is proven, so the map lists the main ones side by side and doesn't pick one. It shows where thinking is handled in the brain, not where thoughts start.
the other reading: as registered - C-2349 Is mathematics discovered or invented?
booked: The map keeps the schools side by side.
the other reading: as registered - C-2351 Will machine-checked proofs replace human refereeing?
booked: The map keeps both views.
the other reading: as registered - C-3245 Do counting results need a direct combinatorial explanation?
booked: The map keeps the competing readings; none is ruled.
the other reading: #P membership as the workable definition (Pak); interpretations as projections that reveal hidden structure (the 'deeper reason' Pak calls unfortunate) - C-3247 What does combinatorics cover?
booked: The map keeps the competing readings; none is ruled.
the other reading: Ryser: hard to define because it crosses so many subdivisions; Mirsky: 'a range of linked studies' diverging in aims, methods and coherence; graph theory as a part of combinatorics, or as a separate subject; partly fragmented by the very connections that dissolved its borders - C-3271 Where did the pigeonhole principle come from?
booked: The map keeps the competing readings; none is ruled.
the other reading: Dirichlet 1834 (the year 'frequently mentioned'); Dirichlet's 1842 uses, the earliest the authors find in his writings; older, unwritten use: 'not necessarily being the origin of the very idea'
Partners and parts published science
Built from / builds (10)
- The mathematical community and its subfields
- Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on
- Permutation (an arrangement: a bijection of a finite set onto itself)
- Combination and binomial coefficient ('n choose k')
- Integer partition
- Combinatorial design (block designs, Latin squares, Steiner systems)
- Generating function (a method)
- Pigeonhole principle (a method)
- Probabilistic method (a method)
- Ramsey theory
Sits inside / holds (3)
- Human society (from local community up to societies)
- Mathematics (the field: the practice and the structures it studies)
- Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on
Trades with (valence) (14)
- Human (Homo sapiens) via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Chemistry (the field: the practice of chemists and the structure of substances and their reactions it works on) via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Statistical mechanics via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Quantum entanglement via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Large language model via sys:computer-hardware · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Mathematics (the field: the practice and the structures it studies) via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Algebra (the practice of solving for unknowns and transforming expressions, and the structures it works with) via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Statistics: the practice of collecting and reasoning from data, the intuitive statistics it grows from, and the structure (samples, distributions, estimators) it works on via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Probability: weighing chances, in brains and in people's mathematics, and the structure it works on via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Cryptography via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Set theory: the study of sets (collections taken as single objects), membership, Cantor's infinities and the axioms, and the practice of the people and machines who work with them via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Computer science (the field: the practice and the computation it studies) via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on via sys:written-record · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
- Prime numbers (the practice of number theory that finds, proves and uses them, and the structure of the primes it works on) via sys:sensory-environment · Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them gain
expressed by (12)
- Generation/Synthesis
- Recombination/Composition
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Interoperability/Transduction (Bridging)
- Encapsulation & Modularity (Abstraction)
- Search/Foraging
- Uncertainty Reduction/Learning
- Hypothesis Portfolio / Multiple Hypothesis Tracking
- Validation of Effectiveness
- Redundancy & Diversity
- Quality Control & Error Correction
floor filled by (24)
- Human (Homo sapiens)
- Writing (the practice of marking language on a surface, and the script plus rules it works with)
- Chemistry (the field: the practice of chemists and the structure of substances and their reactions it works on)
- Statistical mechanics
- Large language model
- Human brain
- The world through the senses (sensory environment)
- Statistics: the practice of collecting and reasoning from data, the intuitive statistics it grows from, and the structure (samples, distributions, estimators) it works on
- Computer hardware
- Computer science (the field: the practice and the computation it studies)
- The mathematical community and its subfields
- Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on
- Permutation (an arrangement: a bijection of a finite set onto itself)
- Combination and binomial coefficient ('n choose k')
- Integer partition
- Combinatorial design (block designs, Latin squares, Steiner systems)
- Generating function (a method)
- Pigeonhole principle (a method)
- Probabilistic method (a method)
- Ramsey theory
- Enumerative combinatorics
- Extremal combinatorics
- Algebraic combinatorics
- SAT solver
Kinds (16)
- Finite geometry
- Mathematics (the field: the practice and the structures it studies)
- Enumerative combinatorics
- Analytic combinatorics
- Partition theory
- Design theory
- Order theory
- Matroid theory
- Extremal combinatorics
- Probabilistic combinatorics
- Algebraic combinatorics
- Combinatorics on words
- Geometric combinatorics
- Topological combinatorics
- Arithmetic (additive) combinatorics
- Infinitary combinatorics (combinatorial set theory)
Notes published science
- The pigeonhole principle is named after Dirichlet, but it was in print two centuries earlier as a Jesuit teaching line: two men must have the same number of hairs. A 1624 book made a wager of it, and the 'two people with the same number of hairs' example is still how it is taught. Source: src:rittaud-heeffer-2014.
- Euler's puzzle of 36 officers (six ranks, six regiments, no repeats in any row or column) has no solution, as was proved in 1900. It does have one if the officers are quantum-entangled, and that solution is a long-sought maximally entangled state whose entries involve the golden ratio. Source: src:rather-2022.
- The numbers 1 to 7824 can be split into two groups with no a² + b² = c² inside either group, but 1 to 7825 cannot. Proving the 7825 case took 800 computer cores about two days and produced a proof of almost 200 terabytes, which its own authors say looks like 'a giant heap of random information' to a person. Source: src:heule-2016.
Layers
The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.
combinatorics: finite things arranged, chosen and counted, up to the theory of finite structures and its uses (reader's view)
- L1: Finite things in the world to be arranged, chosen and counted: six tastes, the hairs on men's heads, church bells, fifteen schoolgirls walking three abreast, the atoms of a gas; and the marks that write them down.
- L2: Taking an arrangement in: a diagram seen (the arithmetical triangle, Young diagrams), a problem read or heard as a puzzle about well-known things (hairs, coins, schoolgirls), a question met 'in isolation' inside some other piece of mathematics.
- L3: Codes: the standard objects, permutations (n! arrangements), combinations ('n choose k'), partitions, graphs, designs, set systems, words; the twelvefold way sorts the basic counts into one table.
- L4: Methods: counting by bijection and recurrence, generating functions, the pigeonhole principle, the probabilistic method, linear programming and computer case checks, SAT solving, program search; many problems are easy to check and hard to solve.
- L5: The questions that steer the work: enumeration, existence, construction, optimisation; open bounds (Ramsey numbers, cap sets) held as targets until closed.
- L6: Theory: the subfields (enumerative, analytic, extremal, Ramsey, probabilistic, algebraic, design, geometric, topological, arithmetic, infinitary) and their theorems; order forced in any large enough structure; numbers read as counts of objects, with #P as a proposed test of what counts.
- L7: Use and standing: an independent branch of mathematics whose objects and counts are used across the sciences (analysis of algorithms, statistical physics, design of experiments, chemistry, cryptography, evolutionary biology).
the boardroom (shared floors)
- L3: The standard objects: permutations, combinations, partitions, graphs, designs, set systems; the twelvefold way's table; a number in the field 'always' counts some combinatorial objects.
- L4: The methods: bijections and recurrences, generating functions (de Moivre, 1730), the pigeonhole principle (Leurechon 1622, Dirichlet), the probabilistic method (Erdos 1947), linear programming and computer case checks, SAT certificates, program search with language models.
- L5: The four questions (enumeration, existence, construction, optimisation) and the open bounds they leave: R(5,5) between 43 and 46, the diagonal Ramsey gap, the largest cap set beyond n = 6.
- L6: Theory and subfields; order forced in large structures (Ramsey); numbers read as counts, with #P proposed as the test of a combinatorial interpretation; results felt as beautiful or not.
- L7: Standing and use: an independent branch, with dozens of journals and conferences; its objects used across the sciences, its theory the mother of branches that left it.
way in: Counting problems arriving from the sciences (microstates, chemical compounds, experiments, algorithms)
- L1: A system with many possible arrangements: a gas whose energy can be shared among its particles in many ways, a family of chemical compounds, the plots of a biological experiment.
- L2: The question taken over as a counting problem: how many ways, counted up to the symmetry the scientist does not see.
way in: Emotion: the felt beauty of a result
- L1: A formula or result rated beautiful, indifferent or ugly by mathematicians.
- L2: Felt beauty, tracked by activity in field A1 of the medial orbito-frontal cortex, the same field as beauty from other sources.
way in: Machines: case checks, SAT solvers and language-model program search
- L1: The problem encoded for a machine: thousands of Boolean variables and clauses (F7825: 6494 variables, 18944 clauses), or a program skeleton with one function to evolve.
- L2: Search: cube-and-conquer with look-ahead and CDCL solvers on 800 cores for about two days; or a language model proposing programs that an evaluator scores.
- L3: The machine's verdict as a checkable object: a satisfying assignment checkable in a second, a refutation certificate of almost 200 terabytes, or a short program that generates the construction.
way in: Posed problems in print: queries, prizes and open questions (Kirkman 1850, Steiner 1853, Graham's prize)
- L1: A problem set down in print, sometimes with a prize: the schoolgirls query in a Diary, Steiner's question, Graham's $100 for the Pythagorean triples problem.
- L2: The problem read by solvers; long met one at a time inside some other mathematical context.
way in: Sight: diagrams of arrangements (the arithmetical triangle, Young and Ferrers diagrams, coloured graphs)
- L1: A drawn diagram: the arithmetical triangle of binomial coefficients, a Young diagram of a partition, a graph with coloured edges.
- L2: The diagram seen as the object: a partition read off its rows of boxes; each row of the triangle read from the row above.
way in: Things to arrange: tastes, hairs, coins, bells, people (taste, touch and the everyday world)
- L1: A finite stock of things met in daily life: six tastes, the hairs on a head or the coins in a purse, a party of six people.
- L2: The things taken in as a puzzle about well-known phenomena, made tangible for an audience (hairs and coins in the 1622 and 1624 Jesuit books).
way in: Thought: combining a few concepts into many, and weighing the candidates
- L1: A finite set of concepts held in mind (a kind, a quantity), the stock combinatorial thought draws on.
- L2: Combining: concepts joined into new wholes, shown already in infants in their first year (a taught word for 2 joined with 'duck').
- L3: Constructing and weighing many candidate solutions under constraints, tracking the best outcome reachable so far; in macaques, single prefrontal (DLPFC) neurons encode and update that bound.
way out: Designs laid out in the world: experiments, tournaments, lotteries, codes
- L1: The arrangement laid out: plots of a biological experiment, a schedule, a ticket set.
- L7: A design chosen for a use: Fisher's experimental designs, tournament schedules, lotteries, networking, group testing, cryptography.
way out: Programs and certificates handed to machines and checkers
- L1: Bits on disk: a certificate of almost 200 terabytes; a program that generates a 512-vector cap set.
- L4: The proof put in a form a checker can verify (DRAT), or the best programs fed back into the model's prompts.
way out: Speech: public disputations, puzzles told and wagers made
- L1: A wager spoken aloud: that two people in Paris have the same number of hairs.
- L7: Mathematics argued in public, weekly, monthly and yearly, before nobility and gentry.
way out: Writing: theorems, proofs and papers
- L1: Papers, journals and conference proceedings.
- L4: The proof written out, with both authors' independent computations.
- L6: A theorem stated (R(k) <= (4 - e)^k; R(5,5) <= 46).
Sources (27) published science
Campos, Griffiths, Morris, Sahasrabudhe: An exponential improvement for diagonal Ramsey (arXiv:2303.09521, v2 2025; Annals of Mathematics) (behind its links)
Romera-Paredes et al.: Mathematical discoveries from program search with large language models (Nature 2024, doi:10.1038/s41586-023-06924-6, PMC10794145, CC BY) (behind its links)
Heule, Kullmann, Marek: Solving and verifying the boolean Pythagorean Triples problem via Cube-and-Conquer (arXiv:1605.00723; SAT 2016) (behind its links)
Graph theory (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Rittaud, Heeffer: The pigeonhole principle, two centuries before Dirichlet (Mathematical Intelligencer 36, 2014; Ghent repository copy, 2013) (behind its links)
Combinatorial explosion (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Hong, Stauffer: Neural correlates of combinatorial reasoning in prefrontal cortex (bioRxiv 2026, doi:10.64898/2026.03.05.709889) (behind its links)
Integer partition (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Ramsey theory (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Angeltveit, McKay: R(5,5) <= 46 (arXiv:2409.15709, v2 2025) (behind its links)
Keevash: The existence of designs (arXiv:1401.3665) (behind its links)
Rather, Burchardt, Bruzda, Rajchel-Mieldzioć, Lakshminarayan, Życzkowski: Thirty-six entangled officers of Euler (arXiv:2104.05122; Physical Review Letters 2022) (behind its links)
Boltzmann's entropy formula (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Permutation (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Pak: What is a combinatorial interpretation? (arXiv:2209.06142, survey) (behind its links)
Pólya enumeration theorem (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)