Elements of Combinatorics

$\binom {n}{k} = \binom {n}{n-k}$.

Find the sum $\binom {n}{0} + \ldots + \binom {n}{n}$.

Pascal's rule. $\binom {n+1}{k+1} = \binom {n}{k+1} + \binom {n}{k}$ if $0 \leqslant k \leqslant n-1$.

\begin{Bmatrix} \end{Bmatrix} n+1 \\ k+1 \end{Bmatrix} = (k+1)\begin{Bmatrix} \end{Bmatrix} n \\ k+1 \end{Bmatrix} + \begin{Bmatrix} \end{Bmatrix} n \\ k \end{Bmatrix}. Here \begin{Bmatrix} \end{Bmatrix} n \\ k \end{Bmatrix} is the number of partitions of an $n$-element set into $k$ parts (i.e. nonempty subsets); partitions are considered unordered, i.e. the partition of the set $\{ 1,2,3\}$ into the parts $\{ 1,2\}$ and $\{ 3\}$ and the partition of the same set into the parts $\{ 3\}$ and $\{ 1,2\}$ are considered the same. Cf. Problem 1.4.7(5).

How many subsets of the set $\mathscr {R}_{11}$ contain no two consecutive numbers?

The same for three consecutive numbers.

$\binom {n}{k} = \dfrac {n!}{k!(n-k)!} = \dfrac {n(n-1)\ldots (n-k+1)}{k!}$.

The binomial theorem. $(a+b)^n = \displaystyle \sum_{j=0}^{n}\binom {n}{j}a^jb^{n-j}$.

$\binom {n}{0} - \binom {n}{1} + \ldots + (-1)^n\binom {n}{n}$;

$\binom {n}{0} + \dfrac {1}{2}\binom {n}{1} + \dfrac {1}{3}\binom {n}{2} + \ldots + \dfrac {1}{n+1}\binom {n}{n}$;

$\binom {n}{1} + 2\binom {n}{2} + 3\binom {n}{3} + \ldots + n\binom {n}{n}$;

$\binom {n}{k} + \binom {n+1}{k+1} + \ldots + \binom {n+m}{k+m}$;

$\binom {n}{0}^2 + \ldots + \binom {n}{n}^2$;

$\binom {n}{0}\binom {m}{k} + \binom {n}{1}\binom {m}{k-1} + \ldots + \binom {n}{k}\binom {m}{0}$;

$\binom {2n}{0} - \binom {2n-1}{1} + \binom {2n-2}{2} - \ldots + (-1)^n\binom {n}{n}$;

$\binom {2n}{n} + 2\binom {2n-1}{n} + 4\binom {2n-2}{n} + \ldots + 2^n\binom {n}{n}$.

Find $\displaystyle \sum_{k \geqslant 0}\binom {n}{2k}$.

Find $\displaystyle \sum_{k \geqslant 0}\binom {n}{4k}$.

Find $\displaystyle \sum_{k \geqslant 0}\binom {n}{3k}$.

Find the number of integers not exceeding 1001 and not divisible by any of the numbers 7, 11, 13.

Find $\varphi (1), \varphi (p), \varphi (p^2), \varphi (p^\alpha )$, where $p$ is a prime number and $\alpha > 2$.

$\varphi (n) = n\left(1 - \dfrac {1}{p_1}\right)\ldots \left(1-\dfrac {1}{p_s}\right)$, where $n = p_1^{\alpha_1}\cdot \ldots \cdot p_s^{\alpha_s}$ is the canonical prime factorization of $n$.

On the floor of a room of area $24\, \text{m}^2$ there are three carpets (of arbitrary shape), each of area $12\, \text{m}^2$. Then the area of the intersection of some two carpets is at least $4\, \text{m}^2$.

There are five patches (of arbitrary shape) on a caftan. The area of each of them is greater than half the area of the caftan. Then the area of the common part of some two patches is greater than one fifth of the area of the caftan.

