Биномиальное преобразование - Википедия - Binomial transform

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

Определение

В биномиальное преобразование, Т, последовательности, {а_п}, это последовательность {s_п} определяется

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

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

${ Displaystyle TT = 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}.}$

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

${ displaystyle s_ {0} = a_ {0}}$

${ displaystyle s_ {1} = - ( Delta a) _ {0} = - a_ {1} + a_ {0}}$

${ displaystyle s_ {2} = ( Delta ^ {2} a) _ {0} = - (- a_ {2} + a_ {1}) + (- a_ {1} + a_ {0}) = a_ {2} -2a_ {1} + a_ {0}}$

${ Displaystyle vdots ,}$

${ displaystyle s_ {n} = (- 1) ^ {n} ( Delta ^ {n} a) _ {0}}$

где Δ - оператор прямой разницы.

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

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

чье обратное

${ displaystyle 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

Верхняя строка 0, 1, 10, 63, 324, 1485, ... (последовательность, определяемая (2п² + п)3^п − 2) является (неинволютивной версией) биномиального преобразования диагонали 0, 1, 8, 36, 128, 400, ... (последовательность, определяемая п²2^п − 1).

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

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

${ Displaystyle е (х) = сумма _ {п = 0} ^ { infty} а_ {п} х ^ {п}}$

и

${ Displaystyle г (х) = сумма _ {п = 0} ^ { infty} s_ {п} х ^ {п}}$

тогда

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

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

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

${ displaystyle sum _ {n = 0} ^ { infty} (- 1) ^ {n} {n + p select 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 (ca, b; c; { frac {z} {z-1}} right).}$

Биномиальное преобразование и его вариация в виде преобразования Эйлера примечательны своей связью с непрерывная дробь представление числа. Позволять ${ Displaystyle 0 <х <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 u_ {n} = sum _ {k = 0} ^ {n} {n select 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 {и_ {п} }}$ и ${ 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) ^ {ni} { binom {n} {i }} a_ {i}.}$

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

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

Его обратное,

${ displaystyle { mathfrak {J}} ^ {- k} (b) _ {n} = a_ {n} = sum _ {i = 0} ^ {n} k ^ {ni} { 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}.}$

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

• Серия Ньютон
• Матрица Ганкеля
• Преобразование Мебиуса
• Преобразование Стирлинга
• Суммирование Эйлера
• Список факториальных и биномиальных тем

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

• Джон Х. Конвей и Ричард К. Гай, 1996, Книга чисел
• Дональд Э. Кнут, Искусство программирования Vol. 3(1973) Аддисон-Уэсли, Рединг, Массачусетс.
• Гельмут Продингер, 1992 г., Некоторая информация о биномиальном преобразовании
• Майкл З. Спайви и Лора Л. Стейл, 2006 г., K-биномиальные преобразования и преобразование Ханкеля
• Борисов Б., Шкодров В., 2007, Расходящиеся ряды в обобщенном биномиальном преобразовании, Adv. Stud. Продолж. Матем., 14 (1): 77-82.
• Христо Н. Бояджиев, Замечания о биномиальном преобразовании, Теория и таблица, с приложением о преобразовании Стирлинга (2018 г.), World Scientific.

внешняя ссылка

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