Биномиальное преобразование

Преобразование математической последовательности

В комбинаторике биномиальное преобразование — это преобразование последовательности (т. е. преобразование последовательности ) , которое вычисляет ее прямые разности . Оно тесно связано с преобразованием Эйлера , которое является результатом применения биномиального преобразования к последовательности, связанной с ее обычной производящей функцией .

Определение

Биномиальное преобразование T последовательности { an _} — это последовательность { sn _} , определяемая формулой

${\displaystyle s_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{k}.}$

Формально можно написать

${\displaystyle s_{n}=(Ta)_{n}=\sum _{k=0}^{n}T_{nk}a_{k}}$

для преобразования, где T — бесконечномерный оператор с _{матричными} элементами Tnk . Преобразование является инволюцией , то есть

${\displaystyle TT=1}$

или, используя индексную запись,

${\displaystyle \sum _{k=0}^{\infty }T_{nk}T_{km}=\delta _{nm}}$

где находится дельта Кронекера . Исходную серию можно восстановить, ${\displaystyle \delta _{nm}}$

${\displaystyle a_{n}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}s_{k}.}$

Биномиальное преобразование последовательности — это всего лишь n- ные прямые разности последовательности, причем нечетные разности имеют отрицательный знак, а именно:

${\displaystyle {\begin{aligned}s_{0}&=a_{0}\\s_{1}&=-(\Delta a)_{0}=-a_{1}+a_{0}\\s_{2}&=(\Delta ^{2}a)_{0}=-(-a_{2}+a_{1})+(-a_{1}+a_{0})=a_{2}-2a_{1}+a_{0}\\&\;\;\vdots \\s_{n}&=(-1)^{n}(\Delta ^{n}a)_{0}\end{aligned}}}$

где ∆ — оператор прямой разности .

Некоторые авторы определяют биномиальное преобразование с дополнительным знаком, чтобы оно не было самообратным:

${\displaystyle t_{n}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}a_{k}}$

чье обратное значение

${\displaystyle a_{n}=\sum _{k=0}^{n}{n \choose k}t_{k}.}$

В этом случае первое преобразование называется обратным биномиальным преобразованием , а второе — просто биномиальным преобразованием . Это стандартное использование, например, в Электронной энциклопедии целочисленных последовательностей .

Пример

Обе версии биномиального преобразования появляются в разностных таблицах. Рассмотрим следующую таблицу различий:

Каждая строка является разницей предыдущей строки. ( N -е число в m -й строке — это a _{m , n} = 3 ^{n −2} (2 ^{m +1} n ² + 2 ^m (1+6 m ) n + 2 ^{m -1} 9 m ² ), и выполняется разностное уравнение a _{m +1, n} = a _{m , n +1} - a _{m , n} .)

Верхняя строка, читаемая слева направо, равна { a _n } = 0, 1, 10, 63, 324, 1485, ... Диагональ с той же начальной точкой 0 равна { t _n } = 0, 1, 8, 36. , 128, 400, ... { t _n } — неинволютивное биномиальное преобразование { a _n }.

Верхняя строка, читаемая справа налево, равна { b _n } = 1485, 324, 63, 10, 1, 0, ... Поперечная диагональ с той же начальной точкой 1485 равна { s _n } = 1485, 1161, 900. , 692, 528, 400, ... { s _n } — инволютивное биномиальное преобразование { b _n }.

Обыкновенная производящая функция

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

${\displaystyle f(x)=\sum _{n=0}^{\infty }a_{n}x^{n}}$

и

${\displaystyle g(x)=\sum _{n=0}^{\infty }s_{n}x^{n}}$

затем

${\displaystyle g(x)=(Tf)(x)={\frac {1}{1-x}}f\left({\frac {-x}{1-x}}\right).}$

преобразование Эйлера

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

${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+1}}}}$

который получается путем подстановки x = 1/2 в последнюю формулу выше. Члены в правой части обычно становятся намного меньше и намного быстрее, что позволяет быстро производить численное суммирование.

Преобразование Эйлера можно обобщить (Борисов Б., Шкодров В., 2007):

${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}{n+p \choose n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{n+p \choose n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+p+1}}},}$

где р = 0, 1, 2,…

Преобразование Эйлера также часто применяется к гипергеометрическому интегралу Эйлера . Здесь преобразование Эйлера принимает вид: ${\displaystyle \,_{2}F_{1}}$

${\displaystyle \,_{2}F_{1}(a,b;c;z)=(1-z)^{-b}\,_{2}F_{1}\left(c-a,b;c;{\frac {z}{z-1}}\right).}$

[ Обобщения на другие гипергеометрические ряды см. в ^{[1] .]}

