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

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

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

${\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 — бесконечномерный оператор с матричными элементами T _nk . Преобразование является инволюцией , то есть,

${\displaystyle ТТ=1}$

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

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

где дельта Кронекера . Исходный ряд может быть восстановлен${\displaystyle \delta _{нм}}$

${\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}.}$

В этом случае первое преобразование называется обратным биномиальным преобразованием , а второе — просто биномиальным преобразованием . Это стандартное использование, например, в On-Line Encyclopedia of Integer Sequences .

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

Каждая строка является разностью предыдущей строки. ( 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} .)

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

Верхняя строка, прочитанная справа налево, имеет вид { 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 }$

Эту свертку можно найти в книге RL Graham, DE Knuth и O. Patashnik: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley (1989). Легко видеть, что биномиальная свертка ассоциативна и коммутативна, а последовательность, определенная с помощью и для , служит тождеством при биномиальной свертке. Кроме того, легко видеть, что последовательности с обладают обратной функцией. Таким образом, множество последовательностей с образует абелеву группу при биномиальной свертке. ${\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),}$

где — каноническая факторизация положительного целого числа , а — биномиальный коэффициент. Эта свертка появляется в книге PJ McCarthy (1986) и была дополнительно изучена L. Toth и P. Haukkanen (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
• Интеграл Римана–Лиувилля
• Список тем по факториалу и биному

• Джон Х. Конвей и Ричард К. Гай, 1996, Книга Чисел
• Дональд Э. Кнут, Искусство программирования , том 3 , (1973) Эддисон-Уэсли, Рединг, Массачусетс.
• Хельмут Продингер, Некоторые сведения о биномиальном преобразовании, The Fibonacci Quarterly 32 (1994), 412-415.
• Spivey, Michael Z.; Steil, Laura L. (2006). "K-биномиальные преобразования и преобразование Ганкеля". Журнал целочисленных последовательностей . 9 : 06.1.1. Bibcode : 2006JIntS...9...11S.
• Борисов, Б.; Шкодров, В. (2007). «Расходящиеся ряды в обобщенном биномиальном преобразовании». Adv. Stud. Cont. Math . 14 (1): 77– 82.
• Христо Н. Бояджиев, Заметки о биномиальном преобразовании , теория и таблица, с приложением о преобразовании Стирлинга (2018), World Scientific.
• RL Graham, DE Knuth и O. Patashnik: Конкретная математика: основа компьютерной науки, Addison-Wesley (1989).
• П. Дж. Маккарти, Введение в арифметические функции, Springer-Verlag, 1986.
• П. Хаукканен, О биномиальной свертке арифметических функций, Nieuw Arch. Виск. (IV) 14 (1996), вып. 2, 209–216.
• Л. Тот и П. Хаукканен, О биномиальной свертке арифметических функций, J. Combinatorics and Number Theory 1 (2009), 31-48.
• П. Хаукканен, Некоторые биномиальные инверсии в терминах обычных производящих функций. Publ. Math. Debr. 47, No. 1-2, 181-191 (1995).

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