List of combinatorics topics


List of combinatorics topics

This is a list of combinatorics topics.

A few decades ago it might have been said that combinatorics is little more than a way to classify poorly-understood problems, and some standard remedies. Great progress has been made since 1960.

This page is complementary to the list of graph theory topics: graph theory being the part of combinatorial mathematics that is most like a separate discipline. In general, combinatorics is as much about problem solving as theory building.

Since combinatorial mathematics is effectively the environment for the study of data structures in computer science, there are very many topics that arise there. The same could be said for other fields, such as error-correcting codes, bioinformatics.

General combinatorial principles and methods

To begin with, some general principles:

*Fundamental theorem of combinatorial enumeration
*Combinatorial principles
*Trial and error, brute force search, bogosort, British Museum algorithm
*Pigeonhole principle
*Method of distinguished element
*Mathematical induction
*Recurrence relation, telescoping series
*Generating functions as an application of formal power series
**Schrödinger method
**exponential generating function
**Stanley's reciprocity theorem
*Binomial coefficients and their properties
*Combinatorial proof
** Double counting (proof technique)
** Bijective proof
*Inclusion-exclusion principle
*Möbius inversion formula
*Parity, even and odd permutations
*Combinatorial Nullstellensatz
*Incidence algebra
*Greedy algorithm
*Divide and conquer algorithm
**Akra-Bazzi method
*Dynamic programming
*Branch and bound
*Birthday attack, birthday paradox
*Floyd's cycle-finding algorithm
*Reduction to linear algebra
*Sparsity
*Weight function
*Minimax algorithm
**Alpha-beta pruning
*Probabilistic method
*Sieve methods
*Analytic combinatorics
*Symbolic combinatorics
*Combinatorial class
*Exponential formula
*Twelvefold way

Problem solving as an art

*Heuristic
*Inductive reasoning
*"How to Solve It"
*Creative problem solving
*"Art of Problem Solving"

ome general theories

*Matroid
*Greedoid
*Ramsey theory
**Van der Waerden's theorem
**Hales-Jewett theorem
**Umbral calculus, binomial type polynomial sequences
*Combinatorial species

Living with large numbers

*Names of large numbers, long scale
*History of large numbers
*Graham's number
*Moser's number
*Skewes' number
*"Large number notations"
**Conway chained arrow notation
**Hyper4
**Knuth's up-arrow notation
**Moser polygon notation
**Steinhaus polygon notation
*"Large number effects"
**Exponential growth
**Combinatorial explosion
**Branching factor
**Granularity
**Curse of dimensionality
**Concentration of measure

Topics in combinatorics: alphabetical list

0-9

*Binary matrix (i.e. "(0,1)-matrix")

A

*Abstract simplicial complex
*Addition chain
**Scholz conjecture
*Algebraic combinatorics
*Alternating sign matrix
*Almost disjoint sets
*Antichain
*Arrangement of hyperplanes
*Assignment problem
**Quadratic assignment problem
*Audioactive decay

B

*Barcode
**Matrix code
**QR Code
**Universal Product Code
*Bell polynomials
*Bertrand's ballot theorem
*Binomial theorem
*Block design
**Symmetric balanced incomplete block design (SBIBD)
**Balanced incomplete block design (BIBD)
**Partially balanced incomplete block design (PBIBD)
*Block walking
*Boolean satisfiability problem
**2-satisfiability
**3-satisfiability
*Bracelet (combinatorics)
*Bruck-Chowla-Ryser theorem

C

*Catalan number
*Cellular automaton
**Conway's Game of Life
*Collatz conjecture
*Combinadic
*Combination
*Combinatorial design
*Combinatorial optimization
*Combinatorial search
*Constraint satisfaction problem
*Cycles and fixed points
*Cyclic order
*Cyclic permutation
*Cyclotomic identity

D

*Data integrity
**Alternating bit protocol
**Checksum
**Cyclic redundancy check
***Luhn formula
**Error detection
***Error-detecting code
***Error-detecting system
**Message digest
**Redundancy check
**Summation check
*De Bruijn sequence
*Deadlock
*Delannoy number
**Dining philosophers problem
**Mutual exclusion
**Rendezvous problem
*Derangement
*Dickson's lemma
*Dinitz conjecture
*Discrete optimization
*Dobinski's formula

E

*Eight queens puzzle
*Entropy coding
*Enumeration
**Algebraic enumeration
**Combinatorial enumeration
**Burnside's lemma
*Erdős-Ko-Rado theorem
*Euler number