Биномиальное преобразование и его вариант преобразования Эйлера примечательны своей связью с представлением числа в виде цепной дроби . Пусть имеется представление цепной дроби ${\displaystyle 0<x<1}$

${\displaystyle x=[0;a_{1},a_{2},a_{3},\cdots ]}$

затем

${\displaystyle {\frac {x}{1-x}}=[0;a_{1}-1,a_{2},a_{3},\cdots ]}$

и

${\displaystyle {\frac {x}{1+x}}=[0;a_{1}+1,a_{2},a_{3},\cdots ].}$

Экспоненциальная производящая функция

Для экспоненциальной производящей функции пусть

${\displaystyle {\overline {f}}(x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}}$

и

${\displaystyle {\overline {g}}(x)=\sum _{n=0}^{\infty }s_{n}{\frac {x^{n}}{n!}}}$

затем

${\displaystyle {\overline {g}}(x)=(T{\overline {f}})(x)=e^{x}{\overline {f}}(-x).}$

Преобразование Бореля преобразует обычную производящую функцию в экспоненциальную производящую функцию.

Биномиальная свертка

Пусть и , — последовательности комплексных чисел. Их биномиальная свертка определяется выражением ${\displaystyle \{a_{n}\}}$ ${\displaystyle \{b_{n}\}}$ ${\displaystyle n=0,1,2,\ldots ,}$

${\displaystyle (a\circ b)_{n}=\sum _{k=0}^{n}{n \choose k}a_{k}b_{n-k},\ \ n=0,1,2,\ldots }$

Эту свертку можно найти в книге Р. Л. Грэма, Д. Е. Кнута и О. Паташника: Конкретная математика: Фонд компьютерных наук, Аддисон-Уэсли (1989). Легко видеть, что биномиальная свертка ассоциативна и коммутативна, а последовательность, определяемая и for, служит тождеством при биномиальной свертке. Далее, легко видеть, что последовательности с обладают обратными. Таким образом, множество последовательностей с образует абелеву группу при биномиальной свертке. ${\displaystyle \{e_{n}\}}$ ${\displaystyle e_{0}=1}$ ${\displaystyle e_{n}=0}$ ${\displaystyle n=1,2,\ldots ,}$ ${\displaystyle \{a_{n}\}}$ ${\displaystyle a_{0}\neq 0}$ ${\displaystyle \{a_{n}\}}$ ${\displaystyle a_{0}\neq 0}$

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

${\displaystyle \left(\sum _{n=0}^{\infty }a_{n}{x^{n} \over n!}\right)\left(\sum _{n=0}^{\infty }b_{n}{x^{n} \over n!}\right)=\sum _{n=0}^{\infty }(a\circ b)_{n}{x^{n} \over n!}.}$

Биномиальное преобразование можно записать в терминах биномиальной свертки. Пусть и для всех . Затем ${\displaystyle \lambda _{n}=(-1)^{n}}$ ${\displaystyle 1_{n}=1}$ ${\displaystyle n}$

${\displaystyle (Ta)_{n}=(\lambda a\circ 1)_{n}.}$

Формула

${\displaystyle t_{n}=\sum _{k=0}^{n}(-1)^{n-k}{n \choose k}a_{k}\iff a_{n}=\sum _{k=0}^{n}{n \choose k}t_{k}}$

можно интерпретировать как формулу типа обращения Мёбиуса

${\displaystyle t_{n}=(a\circ \lambda )_{n}\iff a_{n}=(t\circ 1)_{n}}$

поскольку является обратным биномиальной свертке. ${\displaystyle \lambda _{n}}$ ${\displaystyle 1_{n}}$

В математической литературе существует еще одна биномиальная свертка. Биномиальная свертка арифметических функций и определяется как ${\displaystyle f}$ ${\displaystyle g}$

${\displaystyle (f\circ _{B}g)(n)=\sum _{d\mid n}\left(\prod _{p}{\binom {\nu _{p}(n)}{\nu _{p}(d)}}\right)f(d)g(n/d),}$

где – каноническая факторизация натурального числа , – биномиальный коэффициент. Эта свертка появляется в книге П. Дж. Маккарти (1986) и далее изучается Л. Тотом и П. Хаукканеном (2009). ${\displaystyle n=\prod _{p}p^{\nu _{p}(n)}}$ ${\displaystyle n}$ ${\displaystyle {\binom {\nu _{p}(n)}{\nu _{p}(d)}}}$

Интегральное представление

Если последовательность можно интерполировать с помощью комплексной аналитической функции, то биномиальное преобразование последовательности можно представить с помощью интеграла Нёрлунда – Райса от интерполирующей функции.

Обобщения

Продингер предлагает аналогичное модульное преобразование: позволяя

