Сочетания, разбиения, включения-исключения

Давно ничего не писал, но вот выкладываю сразу аж три параграфа одним скопом. Тут материал довольно прикладной, но одновременно с тем его редко рассматривают на инженерных специальностях, поэтому, думаю, нематематикам будет интересно. Как всегда призываю читать pdf и помогать на Гитхабе.

В pdf-ке так же появился параграф про формализм, но довольно сырой, был ещё немного переработан параграф про интуицию относительно теорий. Всё это пока довольно сыро, я делал это довольно в авральном режиме для того, чтобы курс на Hexlet был более полноценен, так что праки в той части, думаю, ещё будут. Пока же просто уже затрахался править главу логики, вероятно, в дальнейшем к ней ещё вернусь, но только когда закончу третью главу (это, по идее, уже скоро: осталось порядка пяти параграфов).

Сочетания

«-cочетание» — это просто другое название для термина «-элементное подмножество», которое по историческим причинам (хотя многие считают, что так удобнее) принято в комбинаторике. Нас будет интересовать количество -сочетаний взятых из множества .

Определение. Биномиальным коэффициентом называется число сочетаний из по .

Вместо обозначения в российской и французской литературе исторически чаще используется обозначение , однако оно кажется мне менее удобным в случаях если вместо величин и используются какие-то длинные выражения. По этой причине мы будем придерживаться общемирового обозначения.

Значения и очевидны. Так же удобно полагать, что (пустое множество всего одно, соответственно есть лишь один способ его выбрать).

Упражнение. На листочке в клетку начерчен прямоугольник со сторонами и . Мы двигаемся из левого нижнего угла прямоугольника в правый верхний, сдвигаясь за шаг либо на одну клетку вверх, либо на одну клетку вправо. Сколько всего существует таких путей? Сведите задачу к вычислению количества сочетаний, как их считать я расскажу ниже.

Упражнение. Будем считать, что в условиях прошлой задачи . Сколько существует путей из левого нижнего угла в правый верхний таких, что они не пересекают диагонали квадрата? (Подсказка: возьмите путь, пересекающий диагональ, и отразите его начало до пересечения относительно этой диагонали).

Теорема.

Доказательство. В левой части этого выражения строит общее количество всех подмножеств множества . В правой части на самом деле написано то же самое: есть мощность булеана, как вы видели в § 3.1.

Теорема.

Доказательство. Выбрать элементнов из множества это всё равно что выбрать элементов, которые мы оставим в множестве.

Теорема.

Доказательство. Рассмотрим все -сочетания из множества . Сам элемент может либо принадлежать выбранному подмножеству, либо не принадлежать. В первом случае количество сочетаний будет равно , во втором случае, поскольку один элемент сочетания уже фиксирован, это будет величина .

Последняя теорема, как и в случае чисел Стирлинга, позволяет вычислять биномиальные коэффициенты. Однако, для сочетаний мы можем записать и явную формулу.

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

Теорема.

Доказательство. Доказательство практически дублирует доказательство для количества перестановок. На первую позицию мы можем поставить один из элементов. На вторую позицию один из оставшихся элементов. На третью —один из элементов. Однако в отличии от перестановок, теперь нам надо разместить лишь элементов, а не все , поэтому мы этот процесс оборвём на -том шаге. В итоге получаем выражение

Если это выражение умножить и разделить на , получим утверждение теоремы.

Само обозначение на самом деле почти всегда используется просто для обозначения произведения подряд убывающих чисел. Эту величину часто называют убывающим факториалом. В полной аналогии вводится и возрастающий факториал:

Упражнение. Покажите, что

Теорема.

Доказательство. -расстановку мы можем получить, вначале выбрав -элементное подмножество , а затем упорядочив его. Всего существует способов выбрать такое подмножество. Способов упорядочить выбранное — . Таким образом получаем соотношение

Поделив обе части на и подставив выражение для , получаем утверждение теоремы.

Упражнение. Теоремы 3.22 и 3.23 можно доказать, пользуясь явным представлением биномиального коэффициента, полученным в 3.25. Сделайте это.

Упражнение. Чему равно

Упражнение. Докажите, что

Упражнение. Докажите, что

Теорема.

Доказательство. Давайте вначале для наглядности распишем степень подробно:

Раскроем все скобки (если пока не понятно как, то потренируйтесь на каких-то частных случаях типа ). Раскрытие скобок можно интерпретировать так, что из каждой скобки мы выбираем либо , либо . Все слагаемые в полученной сумме будут иметь вид , с каким-то коэффициентом, появляющимся за счёт того, что некоторые слагаемые вида появляются несколько раз.

Слагаемое появится лишь один раз в случае, если из всех скобок мы выберем . Слагаемое появляется, если мы выбираем из всех скобок, кроме одной. Эту одну скобку, из которой мы выбираем , мы можем выбрать одним из способов. По аналогии появится раз, поскольку мы выбираем уже две скобки, из которых мы возьмём . Продолжая по аналогии приходим к утверждению теоремы.

Упражнение. Приведённую теорему можно доказать по индукции. Будет полезным проделать это самостоятельно.

Приведённая теорема даёт нам ещё один способ подсчитать количество подмножеств множества :

Упражнение. Докажите равенство

Последняя задача в свете теоремы 3.26 решается элементарно, однако я замечу, что такие задачи часто даются на олимпиадах для тех школьников, которые ещё по возрасту не могут знать таких теорем. Предполагается, что школьники могут доказать утверждение по индукции (и некоторые действительно могут). Это одна из причин по которой автор ненавидит олимпиадные задачки и «задачки на логику», которые часто дают на собеседованиях — большинство таких задач изначально появляются как тривиальные следствия каких-то более общих результатов, а потом уже задним числом оказывается, что задачу в общем-то можно было бы решить и пользуясь лишь школьной математикой. Однако если сравнивать пользу от решения такой задачи по индукции с пользой от изучения общей теоремы, то последнее явно выигрывает, хотя и не помогает на собеседованиях и олимпиадах.

