What is Combinatorics? Combinatorics is a young field of mathematics, starting to be an independent branch only in the 20th century. However, combinatorial methods and problems have been around ever since. Many combinatorial problems look entertaining and one can easily say that roots of combinatorics lie in mathematical creativity and games.
Nonetheless, this field has grown to be of great importance in today’s world, not only because of its use for other fields like physical sciences, social sciences, biological sciences, information theory and computer science. Combinatorics is concerned with: Arrangements of elements in a set into patterns satisfying specific rules, generally referred to as discrete structures. Here “discrete” (as opposed to continuous) typically also means finite, although we will consider some infinite structures as well. •The existence, enumeration, analysis and optimization of discrete structures.
Interconnections, generalizations- and specialization-relations between several discrete structures. Existence: We want to arrange elements in a set into patterns satisfying certain rules. Is this possible? Under which conditions is it possible? What are necessary, what sufficient conditions? How do we find such an arrangement? Enumeration: Assume certain arrangements are possible. How many such arrangements exist? Can we say “there are at least this many”, “at most this many” or “exactly this many”? How do we generate all arrangements efficiently? Classification: Assume there are many arrangements. Do some of these arrangements differ from others in a particular way? Is there a natural partition of all arrangements into specific classes? Meta-Structure: Do the arrangements even carry a natural underlying structure, e.g., some ordering? When are two arrangements closer to each other or more similar than some other pair of arrangements? Are different classes of arrangements in a particular relation? Optimization: Assume some arrangements differ from others according to some measurement. Can we find or characterize the arrangements with maximum or minimum measure, i.e. the “best” or “worst” arrangements? 4 Interconnections: Assume a discrete structure has some properties (number of arrangements . . .) that match with another discrete structure. Can we specify a concrete connection between these structures? If this other structure is well-known, can we draw conclusions about our structure at hand? We will give some life to this abstract list of tasks in the context of the many real life example.