Элементы комбинаторики

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

Найдите сумму $\binom {n}{0} + \ldots + \binom {n}{n}$.

Правило Паскаля. $\binom {n+1}{k+1} = \binom {n}{k+1} + \binom {n}{k}$, если $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}. Здесь \begin{Bmatrix} \end{Bmatrix} n \\ k \end{Bmatrix} — количество разбиений $n$-элементного множества на $k$ частей (т.е. непустых подмножеств); разбиения считаются неупорядоченными, т.е. разбиение множества $\{ 1,2,3\}$ на части $\{ 1,2\}$ и $\{ 3\}$ и разбиение того же множества на части $\{ 3\}$ и $\{ 1,2\}$ считаются одинаковыми. Ср. с задачей 1.4.7(5).

Числа \begin{Bmatrix} \end{Bmatrix} n \\ k \end{Bmatrix} называются числами Стирлинга второго рода.

Во скольких подмножествах множества $\mathscr {R}_{11}$ не найдётся двух подряд идущих чисел?

То же для трёх подряд идущих чисел.

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

Бином Ньютона. $(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}$.

Найдите $\displaystyle \sum_{k \geqslant 0}\binom {n}{2k}$.

Найдите $\displaystyle \sum_{k \geqslant 0}\binom {n}{4k}$.

Найдите $\displaystyle \sum_{k \geqslant 0}\binom {n}{3k}$.

Найдите количество чисел, не превосходящих 1001 и не делящихся ни на одно из чисел 7, 11, 13.

Найдите $\varphi (1), \varphi (p), \varphi (p^2), \varphi (p^\alpha )$, где $p$ — простое число, $\alpha > 2$.

$\varphi (n) = n\left(1 - \dfrac {1}{p_1}\right)\ldots \left(1-\dfrac {1}{p_s}\right)$, где $n = p_1^{\alpha_1}\cdot \ldots \cdot p_s^{\alpha_s}$ — каноническое разложение числа $n$.

На полу комнаты площадью $24\, \text{м}^2$ расположены три ковра (произвольной формы) площади $12\, \text{м}^2$ каждый. Тогда площадь пересечения некоторых двух ковров не меньше $4\, \text{м}^2$.

На кафтане расположено пять заплат (произвольной формы). Площадь каждой из них больше половины площади кафтана. Тогда площадь общей части некоторых двух заплат больше одной пятой площади кафтана.

Пусть число $\alpha_{|S|} := \left|\bigcap_{j\in S}A_j\right|$ зависит только от размера $|S|$ набора $S \subset \mathscr {R}_n$ индексов, а не от самого набора. Тогда

Обозначим $M_k := \displaystyle \sum_{S\in \binom {\mathscr {R}_n}{k}}\left|\bigcap_{j\in S}A_j\right|$. В частности, $M_0 := |U|$. Тогда

Неравенства Бонферрони. Для любого $s$, $s < \dfrac {n}{2}$,

Сколькими способами их можно переставить так, чтобы ни одна книга не осталась на своем месте?

Количество таких перестановок книг, при которых на месте остаётся ровно 4 книги, больше 50000.

Сколькими способами можно расселить 20 туристов по 5 различным домикам, чтобы ни один домик не оказался пустым?

Сколько существует различных сюръекций $f: \mathscr {R}_k \to \mathscr {R}_n$?

Если сумма $n$ действительных чисел равна $S$, то найдётся слагаемое, не большее $S/n$, а также слагаемое, не меньшее $S/n$.

Если сумма $n$ целых чисел больше $kn$ для некоторого целого $k$, то найдётся слагаемое, не меньшее $k+1$.

Если сумма $n$ целых чисел меньше $kn$ для некоторого целого $k$, то найдётся слагаемое, не большее $k-1$.

всех 9 цветов?

7 цветов?

Среди 7-значных чисел, заканчивающихся на 3 пятерки, существует не менее 1200 чисел, имеющих один и тот же остаток от деления на 7.

Для каждого 4-значного числа посчитали сумму цифр его квадрата. Докажите, что существует не менее 1200 чисел, для которых посчитанные суммы будут давать одинаковый остаток при делении на 7.

Среди чисел, записываемых только единицами, есть число, которое делится на 1997.

В строку записаны $n$ целых чисел. Докажите, что из них можно выделить одно или несколько подряд идущих с суммой, кратной $n$.

Среди любых $n$ действительных чисел найдутся два, дробные части которых различаются не более чем на $\dfrac {1}{n-1}$.

В таблице $10\times 10$ расставлены целые числа, причем любые два числа в соседних по стороне клетках отличаются не более чем на 5. Докажите, что среди этих чисел найдутся два равных.