Сочетания часто используются так же вот в каком ключе. Предположим, мама нам сказала: «Пойди в магазин и купи каких-нибудь пирожков». Мы приходим в магазин, а там продаётся наименований пирожков. Сколько всего способов у нас есть удовлетворить мамин запрос? Задача в такой постановке приводит нас к понятию сочетаний с повторениями, поскольку искомые наборы могут содержать повторяющиеся элементы.

Для решения задачи предположим, что пирожки разного вида мы разложили по разным пакетам (я видел, что в ларьках у метро именно так часто и делают). Схематически мы будем разделять пакеты вертикальной чертой , а пирожки (или, более общо, элементы множества), кружочками . Для примера давайте считать, что у нас всего имеется видов пирожков, а купили мы пирожков, причем из них было два пирожка первого вида, три третьего и один четвертого. Остальных пирожков мы не покупали. На схеме это будет выглядеть как

Теперь мы можем догадаться, как подсчитать общее количество различных сочетаний с повторениями: достаточно просто подсчитать общее количество возможных схем такого вида. В схеме, приведенной выше, если отбросить крайние чёрточки , получится различных позиций, на которых могут стоять чёрточки либо кружки. Причём мы точно знаем, что кружков всего будет штук, а чёрточек . Чтобы получить какую-то конкретную схему, нам надо выбрать позиций под кружки, а остальные позиции мы занимаем чёрточками. Итого для количества сочетаний с повторениями мы имеем выражение

Упражнение. Докажите, что существует способов представить число в виде суммы ненулевых слагаемых. Задача довольно сложная, поэтому дам некоторые наводки. Вначале следует разобрать случай, когда имеется ровно слагаемых. Подход здесь может быть аналогичным задаче с булочками выше, но надо учитывать то, что чтобы слагаемые были ненулевыми, мы не можем поставить подряд две черты, не поставив между ними кружок. Способов сделать это (докажите!). Отсюда уже довольно легко выводится и результат первоначальной задачи.

Упражнение. Сколько можно получить различных слов путём перестановки букв в слове «математика»?

Разбиения множеств

Определение. Число разбиений множества на множества мощностей называется мультиномиальным коэффициентом и обозначается как

В этом определении, очевидно, .

Теорема.

Доказательство. Выберём вначале элемент, споcобов сделать это . Из оставшихся элементов теперь выберём во второе множество элементов, способов сделать это . Продолжая рассуждать таким же образом, получаем
\begin{align*}
{n \choose k_1; k_2;\ldots; k_m} & = {n\choose k_1}{n-k_1\choose k_2}{n-k_1-k_2\choose k_3}\ldots{n-k_1-\ldots k_{m-1}\choose k_m} \\
&= \frac{n!}{k_1!(n-k_1)!}\cdot\frac{(n-k_1)!}{k_2!(n-k_1-k_2)!}\cdot\frac{(n-k_1-k_2)!}{k_3!(n-k_1-k_2-k_3)!}\cdot\ldots\\
&=\frac{n!}{k_1!k_2!\ldots k_m!}
\end{align*}

Теорема.
Здесь суммирование ведётся по всем возможным наборам чисел , дающим в сумме .

Доказательство. Аналогично доказательству теоремы 3.26. Проведите его самостоятельно.

Упражнение. Покажите, что теорема 3.26 является частным случаем для теоремы 3.29.

Упражнение. Покажите, что в теореме 3.29 будет ровно слагаемых.

Определение. Числами Стирлинга второго рода называется количество способов разбить множество на подмножеств.

Упражнение. Выразите через мультиномиальные коэффициенты.

Определение. Числами Белла называется количество способов разбить множество на подмножества.

Теорема.

Доказательство. Очевидно.

Упражнение. Докажите, что .

Значения настолько очевидны, что даже не заслуживают отдельного упражнения. Остальные значения, как и в случае чисел Стирлинга первого рода и количества сочетаний, могут быть вичислены рекурсивно.

Теорема.

Доказательство. Рассмотрим элемент множества . При разбиении на подмножества может войти в отдельное подмножество мощности 1, либо же войти в состав более крупного подмножества. В первом случае количество таких разбиений будет  — количество разбиений без учёта элемента . Во втором случае мы опять же строим разбиение множества , но уже на подмножеств. Нам остаётся лишь выбрать в какое из этих пожмножеств добавить элемент . Получаем .

Числа Белла так же допускают рекурсивное определние, хотя и не особо удобное.

Теорема.

Доказательство. Пусть элемент при некотором разбиении множества попал в множество размера . Есть способов выбрать это множество, оставшиеся элементы можно разбить на подмножества способами. Поскольку может быть произвольным от 1 до , получаем
\begin{align*}
B(n+1) & = \sum_{k=1}^{n+1}{n\choose k-1}B(n+1-k)\\
& = \sum_{k=1}^{n+1}{n\choose n-k+1}B(n-k+1) \\
& = \sum_{k=0}^{n}{n\choose k}B(k)
\end{align*}

Чтобы эта формула работала, нужно положить (чтобы увидеть это, примените 3.32 к значению ), что соответствует интуиции: существует лишь одно разбиение пустого множества на подмножества, которое само является пустым множеством.

Упражнение. Докажите, что для выполняется оценка

Вероятно вначале будет целесообразно, пользуясь 3.31, доказать, что при .

Включения-исключения

Вот задачка, которая как-то попалась мне в младшем возрасте на олимпиаде по математике, а затем многократно попадалась в разных книжках с занимательными примерами по математике.

Есть класс, в кото