Suppose the number $\alpha_{|S|} := \left|\bigcap_{j\in S}A_j\right|$ depends only on the size $|S|$ of the index set $S \subset \mathscr {R}_n$, and not on the set itself. Then

Let $M_k := \displaystyle \sum_{S\in \binom {\mathscr {R}_n}{k}}\left|\bigcap_{j\in S}A_j\right|$. In particular, $M_0 := |U|$. Then

Bonferroni inequalities. For any $s$, $s < \dfrac {n}{2}$,

In how many ways can they be rearranged so that no book remains in its place?

The number of permutations of the books in which exactly 4 books remain in place is greater than 50000.

In how many ways can 20 tourists be accommodated in 5 distinct cabins so that no cabin is empty?

How many distinct surjections $f: \mathscr {R}_k \to \mathscr {R}_n$ are there?

If the sum of $n$ real numbers equals $S$, then there is a summand not greater than $S/n$, and also a summand not less than $S/n$.

If the sum of $n$ integers is greater than $kn$ for some integer $k$, then there is a summand not less than $k+1$.

If the sum of $n$ integers is less than $kn$ for some integer $k$, then there is a summand not greater than $k-1$.

of all 9 colors?

of 7 colors?

Among the 7-digit numbers ending in 3 fives, there are at least 1200 numbers having the same remainder upon division by 7.

For each 4-digit number, the sum of the digits of its square was computed. Prove that there are at least 1200 numbers for which the computed sums give the same remainder upon division by 7.

Among the numbers written using only ones, there is a number divisible by 1997.

Suppose $n$ integers are written in a row. Prove that one can select one or several consecutive ones among them whose sum is a multiple of $n$.

Among any $n$ real numbers there are two whose fractional parts differ by at most $\dfrac {1}{n-1}$.

Integers are placed in a $10\times 10$ table, and any two numbers in cells adjacent by a side differ by at most 5. Prove that among these numbers there are two equal ones.

For any positive integer $N$ there exist coprime $p,q\in \mathbb {Z}$ such that $0 < q \leqslant N$ and

There exist infinitely many pairs of coprime numbers $p,q\in \mathbb {Z}$ for which

several apples so that the weights on the plates differ by less than 1 g.

the same number of apples on each plate so that the weights on the plates differ by less than 2 g.

$\left|\sum_{k=1}^{n}\varepsilon_kv_k\right| \leqslant \sqrt{n}$,

$\left|\sum_{k=1}^{n}\varepsilon_kv_k\right| \geqslant \sqrt{n}$.

What is the least sequence length for which the encoding can be made unambiguous?

If an error in at most one digit is possible when a message is received, i.e., if the codes of different letters must differ in at least three digits, then 8 digits are not enough.

If an error in at most two digits is possible, then 10 digits are not enough.

Find the least number of digits sufficient for the encoding from part (2).

For fixed $n$, the number $\binom {n}{k}$ is maximal at $k = \left[\dfrac {n}{2}\right]$.

Best in their own ways. $k$ schoolchildren took part in a mathematical olympiad. It turned out that for any two schoolchildren $A$ and $B$ there was a problem that $A$ solved and $B$ did not solve, and a problem that $B$ solved but $A$ did not solve. What is the least possible number of problems under this condition? In other words, find the least possible $n$ for which there exists a family of $k$ subsets of an $n$-element set such that no subset of the family is (properly) contained in another.

Every linear subspace contains the zero vector $(0,\ldots ,0)$.

The number of elements in any linear subspace is a power of two.

Find $\begin{vmatrix} 2 \\ k \end{vmatrix}$ for $k=0,1,2$.

Find $\begin{vmatrix} 3 \\ k \end{vmatrix}$ for $k=0,1,2,3$.

$\begin{vmatrix} n \\ 0 \end{vmatrix} = \begin{vmatrix} n \\ n \end{vmatrix} = 1$, $\begin{vmatrix} n \\ 1 \end{vmatrix} = \begin{vmatrix} n \\ n-1 \end{vmatrix} = 2^n-1$.

