1 декабря 2013 в 00:00

Производящие функции — туда и обратно

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

Введение


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

Идея производящих функций достаточно проста: сопоставим некоторой последовательности <g0, g1, g2, ..., gn> — дискретному объекту, степенной ряд g0 + g1z + g2z2 +… + gnzn +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.

История возникновения производящих функций


Известно, что начало методу производящих функций положил английский математик Абрахам де Муавр, а дальнейшему развитию и продолжению данного метода мы обязаны великому математику, имя которого Леонард Эйлер.

В 50-х годах XVIII века Эйлер решал следующую задачу: какие грузы можно взвесить с помощью гирь в 20, 21, 22,..., 2n грамм и сколькими способами? При решении этой задачи он использовал никому неизвестный на то время метод производящих функций, которому и посвящена данная статья. К этой задаче мы вернёмся немного позже, после того как разберёмся более подробно с устройством производящих функций.

Метод производящих функций


Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?

Обозначим белый шар символом ○, чёрный — ●, Tn — искомое количество расположений шаров. Символом Ø — обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:

Если n=1, то очевидно имеется 2 способа — взять либо белый шар ○, либо взять чёрный шар ●, таким образом, T2 = 2.

Если n=2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.

Рассмотрим случай для n=3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать чёрным шаром и аналогично продолжить 4-мя шарами ●○○, ●○●, ●●○, ●●●.

В итоге количество шаров удвоилось, то есть T3 = 2T2. Аналогично T4 = 2T3, то есть, обобщая для всех n, получаем рекуррентное уравнение Tn = 2Tn-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать — Tn = 2n (так как 2⋅2n-1 = 2n).

А что если у нас плохо с угадыванием? И что делать, если уравнение будет сложнее? А вообще причём здесь производящие функции?

«Просуммируем» все возможные комбинации расположений шаров:

G = Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ○○○ + ○○● + ○●○ + ○●● + ●○○ + ●○● + ●●○ + ●●● +…

Вопрос о допустимости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением всё понятно, но что значит умножить одну последовательность шаров на другую? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, так как ○●⋅●○ ≠ ●○⋅○●. Символ Ø — в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○● и коммутирует с любой последовательностью шаров.

Производя с рядом G последовательность манипуляций, а именно вынося за скобки левый белый и чёрный шары

G = Ø + ○ (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) + ● (Ø + ○ + ● + ○○ + ○● + ●○ + ●● + ...) = Ø + ○G +●G

получим уравнение G = Ø + ○G +●G.

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



Учитывая формулу суммы геометрической прогрессии , имеем

.

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



Коэффициент при ○kn-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Таким образом, общее количество расположений n шаров есть сумма по всем возможным значениям k. Как известно .

Эту формулу можно было получить непосредственно из заменив Ø на 1, а ○ и ● на z (в виду их равнозначности). Получим то есть коэффициент при zn равен 2n.

Обсуждение метода


Так что же позволяет данному методу быть работоспособным при решении различных задач?

Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g0 + g1z + g2z2 +… + gnzn +… причем коэффициенты gk (не заданные в явном виде) — являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z — является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.

G(z) = g0 + g1z + g2z2 +… + gnzn +… — называется производящей функцией для последовательности <g0, g1, g2, ..., gn>. Заметим, однако, что хотя G(z) — функция, это всё таки формальная запись, то есть мы не можем подставить вместо z любое значение z = z0, за исключением z = 0, так как G(0) = g0.

Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому, а затем замкнутый вид разложить в степенной ряд, и тем самым получить значения для коэффициентов gk.

Отвечая на поставленный вначале вопрос можно сказать так: успех данного метода связан с возможностью записать производящую функцию в замкнутом виде. Так, например, производящая функция для последовательности <1, 1, 1, ..., 1> в бесконечном виде представляется как 1 + x + x2 + x3 + ..., а в замкнутом .

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

Итак, задача звучит следующим образом: какие грузы можно взвесить с помощью гирь в 20, 21, 22,..., 2n грамм и сколькими способам?

Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z2)(1+z4)… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g1z + g2z2 + g3z3 +….

