Franka Miriam Brückler, Dept. of Mathematics, University of Zagreb, Croatia

Hansel und Gretel, the witch, Snow-white, Sleeping Beauty, the seven dwarfs and the prince on the white horse came to a dinner. In how many ways can they be seated around a round table so that both Snow-white and the Sleeping Beauty sit next to the prince, and that Hansel and Gretel do not sit next to the witch? (Note: only the relative position of the characters is important. The white horse is not to be seated at the table, but to be tied to a nearby tree).

The previous problem* is a typical combinatorial problem. Combinatorics is the science of counting. Counting of what? Of elements of (usually finite) sets. In the problem above one is asked to count how many elements are in the set of all seating arrangements of the characters which fulfil the requirements. The most often used combinatorial words are permutations and combinations. Permutations are rearrangements of a given set (more formally, permutations of a set S are one-to-one functions from S to S), while combinations are subsets of a given set. If you ask how many ways are there for five persons to form a line, you are asking how many permutations of a 5-element set there are (the answer is 120). If you ask how many ways are there to choose three of the five persons, you are asking how many 3-combinations of a 5-element set there are (the answer is 10). There are six permutations of any three objects, e.g. of three different-coloured cubes in a line (see the left picture of Figure 1 below), and there are three 1-combinations of the three cubes (three ways to choose one cube), three 2-combinations (three ways to choose two of the three cubes) and one 3-combination of the 3 cubes (there is only one way to choose all three of three cubes), see the right picture of Figure 1 below. As there is only one way to choose no object at all, there is 1 0-combination of any set.

                     
Figure 1. Six permutations of three cubes (left) and combinationsof the three cubes (right)

Since the sets considered above were small, the answers could be obtained or checked by enumerating all the possibilities. But what if we wanted to know in how many ways you can order 300 persons? Or in how many ways can you choose 50 of them? Generally, the number of the permutations of a set with n elements is n! (n factorials, i.e. the product of all integers from 1 up to n). The number of combinations with m elements from a n-element set is "n over m" (the binomial coefficient), and this is equal to the product of m integers starting with n and such that each next factor is 1 less than the previous (this is n⋅(n-1)⋅...⋅(n-m+1) ) divided by m!. So there are 300! (this is a number with 615 digits) ways to order 300 persons, and there are 300 over 50, i.e. 300⋅299⋅...⋅251/50! (this is a number with 58 digits) ways to choose 50 of them.

Other basic combinatorial counting principles are: the sum rule (if there are m ways to do one thing and n ways to do another and the two things cannot be done both at the same time, there are m + n ways to do one of the things), the product rule (if there are m ways to do one thing and n ways to do another, there are mn ways to do both things) and the pigeonhole principle (if n things are to be put into m boxes and m<n, then at least one box has to contain more than one thing).

---

Figure 2 (a). The sum and product rules: the objects to choose from.
             

If you are given three cylinders, four balls and five cubes and want to choose two objects of different kinds, in how many ways can you do it?
You can choose one cylinder and one ball in 3⋅4 ways, one cylinder and one cube in 3⋅5 ways and one ball and one cube in 4⋅5 ways (product rule).
Consequently you can choose two objects of different kinds in 3⋅4 + 3⋅5 + 4⋅5 = 47 ways (sum rule). The 47 choices are shown below:

                                                            
Figure 2 (b). The 47 possible choices of two objects of different kinds.

---

There are also other more advanced counting techniques. For example, the cardinalities of sequences of sets are often arranged into generating functions. Generating functions are formal power series with coefficients that contain information about a sequence. They are analysed with techniques of analysis. For example, the famous Fibonacci numbers are defined as the sequence of numbers formed from the starting numbers 0 and 1 in such a way that each next Fibonacci number is the sum of the previous two. Thus one obtains the Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The easiest way to obtain a formula for the n-th Fibonacci number fn is by using a generating function. We define it as the sum F(x) of all terms of the form fnxn, for n = 0, 1, 2, ... This sum does not converge for any x;this means that no matter what value one inserts for x, there is no reasonable way to assign a number to the infinite sum. Still, but by performing formal computations one can still obtain many insights in the sequence of coefficients. Since by definition f0 = 0, f1 = 1, fn = fn-1 + fn-2, the sum of all fnxn can be written as x plus the sum of all terms of the form (fn-1 + fn-2)xn for n>1. After rearrangements one gets that F(x) = x + xF(x) + x2F(x), so F(x) = x/(1 - x - x2). The last fraction can be written as (1/(1 - Φx) - 1/(1 - φx))/√5, where Φ = (1 + √5)/2 and φ = (1 - √5)/2. As 1/(1 - ax) can be written (in analysis only if |x|<|a|, because otherwise the series does not converge, but here one performs the expansion formally without considering the convergence) as the sum of all anxn for n from 0 to infinity, comparing the coefficients in the series on both sides of the equality, one gets the closed-form expression for Fibonacci numbers: fn = (Φn - φn)/√5.

Combinatorics is connected to many other areas of mathematics. The best known of these connections is the one to probability. Since for determining the classic a priori probability of an event you have to determine the number of the favorable cases divided by the number of all possible cases, it is usually necessary to employ combinatorial techniques for determining the two numbers to be divided. For example, say you want to know your chance of being dealt four of a kind, i.e. being dealt 4 cards of the same suit in the dealing of 5 cards from a pack of 52. There are 52 over 5 possible combinations that can be dealt (this is 2,598,960). To count the favorable cases, one has to choose one of the 13 suits for the four of a kind cards and one of the other 48 cards. This can be done in 13⋅48 = 624 ways. So the probability of drawing four of a kind is 624/2,598,960 = 0.024%.

Besides the classic (enumerative) combinatorics, many other branches of combinatorics exist. The study of designs (sets and their subsets arranged in a particular symmetric or nonsymmetric pattern) is also a part of combinatorics. Many recreational mathematical problems can be connected to the study of designs. For example, Sudoku problems are problems to find a specific kind of Latin squares. Latin squares are square arrangements of elements of a finite set, such that in each row (and column) all members of the set can be found and each element occurs exactly once in each row and each column. A Latin square formed of the three cubes considered in Figure 1 is shown on Figure 3 below. Partition theory studies problems connected to the partition problem: in how many ways can you represent a given positive integer as an (unordered) sum of positive integers? Order theory studies partially ordered sets (a partially ordered set is a set equipped with a partial order relation, and that is a relation ≤ with the properties that x≤x for all elements x, if x≤y and y≤x, then x=y and if x≤y≤z, then x≤z).

Figure 3. A Latin square formed from three cubes.

Graph theory is both a combinatorial and a topological discipline. It studies graphs, i.e. objects consisting of a set of vertices and a set of edges connecting these vertices. An example of a graph-theoretical problem is the graph-coloring problem: given a graph and a number of colours, can one assign a colour to each vertex in such a way that no two vertices connected by an edge have the same colour. For example, the graph on Figure 4 below can be coloured with three colours (as shown in the picture), but not with two colours. Graph theory has many applications, particularly in describing structures (like the hierarchical structure of a web-page), network analysis, chemistry and physics. Other branches of combinatorics are e.g. extremal combinatorics, geometric combinatorics, algebraic combinatorics...

Figure 4. A 3-colourable graph that is not 2-colourable.

 

* The introductory problem was given as an exam problem for the course in Combinatorics for second-year students of mathematics in Zagreb by Vedran Krcadinac and is not very easy to solve. It is understood that two seating arrangements that can be rotated into each other are considered the same. The solution is that the characters can be seated (in accordance with the given constraints) in 4515840 ways.