Самостоятельная работа №1 План: Аксиоматические теории множеств. Нечеткие множества

А теперь вооружившись знаниями, вернемся к задаче, которую решал Эйлер.

Итак, задача звучит следующим образом: какие грузы можно взвесить с помощью гирь в 2⁰, 2¹, 2²,..., 2ⁿ грамм и сколькими способам?

Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z²)(1+z⁴)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g₁z + g₂z² + g₃z³ +….

Что же из себя представляют коэффициенты g_k? Каждый g_k — это коэффициент при z^k, а z^k — получается как произведение каких-то одночленов z^2m, то есть g^k — это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 2², 2³,..., 2^m,…. Другими словами g_k — это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!
Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).

(1-z)G(z) = (1-z)(1+z)(1+z²)(1+z⁴)(1+z⁸)…
(1-z)G(z) = (1-z2)(1+z²)(1+z⁴)(1+z⁸)…
(1-z)G(z) = (1-z⁴)(1+z⁴)(1+z⁸)…
(1-z)G(z) = 1


С одной стороны G(z) = 1 + g₁z + g₂z² + g₃z³ +… с другой стороны мы только что получили  . Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна  . Сопоставляя эти два равенства, получаем g₁ = g₂ = g₃ =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

Решение рекуррентных соотношений

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

Начнем со всеми знакомой последовательностью чисел Фибоначчи. Каждый из нас знает её рекуррентный вид: F₀ = 0, F₁ = 1, F_n = F_n-1 + F_n-2, n ≥ 2. Однако не каждый знает вид этой формулы в замкнутом виде и это не удивительно, ведь она содержит иррациональное число(«золотое сечение») в своём составе.

Итак, имеем
F₀ = 0,
F₁ = 1,
F_n = F_n-1 + F_n-2, n ≥ 2