${\displaystyle u_{n}=\sum _{k=0}^{n}{n \choose k}a^{k}(-c)^{n-k}b_{k}}$

дает

${\displaystyle U(x)={\frac {1}{cx+1}}B\left({\frac {ax}{cx+1}}\right)}$

где U и B — обычные производящие функции, связанные с рядами и соответственно. ${\displaystyle \{u_{n}\}}$ ${\displaystyle \{b_{n}\}}$

Восходящее k- биномиальное преобразование иногда определяют как

${\displaystyle \sum _{j=0}^{n}{n \choose j}j^{k}a_{j}.}$

Падающее k- биномиальное преобразование:

${\displaystyle \sum _{j=0}^{n}{n \choose j}j^{n-k}a_{j}}$.

Оба являются гомоморфизмами ядра преобразования Ганкеля ряда .

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

${\displaystyle \sum _{i=0}^{n}(-1)^{n-i}{\binom {n}{i}}a_{i}=b_{n}.}$

Пусть это будет равна функции ${\displaystyle {\mathfrak {J}}(a)_{n}=b_{n}.}$

Если создана новая таблица прямых разностей и первые элементы из каждой строки этой таблицы взяты для формирования новой последовательности , то второе биномиальное преобразование исходной последовательности будет: ${\displaystyle \{b_{n}\}}$

${\displaystyle {\mathfrak {J}}^{2}(a)_{n}=\sum _{i=0}^{n}(-2)^{n-i}{\binom {n}{i}}a_{i}.}$

Если один и тот же процесс повторяется k раз, то отсюда следует, что

${\displaystyle {\mathfrak {J}}^{k}(a)_{n}=b_{n}=\sum _{i=0}^{n}(-k)^{n-i}{\binom {n}{i}}a_{i}.}$

Его обратная сторона:

${\displaystyle {\mathfrak {J}}^{-k}(b)_{n}=a_{n}=\sum _{i=0}^{n}k^{n-i}{\binom {n}{i}}b_{i}.}$

Это можно обобщить как:

${\displaystyle {\mathfrak {J}}^{k}(a)_{n}=b_{n}=(\mathbf {E} -k)^{n}a_{0}}$

где оператор сдвига . ${\displaystyle \mathbf {E} }$

Его обратная сторона

${\displaystyle {\mathfrak {J}}^{-k}(b)_{n}=a_{n}=(\mathbf {E} +k)^{n}b_{0}.}$

Смотрите также

• серия Ньютон
• Матрица Ханкеля
• Преобразование Мёбиуса
• Преобразование Стирлинга
• суммирование Эйлера
• Биномиальный QMF
• Интеграл Римана – Лиувилля
• Список факториальных и биномиальных тем

Рекомендации

1. Миллер, Аллен Р.; Париж, РБ (2010). «Преобразования типа Эйлера для обобщенной гипергеометрической функции». З. Энджью. Математика. Физ . 62 (1): 31–45. дои : 10.1007/s00033-010-0085-0. S2CID  30484300.

• Джон Х. Конвей и Ричард К. Гай, 1996, Книга чисел.
• Дональд Э. Кнут, Искусство компьютерного программирования Том. 3 , (1973) Аддисон-Уэсли, Ридинг, Массачусетс.
• Хельмут Продингер, 1992, Некоторая информация о биномиальном преобразовании. Архивировано 12 марта 2007 г. в Wayback Machine.
• Спайви, Майкл З.; Стейл, Лаура Л. (2006). «K-биномиальные преобразования и преобразование Ханкеля». Журнал целочисленных последовательностей . 9 :06.1.1. Бибкод : 2006JIntS...9...11S.
• Борисов Б.; Шкодров, В. (2007). «Расходящиеся ряды в обобщенном биномиальном преобразовании». Адв. Стад. Продолжение Математика . 14 (1): 77–82.
• Христо Н. Бояджиев, Заметки о биномиальном преобразовании , теории и таблице с приложением о преобразовании Стирлинга (2018), World Scientific.
• Р. Л. Грэм, Д. Е. Кнут и О. Паташник: Конкретная математика: фонд компьютерных наук, Аддисон-Уэсли (1989).
• П. Дж. Маккарти, Введение в арифметические функции, Springer-Verlag, 1986.
• П. Хаукканен, О биномиальной свертке арифметических функций, Nieuw Arch. Виск. (IV) 14 (1996), вып. 2, 209–216.
• Л. Тот и П. Хаукканен, О биномиальной свертке арифметических функций, J. Combinatorics and Number Theory 1 (2009), 31–48.

Внешние ссылки

• Биномиальное преобразование
• Преобразования целочисленных последовательностей