Что же из себя представляют коэффициенты gk? Каждый gk — это коэффициент при zk, а zk — получается как произведение каких-то одночленов z2m, то есть gk — это в точности число разных представлений числа k в виде суммы некоторых из чисел 1, 2, 22, 23,..., 2m,…. Другими словами gk — это число способов взвешивания груза в k грамм заданными гирями. Как раз то, что мы искали!

Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).

(1-z)G(z) = (1-z)(1+z)(1+z2)(1+z4)(1+z8)…
(1-z)G(z) = (1-z2)(1+z2)(1+z4)(1+z8)…
(1-z)G(z) = (1-z4)(1+z4)(1+z8)…
(1-z)G(z) = 1


С одной стороны G(z) = 1 + g1z + g2z2 + g3z3 +… с другой стороны мы только что получили . Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна . Сопоставляя эти два равенства, получаем g1 = g2 = g3 =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

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


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

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

Итак, имеем

F0 = 0,
F1 = 1,
Fn = Fn-1 + Fn-2, n ≥ 2

Умножим каждую строчку на z0, z1, ..., zn соответственно:

z0 ⋅ F0 = 0,
z1 ⋅ F1 = z,
zn ⋅ Fn = zn ⋅ Fn-1 + zn ⋅ Fn-2, n ≥ 2

Просуммируем эти равенства:



Обозначим левую часть

Рассмотрим каждое из слагаемых в правой части:



Имеем следующее уравнение G(z) = z + z G(z) + z2 G(z) решая которое относительно G(z) находим

— производящая функция для последовательности чисел Фибоначчи.

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



Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:



Подставляя в это уравнение значение z = z1 и z = z2, находим

Напоследок немного преобразуем выражение для производящей функции



Теперь каждая из дробей представляет собой сумму геометрической прогрессии.

По формуле находим

Но ведь мы искали G(z) в виде . Отсюда делаем вывод, что



Эту формулу можно переписать в другом виде не используя «золотое сечение»:



что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.

Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:

  1. Запишите одно уравнение, выражающее gn через другие элементы последовательности. Это уравнение должно оставаться справедливым для всех целых n с учетом того, что g-1=g-2=....=0.
  2. Умножьте обе части уравнения на zn и просуммируйте по всем n. В левой части получится сумма , которая равна производящей функции G(z). Правую часть следует преобразовать так, чтобы она превратилась в какое-то другое выражение, включающее G(z).
  3. Решите полученное уравнение, получив для G(z) выражение в замкнутом виде.
  4. Разложите G(z) в степенной ряд и прочитайте коэффициент при zn, это и будет замкнутый вид для gn.

Причина, по которой данный метод работает, заключается в том, что единая функция G(z) представляет всю последовательность gn и это представление допускает многие преобразования.

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

Дифференцирование и интегрирование производящих функций


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

Пусть G = G(z) – производящая функция. Производной этой функции называется функция . Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. Имеем



Тем самым, действие дифференцирования на произвольной производящей функции
G (z) = g0 + g1z + g2z2 + g3z3 +… дает G΄(z) = g1 + 2g2z + 3g3z2 + 4g4z3 +….

Интегралом называется функция



Операция дифференцирования обратна операции интегрирования:



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



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



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

g0 = 1,
g1 = 1,
gn = gn-1 + 2gn-2 + (-1)n

Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

z0⋅ g0 = 1,
z1 ⋅ g1 = z,
zn ⋅ gn = zn ⋅ gn-1 + 2zn ⋅ gn-2 + (-1)n ⋅ zn



Левая часть представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:







Составляем уравнение:



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



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



Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:



С одной стороны мы искали G(z) в виде , с другой стороны .

Значит, .

Вместо заключения


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



Возводя в квадрат обе части этого равенства получим



Приравнивая коэффициенты при xn в левой и правой частях, получаем



