Э-ээ, ну, как бы, м-мм, да, вот.

CLRS — Appendix C: Counting

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

Тем не менее, даже тут встретились какие-то небольшие трудности, пока разбирался. Вот, например, в доказательстве формулы для нижней границы биномиального коэффициента: (ⁿk) ≥ (n/k)^k. Сама по себе формула доказывается в два шага, но только, если знаешь вот это неравенство: (n−m)/(k−m) ≥ n/k (для 0 ≤ m < k ≤ n). Э-э, и тут я немного запутался сам в себе. Я точно помню, что доказательство этого неравенства вызывало какие-то адские трудности, но сейчас не вижу тут ничего сложного: достаточно просто сделать несколько эквивалентных преобразований:

> (n−m)/(k−m) ≥ n/k

> (n−m)/n ≥ (k−m)/k

> 1/n ≤ 1/k

> n ≥ k

Хотя, возможно, всё из-за того, что я увидел это доказательство вывернутым наизнанку (то есть n ≥ k последовательно преобразовывалось до неравенства, которое мы доказываем), что как бы формально более корректно, но выглядит при этом как последовательность совершенно случайных действий, которые совершенно случайным образом приводят нас к доказываемуму утверждению. В общем, это ещё один пример того, как по-дурацки записанное доказательство делает из простейшего утверждение какой-то роскет скиенсе, недоступный для понимания тупице вроде меня. И примеров таких очень-очень много, я вообще в чужих доказательствах с трудом ориентируюсь, если они не разбиты логически на пункты и не отмечено вкратце, что делается в каждом пункте. Большинство доказательств просто пишутся сплошной стеной текста, сдобренной фразочками вроде «доказательство этого утверждения предоставляется читателю в качестве упражнения» и «следует из утверждения 2.6.5» (формулировка которого, естественно, находится где-то далеко позади, если вообще не в другой книжке).

Ну, ладно, это была только нижняя граница для биноминального коэффициента. Верхняя же доказывается просто выводится из одной из оценок Стирлинга для факториала (там вроде довольно много всяких формул, но я помню только вот эти две: n! ~ √(2πn)·(n/e)ⁿ и √(2π)·n^n+1/2·e⁻ⁿ ≤ n! ≤ e·n^n+1/2·e⁻ⁿ). В общем, всё сводится вот к этому:

> (n/k)^k ≤ (ⁿk) ≤ (e·n/k)^k

И, наверное, это круто.

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

CLRS — Appendix C: Counting (Exercises)

C.1-1

>How many k-substrings does an n-string have? (Consider identical k-substrings at different positions to be different.) How many substrings does an n-string have in total?

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

Вот, например, в этой задачке можно, конечно, просто просуммировать число строк длины 1, длины 2, и так далее до n и получить (ⁿ⁺¹2). Но гораздо проще представить, что между символами в строке можно поставить условные «маркеры» (перед первым симоволом, после первого, ..., перед последним и после последнего, то есть всего — n+1) и тогда любая подстрока задаётся выбором каких-то двух «маркеров», стоящих по разные стороны относительно подстроки. Ну, а число способов выбрать 2 элемента из n+1 — это и есть (ⁿ⁺¹2).

Собственно, примерно в такой же манере решаются и все остальные задачки на комбинаторику. И это уже было, кстати, в 6.042J.

Вот, например:

> k·(ⁿk) = n·(^n-1k−1)

Эту формулу можно проинтерпретировать как «число способов собрать команду из k человек (выбирая из n претендентов) и выбрать в ней капитана». Слева — мы сначала собираем команду, а потом выбираем в ней капитана, а справа — сначала выбираем n способами капитана, а потом капитан добирает себе в команду оставшихся k−1 человека. То есть разными способами считаем одно и то же.

> (ⁿk) = (ⁿ⁻¹k) + (ⁿ⁻¹k−1)

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

Последний факт, кстати, используется при построении Треугольника Паскаля, про который я вроде когда-то слышал, но никогда не знал толком, что это. Как оказалось, это просто последовательность строк, записанных друг под другом, где в n-ой строке выписаны n биноминальных коэффициентов: начиная с (ⁿ0), и, заканчивая (ⁿn). Получается такой прямоугольный треугольник, у которого по границе стоят единицы, а остальные элементы вычисляются как сумма вышестоящего и слева-сверху-стоящего элементов. Полезно, если ты не знаешь коэффициенты для Бинома Ньютона для какой-то там большой степени: можно быстро просуммировать на бумажке и получить их выписанными в одном из рядов в треугольнике.

