• Закончил Матфак ВШЭ
• Работаю в 179 школе
• Преподаю математику
  школьникам, студентам и
  взрослым, организую
  математические события
• Веду телеграм-канал
  Кроссворд Тьюринга
  @turings_crossword
• Телеграм @d1_d57

В этих двух комбинаторных задачах одинаковый ответ:

• сколько в сумме сторон и диагоналей у 15-угольника;
• сколькими способами можно выбрать две батарейки из 15 имеющихся

Это следует из того, что существует взаимно однозначное соответствие между отрезками и парами батареек

Отрезок ↔ пара вершин ↔ пара батареек

Один из важных комбинаторных принципов — если между элементами множеств установлено взаимно однозначное соответствие, в них равное число элементов

Рассмотрим тождества о биномиальных коэффициентах

$\binom nk=\binom n{n-k}$$\sum_{k=0}^{n}\binom nk=2^{\,n}$$k\binom nk=n\binom{n-1}{k-1}$$\binom nk=\binom{n-1}{k-1}+\binom{n-1}k$$\binom{m+n}k=\sum_{j=0}^{k}\binom mj\binom n{k-j}$$\sum_{k=0}^{n}(-1)^k\binom nk=0$ при $n\ge1$$\sum_{0\le l\le k\le n}\binom nk\binom kl=3^{\,n}$$\sum_{k\ge0}\binom{n+1-k}{k}=\mathrm{Fib}_{n+2}$

Доказательства бывают разные: через формулу биномиальных коэффициентов, индукцию, бином Ньютона. Обычно больше всего ценятся комбинаторные доказательства

Комбинаторным доказательством называется доказательство, в котором устанавливается взаимно однозначное соответствие между множествами $X$ и $Y\text{,}$ отвечающими левой и правой частям тождества

$\binom nk=\binom n{n-k}$$\sum_k\binom nk=$$2^{\,n}$$\sum_{0\le l\le k\le n}\binom nk\binom kl=$$3^{\,n}$

Описанные операции сохраняются при переименовании элементов

Свойства биекции $S\mapsto U\setminus S$

• переименование $\sigma\colon U\to V$ переводит дополнение в дополнение;
• переименовать и взять дополнение — то же самое, что взять дополнение и переименовать

Давайте попробуем понять, какие свойства структур мы видели в предыдущих примерах

Комбинаторный вид $F\text{:}$

• конечному множеству $U$ отвечает множество $F(U)\text{;}$
• биекции $\sigma\colon U\to V$ вид $F$ сопоставляет биекцию $F[\sigma]\colon F(U)\to F(V)\text{;}$
• $F[\tau\circ\sigma]=F[\tau]\circ F[\sigma]$

$F$ — это множество структур на $U$ специального вида; если $\sigma$ — переименование элементов $U\text{,}$ то структуры тоже можно переименовать

Это свойство называется функториальностью

Примеры видов

• линейные порядки;
• циклические порядки;
• перестановки;
• беспорядки;
• инволюции (перестановки с $\pi^2=\mathrm{id}$);
• подмножества $E(U)$ и $k\text{-}$подмножества $E_k(U)\text{;}$
• разбиения на блоки;
• графы, деревья и корневые деревья с вершинами $U\text{;}$
• бывают инъекции, бывают ещё сюръекции — это и то, и то виды

При переименовании элементов $U$ переименовываются и объекты каждого из этих множеств

Естественный изоморфизм $\varphi\colon F\to G$ — семейство биекций $\varphi_U\colon F(U)\to G(U)\text{,}$ согласованное со всякой биекцией $\sigma\colon U\to V\text{:}$

$\displaystyle \varphi_V\circ F[\sigma]=G[\sigma]\circ\varphi_U$

Доказательство тождества $\lvert F(U)\rvert=\lvert G(U)\rvert$ красиво, когда предъявлено такое семейство, а не отдельная биекция при каждом $U$

Какие из выписанных в начале тождеств — изоморфизмы видов?

$\displaystyle \sum_{k=0}^{n}(-1)^k\binom nk=0\qquad (n\ge1)$

Число чётных подмножеств такое же, как число нечётных: $\lvert E^{+}\rvert=\lvert E^{-}\rvert$

Есть биекция $S\mapsto S\,\triangle\,\{x_0\}\text{:}$ она добавляет или убирает $x_0$

Но это не изоморфизм видов: переименование не сохраняет $x_0$

Упражнение

$E^{+}$ и $E^{-}$

не изоморфны при чётном числе элементов;изоморфны при нечётном

Как вывести из изоморфизма видов тождество Паскаля?

$\displaystyle \binom nk=\binom{n-1}{k-1}+\binom{n-1}k$

Чтобы придумать комбинаторные виды, для которых число элементов равно $\binom{n-1}{k-1}\text{,}$ $\binom{n-1}k\text{,}$ добавим дополнительную структуру:

отмеченное множество $(U,\ast)$ — множество и фиксированный элемент;биекция отмеченных множеств $U_\ast\to V_\ast$ — биекция множеств, сохраняющая отмеченный элемент;отмеченный вид — функтор из отмеченных множеств в множества

Отображение $S\mapsto S\,\triangle\,\ast$ задаёт изоморфизм отмеченных видов $E^{+}\text{,}$ $E^{-}$

Рассмотрим отмеченный вид $k\text{-}$подмножеств, содержащих и не содержащих отмеченную точку, — это сразу даёт тождество Паскаля

Как доказать тождество Вандермонда $\binom{m+n}k=\sum_r\binom mr\binom n{k-r}$ комбинаторно?

Введём дополнительную структуру:

покрашенное множество $(M,N)$ — пара множеств;биекция покрашенных множеств — биекция множеств, сохраняющая цвет;покрашенный вид — функтор из покрашенных множеств в множества

Вид подмножеств объединения $M$ и $N$ даёт тождество Вандермонда

Категория $\mathcal C$ состоит из:

• класса объектов $\mathrm{Ob}\,\mathcal C\text{;}$
• множества морфизмов $\mathcal C(A,B)$ между парой объектов $A$ и $B$ из $\mathrm{Ob}\,\mathcal C\text{;}$
• композиции $\circ\colon\mathcal C(B,C)\times\mathcal C(A,B)\to\mathcal C(A,C)$ и единицы $1_A\in\mathcal C(A,A)\text{,}$ для которых выполняются аксиомы

$h\circ(g\circ f)=(h\circ g)\circ f\qquad 1_B\circ f=f=f\circ 1_A$

Функтор $F\colon\mathcal C\to\mathcal D$ состоит из:

отображения объектов $\mathrm{Ob}\,\mathcal C\to\mathrm{Ob}\,\mathcal D\text{;}$отображений морфизмов $\mathcal C(A,B)\to\mathcal D(FA,FB)\text{,}$ для которых $F(g\circ f)=Fg\circ Ff$ и $F1_A=1_{FA}$

Конечные множества и биекции образуют категорию; отмеченные и покрашенные множества — тоже. Комбинаторный вид — функтор из этих категорий в категорию множеств

• понятие комбинаторного доказательства получило точную формулировку — изоморфизм комбинаторных видов;
• при этом понятие комбинаторного вида пришлось трактовать в разных ситуациях по-разному;
• тождества можно искать, не только проверять: изоморфизм видов — это такое сильное условие, которое помогает находить объект;
• невозможность и единственность стали теоремами; дальше — классификация самих видов