F

*Faà di Bruno's formula
*Factoradic
*Family of sets
*Faulhaber's formula
*Fifteen puzzle
*Finite geometry
*Finite intersection property

G

*Game theory
**Combinatorial game theory
***Combinatorial game theory (history)
***Combinatorial game theory (pedagogy)
***Star (game)
***Zero game, fuzzy game
**Dots and Boxes
**Impartial game
***Digital sum
***Nim
***Nimber
***Sprague-Grundy theorem
**Partizan game
**Solved board games
**Col game
**Sim
**Sprouts (game)
**Surreal numbers
**Transposition table
**Black Path Game
**Sylver coinage
*Golomb coding
*Golomb ruler
*Graeco-Latin square
*Gray code

H

*Hadamard matrices
**Complex Hadamard matrices
**Butson-type Hadamard matrices
**Generalized Hadamard matrices
**Regular Hadamard matrices
*Hamming distance
*Hash function
**Hash collision
**Perfect hash function
*Hat problem
*Heilbronn triangle problem
*Helly family
*Hypergeometric function identities
*Hypergeometric series
*Hypergraph

I

*Incidence structure
*Integer partition
**Ferrers graph

K

*Kakeya needle problem
*Kirkman's schoolgirl problem
*Knapsack problem
*Kruskal-Katona theorem

L

*Lagrange inversion theorem
*Lagrange reversion theorem
*Lah number
*Large number
*Latin square
*Levenshtein distance
*Lexicographical order
*Littlewood-Offord problem
*Lubell-Yamamoto-Meshalkin inequality (known as the LYM inequality)
*Lucas chain

M

*Magic square
*Marriage theorem
**Perfect matching
*Matroid embedding
*Monge array
*Monomial order
*Moreau's necklace-counting function
*Motzkin number
*Multiplicities of entries in Pascal's triangle
*Multiset
*Munkres' assignment algorithm

N

*Necklace (combinatorics)
*Necklace problem
*Negligible set
**Almost all
**Almost everywhere
**Null set
*Newton's identities

O

*Ordered partition of a set
*Orthogonal design
**Complex orthogonal design
**Quaternion orthogonal design

P

*Packing problem
**Bin packing problem
*Partition of a set
**Noncrossing partition
*Permanent
*Permutation
**Permutation matrix
**Permutations and combinations
**Josephus permutation
**Shuffling playing cards
*Pochhammer symbol
*Polyforms
**Polycubes
***Soma cube
**Polyiamonds
**Polyominoes
***Hexominoes
***Pentominoes
***Tetrominoes
**Polysquare puzzle
*Projective plane
*Property B
*Prüfer sequence

Q

*q-analog
*q-binomial theorem—see Gaussian binomial
*q-derivative
*q-series
*q-theta function
*q-Vandermonde identity

R

*Rencontres numbers
*Rubik's cube
**
**Optimal solutions for Rubik's Cube
**Rubik's Revenge

*Schröder number
*Search algorithm
**Binary search
**Interpolation search
**Linear search
**Local search
**String searching algorithm
***Aho-Corasick algorithm
***Fuzzy string searching
***grep, agrep, wildcard character
***Knuth-Morris-Pratt algorithm
*Sequences with zero autocorrelation function
*Series-parallel networks problem
*Set cover problem
*Shuffling puzzle
*Small set (combinatorics)
*Sparse matrix, Sparse array
*Sperner family
*Sperner's lemma
*Stable marriage problem
*Steiner system
*Stirling number
**Stirling transform
*String algorithm
*Straddling checkerboard
*Subsequence
**Longest common subsequence problem
***Optimal-substructure
*Subset sum problem
*Symmetric functions
*Szemerédi's theorem

T

*Thue-Morse sequence
*Tower of Hanoi
*Turán number
*Turing tarpit

U

*Urn problems (probability)

V

*Vandermonde's identity

W

*Weighing matrices
*Weighted round robin
**Deficit round robin
*Wigner-d'Espagnat inequality

Y

*Young tableau

Data structure concepts

*Data structure
**Data type
**Abstract data type
**Algebraic data type
**Composite type
*Array
*Associative array
*Deque
*List
**Linked list
*Queue
**Priority queue
*Skip list
*Stack
*Tree data structure
*Automatic garbage collection

People