$\begin{vmatrix} n \\ k \end{vmatrix} = \begin{vmatrix} n \\ n-k \end{vmatrix}$.

$\begin{vmatrix} n+1 \\ k+1 \end{vmatrix} = \begin{vmatrix} n \\ k+1 \end{vmatrix} + 2^{n-k}\begin{vmatrix} n \\ k \end{vmatrix}$.

Find $\begin{vmatrix} n \\ 2 \end{vmatrix}$.

Find $\begin{vmatrix} n \\ k \end{vmatrix}$.

$\displaystyle \sum_{d \mid n}\mu (d) = \begin{cases} 1, & n=1; \\ 0, & n \neq 1. \end{cases}$

Find the sum of the values of the Möbius function over exactly those divisors of $n$ whose canonical factorization contains an even number of prime factors.

The Möbius inversion formula. Let $f: \mathbb {N} \to \mathbb {R}$ be an arbitrary function, and let $g(n) = \displaystyle \sum_{d \mid n}f(d)$. Then the following formula holds:

Find the sum $\displaystyle \sum_{d \mid n}\varphi (d)$.

$\displaystyle \sum_{d \mid n}\frac{\mu (d)}{d} = \left(1-\frac{1}{p_1}\right)\ldots \left(1-\frac{1}{p_s}\right)$.

Find $T_r(n)$ for $n = 3,4,5,6,9$.

$2^{2^n-n-1} < T_2(2^n) < 2^{2^n-n}$.

The period of a sequence divides its length.

If $d$ divides $n$, then the number of sequences of length $n$ and period $d$ equals the number of sequences of length $d$ and period $d$.

Find $\displaystyle \sum_{d \mid n}M_r(d)$.

Express $T_r(n)$ in terms of all $M_r(d)$, where $d \mid n$.

$T_r(n) = \displaystyle \sum_{l \mid n}\frac{1}{l}\sum_{d \mid l}\mu (d)r^{l/d}$.

$T_r(n) = \dfrac {1}{n}\displaystyle \sum_{d \mid n}\varphi (d)r^{n/d}$. (A simpler proof of this formula is given in Sec.1.9, Problem 1.9.4(1).)

color $s$ occurs $n_s$ times for each $s = 1, \ldots , r$ (here a formula with summation over divisors, analogous to 1.5.5(3), is accepted as an answer);

exactly 4 of the $r=5$ given colors are present.

21 nine-element subsets of a 30-element set are given. Then some element of the 30-element set is contained in at least seven of the given subsets.

A committee met 40 times. Exactly 10 people were present at each meeting, and no two of them were together more than once. Then the committee has at least 60 members.

In a company, any two people who are acquainted with each other have exactly 5 common acquaintances (other than themselves). Then the number of pairs of mutually acquainted people in the company is divisible by 3.

Denote by $P_n(k)$ the number of permutations of the set of positive integers from 1 to $n$ that leave exactly $k$ numbers in place. Then $\displaystyle \sum_{k=0}^{n}k\cdot P_n(k) = n!$.

If $k \geqslant l$ and every $l$-element subset of the $n$-element set is contained in some subset from $\mathscr {F}$, then $|\mathscr {F}| \geqslant \dbinom {n}{l}\Big/\dbinom {k}{l}$.

The number of $(k-1)$-element subsets of the $n$-element set that are entirely contained in at least one of the subsets of the family $\mathscr {F}$ is at least $\dfrac {k|\mathscr {F}|}{n-k+1}$.

If for some even $n$

then in an $n$-element set one can find $l$ subsets of $k$ elements each such that for any coloring of the elements of this set in two colors at least one of these $l$ subsets is monochromatic.

There exists $c>0$ such that for any $k$ there exist $k$-element subsets of some set, at most $ck^22^k$ in number, such that for any coloring of the elements of this set in two colors one of these subsets is monochromatic.

$(12)\circ (13)$;

$(12)\circ (23)$;

