scroll identifier for mobile
main-content

This text provides a theoretical background for several topics in combinatorial mathematics, such as enumerative combinatorics (including partitions and Burnside's lemma), magic and Latin squares, graph theory, extremal combinatorics, mathematical games and elementary probability. A number of examples are given with explanations while the book also provides more than 300 exercises of different levels of difficulty that are arranged at the end of each chapter, and more than 130 additional challenging problems, including problems from mathematical olympiads. Solutions or hints to all exercises and problems are included. The book can be used by secondary school students preparing for mathematical competitions, by their instructors, and by undergraduate students. The book may also be useful for graduate students and for researchers that apply combinatorial methods in different areas.

### Chapter 1. Introduction

Abstract
Sets. In this section, we introduce necessary notions and notation. A set is one of the basic notions in mathematics and is determined by its elements. We shall use the following notation:

### Chapter 2. Arrangements, Permutations, and Combinations

Abstract
Solving combinatorial problems always requires knowledge of basic combinatorial configurations such as arrangements, permutations, and combinations. All of them are formed from the elements of the finite sets considered, for example, by taking sequences of the elements that belong to some sets or by taking subsets. In this chapter we shall define these combinatorial configurations and provide some examples and exercises.

### Chapter 3. Binomial and Multinomial Theorems

Abstract
The following equalities hold true for any real numbers x and y:

### Chapter 4. Inclusion-Exclusion Principle

Abstract
Counting the number of elements of the union of a few finite sets often appears as part of many combinatorial problems. Let us first consider two simple examples.

### Chapter 5. Generating Functions

Abstract
In this chapter we shall introduce one more method for solving combinatorial counting problems that is based on generating functions. We shall also give some examples of the generating functions of certain sequences of positive integers that appear in combinatorial problems.

### Chapter 6. Partitions

Abstract
In this chapter we shall consider the representation of a given positive integer as a sum of positive integers, as well as the representation of a given finite set in the form of the union of pairwise disjoint sets. These representations will be called the partitions of positive integers and the partitions of finite sets. We shall be interested in counting the number of partitions that satisfy some additional conditions.

### Chapter 7. Burnside’s Lemma

Abstract
The simple problem of coloring fields of a square 2 × 2 using three colors is considered in Example 2.​7.​11, and the number of nonequivalent colorings is determined by direct counting. At the beginning of this section we shall formulate two more similar problems.

### Chapter 8. Graph Theory: Part 1

Abstract
We shall start this chapter with two examples. The first one was formulated in 1736 by Leonard Euler. Now it is known as the Königsberg bridge problem and is usually considered to be the beginning of Graph Theory.

### Chapter 9. Graph Theory: Part 2

Abstract
In this section we shall focus on graphs without cycles. A tree is a connected graph that has no cycles. A forest is a disconnected graph that has no cycles. It is obvious that any connected component of a forest is a tree.

### Chapter 10. Existence of Combinatorial Configurations

Abstract
A square table n × n filled with the positive integers 1, 2, …, n 2 is called a magic square of order n if the sum of all numbers in each row, the sum of all numbers in each column, and the sum of all numbers in the two main diagonals are equal to each other. This constant sum is called a magic sum. The magic sum of a magic square of order n is
$$\displaystyle \frac 1n(1+2+\dots +n^2)=\frac 1n\cdot \frac 12n^2(n^2+1)=\frac {n(n^2+1)}{2}.$$

### Chapter 11. Mathematical Games

Abstract
The nim game is defined as follows. Suppose there are a few piles with a finite number of coins in each of them. Two players alternately take any number of coins from any single one of the piles. The winner is the player who removes the last coin (or the last few coins). Suppose now that two players, A and B, are playing the nim game, and that player A makes the first move. Is there a winning strategy for player A or B? If the answer to this question is yes, how should the player with a winning strategy play? Let us first consider some examples.

### Chapter 12. Elementary Probability

Abstract
In this chapter we shall introduce the basic notions of Probability Theory. In order to avoid a strong measure-theoretical background we shall concentrate on the so-called discrete probability spaces.

Abstract
13.1. Let p k(n) be the number of permutations of the set {1, 2, …, n} that have exactly k fixed points. Prove the following equalities:
(a) kp n(k) = np n−1(k − 1), where $$1\leqslant k\leqslant n$$;
(b) $$\sum \limits _{k=m}^n\displaystyle \frac {k!}{(k-m)!}p_n(k)=n!$$, where $$0\leqslant m\leqslant n$$.

### Chapter 14. Solutions

Abstract
Digit c 1 of the three-digit number c 1 c 2 c 3 can be chosen arbitrarily from the set {1, 2, …, 9}. There are 9 possible choices of digit c 2 such that c 2 ≠ c 1, and there are 8 possible choices of digit c 3 such that c 3 ≠ c 1 and c 3 ≠ c 2. By the product rule it follows that the number of positive integers with the given properties is equal to 9 ⋅ 9 ⋅ 8 = 648.