Вспоминая дискретную математику...

Любить математику "платонически" нельзя, её периодически нужно касаться и решать проблемы несколько более сложные и увлекательные чем базовые операции с которыми сталкивается обычно программист в рабочих буднях. Даже те, чья работа сильно зваисит от математики, обычно используют знания из небольшого количества разделов.

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



О комбинаторике
Комбиноаторика нужна для вычисления вероятностей. Она полезна для расчета сложности алгоритма. Многие техники AI и ML, а так же многое из алгоритмов базируется на использовании комбинаторики. В общем, из решения комбинаторных задач можно получить много практической выгоды.. А так же замечаетлно размять мозги и получить массу удовольствия!

Решив несколько задач и освежив представления о комбинаторике хочу сохранить нечто вроде опороного конспекта или "шпоры" тут. Конечно сторонних материалов масса, но что может быть лучше самостоятельно сделанного конспекта? Вот постепенно буду обрабатывать свои записи и выкладывать сканы сюда. И иногда исправлять ошибки.

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

Немного о математической иднукции и рекуррентностях. 

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

Для чего нужен мне метод мат индукции? В основном для проверки математических догадок. Иногда полу интуитивно получаешь некоторое утверждение, в котором не уверен окончательно, вот тут то мат. индукция приходит на помощь.

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

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


<Обновление>.


Выкладываю чтобы потом не забыть.

 К развязыванию рекурентностей обновляю скриншот. Метод N2 рулит - он универсальный.