*Noga Alon
*George Andrews
*Eric Temple Bell
*Belá Bollobás
*Peter Cameron
*Louis Comtet
*John Horton Conway
**On Numbers and Games
**Winning Ways for your Mathematical Plays
*Persi Diaconis
*Ada Dietz
*Paul Erdős
**Erdős conjecture
*Solomon Golomb
*Ben Green
*Tim Gowers
*Gyula O. H. Katona
*Imré Leader
*Luke Pebody
*George Pólya
*Gian-Carlo Rota
*Cecil C. Rousseau
*Dick Schelp
*Vèra T. Sôs
*Joel Spencer
*Emanuel Sperner
*Richard P. Stanley
*Endre Szemerédi
*Terence Tao
*Jacques Touchard
*Bartel Leendert van der Waerden
*Herbert Wilf
*Doron Zeilberger

Journals

* Annals of Combinatorics
* Ars Combinatoria
* Australasian Journal of Combinatorics
* Bulletin of the Institute of Combinatorics and Its Applications
* Combinatorica
* Combinatorics, Probability and Computing
* Computational Complexity
* Designs, Codes and Cryptography
* Discrete and Computational Geometry
* Discrete Applied Mathematics
* Discrete Mathematics
* Discrete Mathematics & Theoretical Computer Science
* Discrete Optimization
* Discussiones Mathematicae Graph Theory
* Electronic Journal of Combinatorics
* European Journal of Combinatorics
* The Fibonacci Quarterly
* Finite Fields and Their Applications
* Graphs and Combinatorics
* Integers, Electronic Journal of Combinatorial Number Theory
* Journal of Algebraic Combinatorics
* Journal of Automata Languages and Combinatorics
* Journal of Combinatorial Designs
* Journal of Combinatorial Mathematics and Combinatorial Computing
* Journal of Combinatorial Optimization
* Journal of Combinatorial Theory, Series A
* Journal of Combinatorial Theory, Series B
* Journal of Complexity
* Journal of Cryptology
* Journal of Graph Algorithms and Applications
* Journal of Graph Theory
* Journal of Integer Sequences (Electronic)
* Journal of Mathematical Chemistry
* Online Journal of Analytic Combinatorics
* Optimization Methods and Software
* The Ramanujan Journal
* Séminaire Lostharingien de Combinatoire
* SIAM Journal on Discrete Mathematics

Prizes

* Euler Medal

Publications

*"Geombinatorics"

ee also

* list of factorial and binomial topics
* list of partition topics
* list of permutation topics
* list of puzzle topics.
* list of formal language and literal string topics
* combinatorial chemistry


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • List of topology topics — This is a list of topology topics, by Wikipedia page. See also: topology glossary List of general topology topics List of geometric topology topics List of algebraic topology topics List of topological invariants (topological properties)… …   Wikipedia

  • List of puzzle topics — This is a list of puzzle topics, by Wikipedia page.See also: * List of impossible puzzles * List of puzzle based computer and video games * List of game topics.* Acrostic * Anagram * Back from the klondike * Burr puzzle * Chess problem * Chess… …   Wikipedia

  • List of exponential topics — This is a list of exponential topics, by Wikipedia page. See also list of logarithm topics. *Accelerating change *Artin Hasse exponential *Bacterial growth *Baker Campbell Hausdorff formula *Cell growth *Barometric formula *Basic infection number …   Wikipedia

  • List of partition topics — This is a list of partition topics, in the mathematical sense. Partition (disambiguation) lists meanings in other fields. In mathematics, a partition may be a partition of a set or an ordered partition of a set, or a partition of a graph, or a… …   Wikipedia

  • Combinatorics — is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size (enumerative combinatorics), deciding when certain criteria can be met,… …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • List of basic statistics topics — For a more comprehensive list, see the List of statistics topics. Statistics is a mathematical science pertaining to the collection, analysis, interpretation, and presentation of data. It is applicable to a wide variety of academic disciplines,… …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • List of important publications in mathematics — One of the oldest surviving fragments of Euclid s Elements, found at Oxyrhynchus and dated to circa AD 100. The diagram accompanies Book II, Proposition 5.[1] This is a list of important publications in mathematics, organized by field. Some… …   Wikipedia

  • List of basic discrete mathematics topics — Discrete mathematics, also called finite mathematics, is the study of mathematical structures that are fundamentally , in the sense of not supporting or requiring the notion of continuity. Most, if not all, of the objects studied in finite… …   Wikipedia