$(23)\circ (12)$;

$(123)\circ (132)$;

$(12)\circ (13)\circ (12)$;

$(12345)\circ (12)$;

$(12345)\circ (56789)$.

$\langle 2,3 \rangle$;

$\langle 3,3 \rangle$;

$\langle 1,2,3,4 \rangle$.

disjoint cycles;

transpositions, i.e., permutations each of which swaps some two elements and leaves the rest in place (in other words, cycles of length 2);

transpositions $(1i)$, $i=2,3,\ldots ,n$.

Permutations $a$ and $b$ are conjugate if and only if their types are the same.

Let $a$ and $x$ be arbitrary permutations of an $n$-element set. Then

In other words, the cycle decomposition of the permutation $xax^{-1}$ is obtained from the cycle decomposition of the permutation $a$ by replacing each element with its $x$-image: if $a = \displaystyle \prod_{j=1}^{q}(i_{j1},i_{j2},\ldots ,i_{js_j})$, then

Find $gf^{-1}g^{-1}f$ for $f := (1,2,\ldots ,N)$ and $g := (N,N+1,\ldots ,L)$.

Can every permutation be represented as a composition of several cycles of length 3?

Can every permutation be represented as a composition of an even number of transpositions?

The 15 puzzle. A square box of size $4\times 4$ holds 15 square tiles of size $1\times 1$ numbered $1,2,\ldots ,15$, and one place is left empty. Initially the tiles are arranged as in the figure on the right. Is it possible, by successively sliding tiles into the empty place, to obtain the arrangement of tiles in the figure on the left?

on the order in which the elements of the cycle follow one another?

on $n$?

The composition of an even (odd) permutation and a transposition is odd (even).

How can one determine the parity of a composition of permutations, knowing the parities of the factors?

The permutation can be represented as a composition of an even number of transpositions.

Every representation of the permutation as a composition of transpositions contains an even number of them.

The permutation can be represented as a composition of several cycles of length 3.

Which permutations of an $n$-element set are more numerous: even or odd ones?

What is the minimal number of transpositions into which a permutation of an $n$-element set consisting of $k$ disjoint cycles of length greater than 1 can be decomposed?

The set of all even permutations of a finite set is generated by any pair of cycles (each of length at least 2) that have exactly one common element and contain all elements of the set.

If $nk$ is even, $n>1$, $k>1$, then the cycles $(1\ldots n)$ and $(n \ldots n+k-1)$ generate all permutations of the set $\mathscr {R}_{n+k-1}$.

If $nk$ is odd, $n>1$, $k>1$, then the cycles $(1\ldots n)$ and $(n\ldots n+k-1)$ generate all even permutations of the set $\mathscr {R}_{n+k-1}$ and only them.

colorings of the unlabeled faces of a cube in red and gray are there?

distinct (i.e., non-isomorphic) undirected graphs with 4 unlabeled vertices are there?

colorings of the unlabeled vertices of a regular tetrahedron in $r$ colors are there? Here colorings that can be carried into each other by a motion of space (not necessarily orientation-preserving) are considered the same.

colorings of the vertices of the complete graph on 4 unlabeled vertices in $r$ colors are there? Here colorings that can be carried into each other by a permutation of the vertices (i.e., an automorphism) of this graph are considered the same.

$n=5$;

$n=4$;

$n=6$.

colorings of a carousel of $n$ cars in $r$ colors (see the formalization and another solution in Sec.1.5, Problem 1.5.5);

$r$-colored necklaces of $n=2k+1$ beads (necklaces are considered the same if they can be carried into each other either by a rotation about the center of the necklace or by an axial symmetry of the necklace);

colorings of the unlabeled faces of a cube in $r$ colors;

colorings of the unlabeled vertices of a cube in $r$ colors;

colorings of the unlabeled vertices of the graph $K_{3,3}$ (Sec.2.1) in $r$ colors. Colorings are considered the same if they can be carried into each other by an automorphism of this graph.