Для произвольного натурального $N$ найдутся такие взаимно простые $p,q\in \mathbb {Z}$, что $0 < q \leqslant N$ и

Существует бесконечно много пар взаимно простых чисел $p,q\in \mathbb {Z}$, для которых

несколько яблок так, чтобы веса в тарелках отличались меньше чем на 1 г.

по одинаковому количеству яблок так, чтобы веса в тарелках отличались меньше чем на 2 г.

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

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

При каком наименьшей длине последовательности кодирование можно сделать однозначным?

Если при получении сообщения возможна ошибка в не более чем одном разряде, т.е. если коды различных букв должны отличаться по крайней мере в трёх разрядах, то 8 разрядов не хватит.

Если возможна ошибка в не более чем двух разрядах, то 10 разрядов не хватит.

Найдите наименьшее число разрядов, достаточное для кодирования из п.(2).

При фиксированном $n$ число $\binom {n}{k}$ максимально при $k = \left[\dfrac {n}{2}\right]$.

Best in their own ways. В математической олимпиаде участвовало $k$ школьников. Выяснилось, что для любых двух школьников $A$ и $B$ нашлась задача, которую решил $A$ и не решил $B$, и задача, которую решил $B$, но не решил $A$. Какое наименьшее возможное количество задач могло быть при этом условии? Иными словами, найдите наименьшее возможное $n$, для которого найдётся такое семейство из $k$ подмножеств $n$-элементного множества, что ни одно из подмножеств семейства не содержится (собственно) в другом.

Любое линейное подпространство содержит нулевой набор $(0,\ldots ,0)$.

Число элементов в любом линейном подпространстве является степенью двойки.

Найдите $\begin{vmatrix} 2 \\ k \end{vmatrix}$ для $k=0,1,2$.

Найдите $\begin{vmatrix} 3 \\ k \end{vmatrix}$ для $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}$.

Найдите $\begin{vmatrix} n \\ 2 \end{vmatrix}$.

Найдите $\begin{vmatrix} n \\ k \end{vmatrix}$.

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

Найдите сумму значений функции Мёбиуса по тем и только тем делителям числа $n$, в каноническое разложение которых входит чётное количество простых множителей.

Формула обращения Мёбиуса. Пусть $f: \mathbb {N} \to \mathbb {R}$ — произвольная функция, $g(n) = \displaystyle \sum_{d \mid n}f(d)$. Тогда справедлива формула

Найдите сумму $\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)$.

Найдите $T_r(n)$ при $n = 3,4,5,6,9$.

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

Период последовательности делит её длину.

Если $d$ делит $n$, то количество последовательностей длины $n$ и периода $d$ равно количеству последовательностей длины $d$ и периода $d$.

Найдите $\displaystyle \sum_{d \mid n}M_r(d)$.

Выразите $T_r(n)$ через все $M_r(d)$, где $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}$. (Более простой способ доказательства этой формулы приведён в п.1.9, задача 1.9.4(1).)

цвет $s$ встречается $n_s$ раз для каждого $s = 1, \ldots , r$ (здесь в качестве ответа принимается формула с суммированием по делителям, аналогичная 1.5.5(3));

присутствует ровно 4 цвета из $r=5$ данных.

Дано 21 девятиэлементное подмножество 30-элементного множества. Тогда какой-то элемент 30-элементного множества содержится по крайней мере в семи данных подмножествах.

Комиссия собиралась 40 раз. На каждом заседании было ровно 10 человек, любые два не были вместе больше одного раза. Тогда в комиссии хотя бы 60 человек.

В компании у любых двух знакомых друг с другом человек есть ровно 5 общих знакомых (кроме них самих). Тогда количество пар знакомых между собой людей в компании делится на 3.

Обозначим через $P_n(k)$ число перестановок множества натуральных чисел от 1 до $n$, оставляющих ровно $k$ чисел на своём месте. Тогда $\displaystyle \sum_{k=0}^{n}k\cdot P_n(k) = n!$.

Если $k \geqslant l$ и каждое $l$-элементное подмножество $n$-элементного множества содержится в некотором подмножестве из $\mathscr {F}$, то $|\mathscr {F}| \geqslant \dbinom {n}{l}\Big/\dbinom {k}{l}$.

Количество $(k-1)$-элементных подмножеств $n$-элементного множества, целиком содержащихся хотя бы в одном из подмножеств семейства $\mathscr {F}$, не меньше $\dfrac {k|\mathscr {F}|}{n-k+1}$.

Если для некоторого чётного $n$

