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

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

Определение [ править ]

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

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

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

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

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

TT=1

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

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

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

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

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

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

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

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

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

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

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

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

Пример [ править ]

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

0		1		10		63		324		1485
	1		9		53		261		1161
		8		44		208		900
			36		164		692
				128		528
					400

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

Обычная производящая функция [ править ]

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

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

и

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

затем

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

Преобразование Эйлера [ править ]

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

\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):

\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,…

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

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

[Видеть ^[1] для обобщений на другие гипергеометрические ряды.]

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

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

затем

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

и

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

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

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

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

и

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

затем

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

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

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

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

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

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

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

\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!}.

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

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

Формула

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}

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

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

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

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

(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),

где $n=\prod _{p}p^{\nu _{p}(n)}$ является канонической факторизацией натурального числа $n$ и ${\binom {\nu _{p}(n)}{\nu _{p}(d)}}$ - биномиальный коэффициент. Эта свертка появляется в книге П. Дж. Маккарти (Введение в арифметику).Функции, Springer-Verlag, 1986) и далее изучался Хаукканеном и Тотом (П. Хаукканен, О биномиальной свертке арифметических функций,Нью-Арк. Виск. (IV) 14 (1996), вып. 2, 209-216 и Л. Т\'{о}т и П. Хаукканен, О биномиальной свертке арифметических функций, J. Combinatorics and Number Theory 1 (2009), 31-48.

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

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

Обобщения [ править ]

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

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

дает

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

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

Джон Х. Конвей и Ричард К. Гай, 1996, Книга чисел.
Дональд Э. Кнут, Искусство компьютерного программирования, том. 3 , (1973) Аддисон-Уэсли, Ридинг, Массачусетс.
Хельмут Продингер, 1992, Некоторая информация о биномиальном преобразовании. Архивировано 12 марта 2007 г. в Wayback Machine.
Спайви, Майкл З.; Стейл, Лаура Л. (2006). «К-биномиальные преобразования и преобразование Ханкеля» . Журнал целочисленных последовательностей . 9 :06.1.1. Бибкод : 2006JIntS...9...11S .
Борисов Б.; Шкодров, В. (2007). «Расходящиеся ряды в обобщенном биномиальном преобразовании» . Адв. Стад. Продолжение Математика . 14 (1): 77–82.
Христо Н. Бояджиев, Заметки о биномиальном преобразовании , теории и таблице с приложением о преобразовании Стирлинга (2018), World Scientific.

Внешние ссылки [ править ]

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

[1]