С.1-10

>Покажите, что (ⁿk) принимает максимальное значение в k = [n/2].

Доказательство на пикрелейтеде. Я его отдельно довольно подробно расписал, потому что один раз умудрился запутаться во всех этих индексах и доказать неправильно. Сейчас вроде как нормально.

С.1-11

> (nj+k) ≤ (nj)·(n−jk)

Вроде очевидно, но заставляет задуматься. Может показаться, что верно и более строгое утверждение, с равенством, но на деле это не так: слева — число способов выбрать j+k элементов из n, а справа — число способов сначала выбрать j, а потом k элементов из того же набора. То есть во втором случае нам чуть-чуть важен порядок, так что в каком-нибудь простом примере на множестве {A, B} и j=1, k=1 будет выполняться строгое неравенство: с одной стороны, можем выбрать только одним способом сразу два элемента, с другой, последовательно элементы мы можем выбрать двумя способами: либо сначала A, а потом B, либо сначала B, а потом A.

C.1-13

>Use Stirling's approximation to prove that (2nn) = чему-то там

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

Остаются только две приложенных картинки.

Первая из двух, но третья из четырёх, вот такая математика — доказательство какого-то очередного глупого неравенства. ОБРАТИТЕ ВНИМАНИЕ на два «короче» внизу и на то, что я, будучи человеком, который неспособен сложить два двузначных числа в уме, героически посчитал производную сложной функции, доведя её до состояния, где можно понять, что производная имеет какой-то там знак на каком-то там интервале. А само доказательство получилось каким-то заковыристым, плюс наверняка там полная ерунда с областями определения n и k, так что там в некоторых местах могут быть деления на ноль, которые надо бы отдельно рассматривать, но мне всё равно, вот. А доказательство для второй половины промежутка там следует просто из такой своего рода «симметричности» биноминального коэффициента.

На последней картинке на мой взгляд человека, не обременённого особыми познаниями во всяких математиках — просто какие-то формулы, которые как-то магически друг из друга выводятся. Какой смысл у всего этого, что такое binary entropy function, почему мы обозначали k = λn — не знаю.

Короче, чёт такое. Уже предвосхищаю слетевшую разметку с поста.

Э-ээ, ну, как бы, м-мм, да, вот.

CLRS — Appendix C: Counting

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

Условимся, что (n | k) — это биноминальный коэффициент, или же «цэ из эн по ка». Я мог бы записать их вот так: (ⁿ_k), но тогда из-за того, что здесь слишком много биноминальных коэффициентов, слетает разметка.

Тем не менее, даже тут встретились какие-то небольшие трудности, пока разбирался. Вот, например, в доказательстве формулы для нижней границы биномиального коэффициента: (n | k) ≥ (n/k)^k. Сама по себе формула доказывается в два шага, но только, если знаешь вот это неравенство: (n−m)/(k−m) ≥ n/k (для 0 ≤ m < k ≤ n). Э-э, и тут я немного запутался сам в себе. Я точно помню, что доказательство этого неравенства вызывало какие-то адские трудности, но сейчас не вижу тут ничего сложного: достаточно просто сделать несколько эквивалентных преобразований:

> (n−m)/(k−m) ≥ n/k

> (n−m)/n ≥ (k−m)/k

> 1/n ≤ 1/k

> n ≥ k

Хотя, возможно, всё из-за того, что я увидел это доказательство вывернутым наизнанку (то есть n ≥ k последовательно преобразовывалось до неравенства, которое мы доказываем), что как бы формально более корректно, но выглядит при этом как последовательность совершенно случайных действий, которые совершенно случайным образом приводят нас к доказываемуму утверждению. В общем, это ещё один пример того, как по-дурацки записанное доказательство делает из простейшего утверждение какой-то роскет скиенсе, недоступный для понимания тупице вроде меня. И примеров таких очень-очень много, я вообще в чужих доказательствах с трудом ориентируюсь, если они не разбиты логически на пункты и не отмечено вкратце, что делается в каждом пункте. Большинство доказательств просто пишутся сплошной стеной текста, сдобренной фразочками вроде «доказательство этого утверждения предоставляется читателю в качестве упражнения» и «следует из утверждения 2.6.5» (формулировка которого, естественно, находится где-то далеко позади, если вообще не в другой книжке).