то в $n$-элементном множестве найдётся $l$ таких $k$-элементных подмножеств, что при любой раскраске элементов этого множества в два цвета хотя бы одно из этих $l$ подмножеств одноцветно.

Существует такое $c>0$, что для любого $k$ существует не более чем $ck^22^k$ таких $k$-элементных подмножеств некоторого множества, что при любой раскраске элементов этого множества в два цвета одно из этих подмножеств одноцветно.

$(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$.

непересекающихся циклов;

транспозиций, т.е. перестановок, каждая из которых меняет местами некоторые два элемента, а остальные оставляет на месте (иными словами, циклов длины 2);

транспозиций $(1i)$, $i=2,3,\ldots ,n$.

Перестановки $a$ и $b$ сопряжены тогда и только тогда, когда их типы одинаковы.

Пусть $a$ и $x$ — произвольные перестановки $n$-элементного множества. Тогда

Иными словами, циклическое разложение перестановки $xax^{-1}$ получается из циклического разложения перестановки $a$ заменой каждого элемента на его $x$-образ: если $a = \displaystyle \prod_{j=1}^{q}(i_{j1},i_{j2},\ldots ,i_{js_j})$, то

Найдите $gf^{-1}g^{-1}f$ для $f := (1,2,\ldots ,N)$ и $g := (N,N+1,\ldots ,L)$.

Любую ли перестановку можно представить в виде композиции нескольких циклов длины 3?

Любую ли перестановку можно представить в виде композиции чётного числа транспозиций?

Игра в 15. В квадратной коробочке размера $4\times 4$ размещены 15 квадратных фишек размера $1\times 1$ с номерами $1,2,\ldots ,15$, а одно место осталось свободным. Первоначально фишки расставлены так, как на рисунке справа. Можно ли, последовательно сдвигая фишки на свободное место, получить расстановку фишек на рисунке слева?

от порядка следования элементов цикла?

от $n$?

Композиция чётной (нечётной) перестановки и транспозиции нечётна (чётна).

Как определить чётность композиции перестановок, зная чётность сомножителей?

Перестановку можно представить в виде композиции чётного числа транспозиций.

Любое представление перестановки в виде композиции транспозиций содержит чётное их число.

Перестановку можно представить в виде композиции нескольких циклов длины 3.

Каких перестановок $n$-элементного множества больше: чётных или нечётных?

В какое минимальное количество транспозиций раскладывается перестановка $n$-элементного множества, состоящая из $k$ непересекающихся циклов длины больше 1?

Множество всех чётных перестановок конечного множества порождается любой парой циклов (длины хотя бы 2 каждый), имеющих ровно один общий элемент и содержащих все элементы множества.

Если $nk$ чётно, $n>1$, $k>1$, то циклами $(1\ldots n)$ и $(n \ldots n+k-1)$ порождаются все перестановки множества $\mathscr {R}_{n+k-1}$.

Если $nk$ нечётно, $n>1$, $k>1$, то циклами $(1\ldots n)$ и $(n\ldots n+k-1)$ порождаются все чётные перестановки множества $\mathscr {R}_{n+k-1}$ и только они.

раскрасок незанумерованных граней куба в красный и серый цвета?

различных (т.е. неизоморфных) неориентированных графов с 4 незанумерованными вершинами?

раскрасок в $r$ цветов незанумерованных вершин правильного тетраэдра? Здесь раскраски, совмещающиеся движением пространства (не обязательно сохраняющим ориентацию), считаются одинаковыми.

раскрасок вершин полного графа на 4 незанумерованных вершинах в $r$ цветов? Здесь раскраски, совмещающиеся перестановкой вершин (т.е. автоморфизмом) этого графа, считаются одинаковыми.

$n=5$;

$n=4$;

$n=6$.

раскрасок карусели из $n$ вагончиков в $r$ цветов (см. формализацию и другое решение в п.1.5, задача 1.5.5);

$r$-цветных ожерелий из $n=2k+1$ бусин (ожерелья считаются одинаковыми, если они совмещаются либо поворотом вокруг центра ожерелья, либо осевой симметрией ожерелья);

раскрасок незанумерованных граней куба в $r$ цветов;

раскрасок незанумерованных вершин куба в $r$ цветов;

раскрасок незанумерованных вершин графа $K_{3,3}$ (п.2.1) в $r$ цветов. Раскраски считаются одинаковыми, если они совмещаются автоморфизмом этого графа.

Для каждого вращения $s$ куба найдите количество $\mathrm{fix}(s)$ замороженных раскрасок, переходящих в себя при вращении $s$.