Эта формула имеет прозрачный комбинаторный смысл, но доказать её непросто. Еще в 80-е годы XX века появились публикации, посвященный этому вопросу.
Гуев Тимур @timyrik20
карма
117,7
рейтинг 0,0
Похожие публикации
Самое читаемое Разработка

Комментарии (35)

  • +4
    Легко и непринужденно сворачивая ряд 1+х+х^2… в 1/(1-х), ни разу не упомянуто о том, что это верно лишь для |х|<=1.
    • +7
      В том-то и дело, что это здесь никого не интересует:

      Тот факт, что ряд является формальным, говорит о том, что z — является просто символом, вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.
      • +4
        Ну так данный конкретный ряд сворачивается только для чисел, при чем по модулю меньших единицы. По формуле геом. прогрессии 1+х+х^2+..+х^n = (1-x^n)/(1-x). Если же предела х^n при n стремящемся к бесконечности нет или он не 0 (а его нет, если х — абстрактный предмет), то данный ряд не будет равен 1/(1-х).
        • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Достаточно считать, что последовательность степенных рядов сходится к ряду S, если для любого N найдётся такой номер K, что у всех элементов последовательности с номерами больше K все коэффициенты до x^N включительно такие же, как у S. Тогда последовательность
          1*(1-x), (1+x)*(1-x), (1+x+x^2)*(1-x),… сходится к 1. Объект x в этом случае быть числом не обязан, это просто символ.
          • НЛО прилетело и опубликовало эту надпись здесь
        • +5
          Для тех, кто не понимает формальной строгости происходящего, я чуть-чуть дополню статью.

          Наиболее правильный ответ на любые претензии по корректности: считайте, что вы работаете с формальными бесконечными рядами коэффициентов (a0, a1, a2,… ), как с бесконечномерным векторным пространством, на котором определено некоторым образом умножение (аналогично тому, как это происходит у многочленов: (a0, a1, a2, ...) * (b0, b1, b2) = (a0b0, a0b1 + a1b0, a2b0 + a1b1 + a0b2, ...) ), деление (чуть-чуть посложнее, но по-прежнему корректно, если младшие слагаемые в обоих рядах правильно соотносятся по степеням, то есть в итоге не вылезет слагаемых 1 / x), дифференцирование (опять же, по формальному правилу (a0, a1, a2, ...)' = (a1, 2a2, 3a3, ...), оно, например, удовлетворяет тождеству u'v = v'u), и так далее.

          Одно из главных свойств заключается в том, что производящий ряд для функции f(x) очень часто совпадает с рядом Тейлора функции f. В частности это видно из статьи для функции 1 / (1 — x) = 1 + x + x^2 +… В ряд она действительно раскладывается только на круге сходимости (-1 < x < 1), но формальное равенство степенных рядов (1 — x) * (1 + x + x^2 + ...) = (1, -1, 0, 0, ...) * (1, 1, 1, 1, ...) = 1 по описанному выше правилу умножения верно само по себе.

          Другой пример: разложение по биному для sqrt(1 + x) = (1 + x) ^ (1/2) = 1 + 1/2 x + 1/2 * (-1/2) / 2! x^2 + 1/2 * (-1/2) * (-3/2) / 3! x^3 +… = f(x) тоже удовлетворяет свойству sqrt(1 + x) * sqrt(1 + x) = 1 + x (проверьте сами, посчитав первые сколько-то коэффициентов в произведении).

          Ну, и так далее. Аппарат действительно мощный. Очень наглядно иллюстрируется формулой для вывода чисел Каталана.
          • 0
            как с бесконечномерным векторным пространством, на котором определено некоторым образом умножение (аналогично тому, как это происходит у многочленов: (a0, a1, a2, ...) * (b0, b1, b2) = (a0b0, a0b1 + a1b0, a2b0 + a1b1 + a0b2, ...) )


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

            В ряд она действительно раскладывается только на круге сходимости (-1 < x < 1), но формальное равенство степенных рядов (1 — x) * (1 + x + x^2 + ...) = (1, -1, 0, 0, ...) * (1, 1, 1, 1, ...) = 1 по описанному выше правилу умножения верно само по себе.


            Но это лучше показать явно. Вы можете дать ссылку на учебник, где-это более строго расписывается?
            Чувствую себя идиотом. Вроде как математика строгая и формальная, но куда не ткнись пытаются объяснять «интуитивно». Хотя, может просто не везло с преподами :)
            • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              Еще б доказать, что ничего никуда не вылезает за пределы кольца. То что существует деление, и можно определить дифференцирование.

              То, что оно «не вылезает за пределы», следует из определения — результаты сложения и умножения записаны в виде степенных рядов, а значит, принадлежат описываемой структруре.
              Чтобы доказать, что это кольцо, надо проверить основные свойства. То, что это группа по сложению, следует из того, что сложение идёт «покоординатно». То, что это векторное пространство над R (правда, без конструктивно описываемого базиса), нам сейчас неинтересно. Осталось проверить свойства умножения.
              Коммутативность (которая не обязательна, но знать, выполняется ли она, полезно) сразу следует из формулы. Ассоциативность проверяем так же, как для матриц — явно выписывая коэффициент произведения трёх рядов: если d=a*b*c, то в обоих порядках получим d[i]=sum(a[k]*b[m]*c[n],k+m+n=i) — выражения будут одинаковыми. Дистрибутивность тоже проверяем прямым вычислением коэффициента.
              Существование деления на ряд с ненулевым свободным членом доказывается по индукции: если мы вычислили первые N-1 коэффициент результата, то N-й определяется однозначно. И можно доказать, что каждый конкретный коэффициент произведения ряда с вычисленными таким образом коэффициентами на «делимое» будет равен соответствующему коэффициенту «делителя».
              Про дифференцирование пока ничего не скажу. Для суммы и произведения формулы проверяются, а вот является ли подстановка одного степенного ряда в другой корректной операцией — не уверен. Думаю, что нет.
              Показать явно здесь можно всё: просто садитесь и считайте. Прямо по исходным формулам. Но это долго и довольно скучно.
      • 0
        Если х это объект, то как вообще обосновать вот такое равенство 1/(1-x)=sum x^n?
        • +2
          Переписать его как (sum x^n)*(1-x)-1=0. И доказать, что коэффициент при любом x^k действительно равен нулю.
          • 0
            Спасибо! Очень понятно и кратко объяснили. Предыдущие комментарии не давали понимания.

            Пожалуйста, объясните ещё, как в статье был совершён переход:
            (1-z)G(z) = (1-z^4)(1+z^4)(1+z^8)…
            в
            (1-z)G(z) = 1
            Моё доказательство для 0 < z < 1
            Как я понял, (1-z^4)(1+z^4) превращается в (1-z^8), которое вместе с (1+z^8) превращается в (1-z^16) и т. д. Если предположить, что 0 < z < 1, то понятно, как в итоге получить 1. Можно взять последовательность, каждый следующий элемент которой будет получаться из предыдущего умножением на (1+z^(2^x)). Для неё доказать, что она возрастает, что для каждого y<1 найдётся номер члена, начиная с которого все члены будут больше y, и что все члены < 1. Тогда мы докажем, что предел такой последовательности 1. Возможно, есть и более простое доказательство.

            А как это доказать для любого z, в том числе не для чисел?

            Мне кажется, тут нужно применить приём, похожий на тот, что применили Вы, поэтому задаю этот вопрос сюда.
            • +2
              А у Вас уже почти всё написано. Произведение первых членов вплоть до 1+z^k равно 1-z^(2*k) (где k — степень двойки), а при умножении на любой следующий член коэффициенты произведения при z^0, z^1, ..., z^(2k-1) измениться уже не могут. Отсюда следует, что в бесконечном произведении все коэффициенты, кроме первого, равны нулю.
    • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Действительно если ряд расходится это не значит, что он не имеет суммы.
      Всем операциям которые мы проделывали над производящими функциями можно дать строгое истолкование как операциям над формальными рядами, а такие операции корректны даже если ряд расходится.
      Но если мы говорим о просто степенных рядах, то конечно данная формула справедлива только для чисел меньших 1 по модулю.
  • НЛО прилетело и опубликовало эту надпись здесь
  • –4
    А завтра как раз матан в НМУ… Спасибо!
  • 0
    Очень интересно было читать. Даже не догадывался о том, что ряды можно использовать таким необычным образом. Спасибо за интересное изложение:) Общая идея напомнила операционное исчисление.
    • 0
      Спасибо! Писать тоже было очень интересно :)
      Действительно на сегодняшний день самый мощный метод работы с последовательностями — это преобразование бесконечных рядов, которые генерируют эти последовательности.
  • +3
    любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.
    Казалось бы, это очевидным образом следует из существования двоичной системы счисления.
    • 0
      Видимо, у Эйлера не было в детстве компьютера, и он с ней был плохо знаком ((
  • +1
    Спасибо за статью. Заставила залезть в учебник.

    Но тут много неясных моментов. Без введения формальных алгебраических структур это напоминает шаманство.
    1) С первых формул вводится деление, хотя это еще вопрос, допускает ли эта структура обратный элемент по произведению
    2) Чудесным образом ряд раскладывается по сумме геометрической прогрессии. Но, как правильно заметили выше, это требует введения пределов. Аргумент что Z — это формальная переменная какой-то не очень «математический». Понятно, что сумма будет существовать, но лучше это показать или хотя б пояснить почему она существует.

    Все же, вы можете дать строгое определение формального ряда, и вывести тоже самое без использование геометрической прогрессии (хотяб схематично)? А то есть чувство, что где-то обманывают :)
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        И ещё — коэффициент произведения не зависит от коэффициентов сомножителей при более высоких степенях.
  • 0
    Правы те, кто говорит, что надо учитывать сходимость ряда и область его сходимости.
    Пока мы работаем просто со степенными рядами, то это, конечно, неважно. Но если мы захотим перейти от бесконечного числа коэффициентов к представлению в виде формулы, и получить производящую функцию, то нам придётся идти на поклон к ТФКП, и просить у них функцию, ряд Тейлора которой имеет те же коэффициенты, что и наш степенной ряд. Только после этого у нас появится круг сходимости, в котором мы сможем манипулировать нашими рядами как функциями. А если вдруг нам попадётся ряд sum(x^n*n!) — чем нам вообще может помочь метод производящих функций? Конечно, в каких-нибудь p-адических числах этот ряд к чему-то сходится, только вот к чему?
  • 0
    Я только начал читать, но возник вопрос:
    А как работает формула про (a+b)^n при отсутствии коммутативности?
    • 0
      Довольно просто. Берутся все строки длиной n, составленные из a и b (их всего 2^n), для каждой вычисляется произведение, а потом эти произведения складываются.
      Это в предположении, что некоммутативно только умножение (в кольцах сложение коммутативно всегда).
      • 0
        (a+b)^2 = a*a + a*b + b*a + b*b. Откуда тут получится 2*a*b?
        • 0
          Ниоткуда не получится. Будет сумма 4=2^2 произведений, как у вас и написано.
          А (a+b)^3 = a^3 + a^2*b + a*b*a + a*b^2 + b*a^2 + b*a*b + b^2*a + b^3, сумма 8 произведений. Всё, как и должно быть.

          Возможно, я неправильно понял вопрос. «Как работает формула» я прочитал, как «какая получается формула». А классический бином Ньютона, конечно, работать не будет.
          • 0
            Именно, не получается. А в статье есть такой переход.

            Там понятно что почему получается и сходится, но как по мне эта часть статьи эээ странная.
          • +1
            Вот это просто неправда: image
  • 0
    Почему сворачивая цепочку (1-z^2)(1+z^2)(1+z^4)… мы получим единицу? Если z — это нечто «формальное», то как оно может иметь какой-то предел вообще?
    • +3
      Потому что коэффициент при любой степени z, кроме z^0, в конце концов окажется равным нулю. И больше не изменится.
      • +1
        Изящно! :)

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.