Ну, ладно, это была только нижняя граница для биноминального коэффициента. Верхняя же доказывается просто выводится из одной из оценок Стирлинга для факториала (там вроде довольно много всяких формул, но я помню только вот эти две: n! ~ √(2πn)·(n/e)ⁿ и √(2π)·n^n+1/2·e⁻ⁿ ≤ n! ≤ e·n^n+1/2·e⁻ⁿ). В общем, всё сводится вот к этому:

> (n/k)^k ≤ (ⁿ_k) ≤ (e·n/k)^k

И, наверное, это круто.

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

CLRS — Appendix C: Counting (Exercises)

C.1-1

>How many k-substrings does an n-string have? (Consider identical k-substrings at different positions to be different.) How many substrings does an n-string have in total?

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

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

Собственно, примерно в такой же манере решаются и все остальные задачки на комбинаторику. И это уже было, кстати, в 6.042J.

Вот, например:

> k·(n | k) = n·(n-1 | k−1)

Эту формулу можно проинтерпретировать как «число способов собрать команду из k человек (выбирая из n претендентов) и выбрать в ней капитана». Слева — мы сначала собираем команду, а потом выбираем в ней капитана, а справа — сначала выбираем n способами капитана, а потом капитан добирает себе в команду оставшихся k−1 человека. То есть разными способами считаем одно и то же.

> (n | k) = (n−1 | k) + (n−1 | k−1)

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

Последний факт, кстати, используется при построении Треугольника Паскаля, про который я вроде когда-то слышал, но никогда не знал толком, что это. Как оказалось, это просто последовательность строк, записанных друг под другом, где в n-ой строке выписаны n биноминальных коэффициентов: начиная с (n | 0), и, заканчивая (n | n). Получается такой прямоугольный треугольник, у которого по границе стоят единицы, а остальные элементы вычисляются как сумма вышестоящего и слева-сверху-стоящего элементов. Полезно, если ты не знаешь коэффициенты для Бинома Ньютона для какой-то там большой степени: можно быстро просуммировать на бумажке и получить их выписанными в одном из рядов в треугольнике.

С.1-10

>Покажите, что (n | k) принимает максимальное значение в k = [n/2].

Доказательство на пикрелейтеде. Я его отдельно довольно подробно расписал, потому что один раз умудрился запутаться во всех этих индексах и доказать неправильно. Сейчас вроде как нормально.

С.1-11

> (n | j+k) ≤ (n | j)·(n−j | k)

Вроде очевидно, но заставляет задуматься. Может показаться, что верно и более строгое утверждение, с равенством, но на деле это не так: слева — число способов выбрать j+k элементов из n, а справа — число способов сначала выбрать j, а потом k элементов из того же набора. То есть во втором случае нам чуть-чуть важен порядок, так что в каком-нибудь простом примере на множестве {A, B} и j=1, k=1 будет выполняться строгое неравенство: с одной стороны, можем выбрать только одним способом сразу два элемента, с другой, последовательно элементы мы можем выбрать двумя способами: либо сначала A, а потом B, либо сначала B, а потом A.

C.1-13

>Use Stirling's approximation to prove that (2n | n) = чему-то там

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

Остаются только две приложенных картинки.

Первая из двух, но третья из четырёх, вот такая математика — доказательство какого-то очередного глупого неравенства. ОБРАТИТЕ ВНИМАНИЕ на два «короче» внизу и на то, что я, будучи человеком, который неспособен сложить два двузначных числа в уме, героически посчитал производную сложной функции, доведя её до состояния, где можно понять, что производная имеет какой-то там знак на каком-то там интервале. А само доказательство получилось каким-то заковыристым, плюс наверняка там полная ерунда с областями определения n и k, так что там в некоторых местах могут быть деления на ноль, которые надо бы отдельно рассматривать, но мне всё равно, вот. А доказательство для второй половины промежутка там следует просто из такой своего рода «симметричности» биноминального коэффициента.

На последней картинке на мой взгляд человека, не обременённого особыми познаниями во всяких математиках — просто какие-то формулы, которые как-то магически друг из друга выводятся. Какой смысл у всего этого, что такое binary entropy function, почему мы обозначали k = λn — не знаю.

Короче, чёт такое.