Меня часто спрашивают о том, как можно вывести огромную формулу в несколько тысяч слагаемых, которая является решением той или иной трудной задачи. Как вообще действовать, чтобы вывести формулы длиной свыше 10000 слагаемых, о которых рассказывается, например, здесь? На самом деле, во-первых, все эти формулы не выводятся, а «угадываются», а во-вторых, в ряде случаев это делается тривиальным образом. Хотя бывают и чрезвычайно сложные ситуации. Здесь я расскажу о самых простых примерах, так сказать, для начала. Речь пойдёт пока только о линейных рекуррентных соотношениях с постоянными коэффициентами.

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

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

Этот пост рекламирует мой новый сайт, ссылки на который встречаются в середине текста и в самом конце. Здесь рассматривается один из самых простых примеров применения техники производящих функций.