Биномиальное преобразование - Binomial transform
В комбинаторике , то биномиальное преобразование является преобразованием последовательности (то есть, преобразование в последовательности ) , которая вычисляет его вперед различия . Он тесно связан с преобразованием Эйлера , которое является результатом применения биномиального преобразования к последовательности, связанной с его обычной производящей функцией .
Определение
Биномиальное преобразование , Т , из последовательности { п }, является последовательностью { ы п } определяется
Формально можно написать
для преобразования, где T - бесконечномерный оператор с матричными элементами T nk . Преобразование является инволюцией , то есть
или, используя индексную нотацию,
где - дельта Кронекера . Исходную серию можно восстановить
Биномиальное преобразование последовательности - это просто n- е прямые разности последовательности, при этом нечетные разности имеют отрицательный знак, а именно:
где Δ - оператор прямой разности .
Некоторые авторы определяют биномиальное преобразование с дополнительным знаком, чтобы оно не было самообратным:
чье обратное
В этом случае первое преобразование называется обратным биномиальным преобразованием , а второе - просто биномиальным преобразованием . Это стандартное использование, например, в Он-лайн энциклопедии целочисленных последовательностей .
Пример
Обе версии биномиального преобразования появляются в таблицах различий. Рассмотрим следующую таблицу различий:
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 n −2 (2 m +1 n 2 + 2 m (1 + 6 m ) n + 2 m -1 9 m 2 ), и выполняется разностное уравнение 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 }.
Обычная производящая функция
Преобразование связывает производящие функции, связанные с серией. Для обычной производящей функции пусть
а также
тогда
Преобразование Эйлера
Связь между обычными производящими функциями иногда называют преобразованием Эйлера . Обычно он появляется одним из двух разных способов. В одной форме, она используется для ускорения сходимости в качестве знакопеременных рядов . То есть у человека есть личность
которое получается заменой x = 1/2 в последнюю формулу выше. Члены в правой части обычно становятся намного меньше, намного быстрее, что обеспечивает быстрое численное суммирование.
Преобразование Эйлера можно обобщить (Борисов Б., Шкодров В., 2007):
где p = 0, 1, 2,…
Преобразование Эйлера также часто применяется к гипергеометрическому интегралу Эйлера . Здесь преобразование Эйлера принимает вид:
Биномиальное преобразование и его вариация как преобразование Эйлера примечательны своей связью с представлением числа в виде непрерывной дроби . Пусть имеется представление в виде цепной дроби
тогда
а также
Экспоненциальная производящая функция
Для экспоненциальной производящей функции пусть
а также
тогда
Преобразование Бореля преобразует обычную производящую функцию в экспоненциальную производящую функцию.
Интегральное представление
Когда последовательность может быть интерполирована комплексной аналитической функцией, то биномиальное преобразование последовательности может быть представлено с помощью интеграла Норлунда – Райса на интерполирующей функции.
Обобщения
Продингер дает родственное, похожее на модульное преобразование: позволяя
дает
где U и B - обычные производящие функции, связанные с рядами и соответственно.
Поднимающееся k -биномиальное преобразование иногда определяют как
Падения к -binomial преобразования
- .
Оба гомоморфизмы ядра из Ганкеля преобразования серии .
В случае, когда биномиальное преобразование определяется как
Пусть это будет функция
Если создается новая таблица прямых различий и первые элементы из каждой строки этой таблицы берутся для формирования новой последовательности , то второе биномиальное преобразование исходной последовательности будет следующим:
Если один и тот же процесс повторяется k раз, то следует, что,
Его обратное,
Это можно обобщить как,
где - оператор сдвига .
Его обратное
Смотрите также
- Серия Ньютон
- Матрица Ганкеля
- Преобразование Мебиуса
- Преобразование Стирлинга
- Суммирование Эйлера
- Список факториальных и биномиальных тем
Рекомендации
- Джон Х. Конвей и Ричард К. Гай, 1996, Книга чисел
- Дональд Э. Кнут, Искусство компьютерного программирования, том. 3 , (1973) Addison-Wesley, Reading, MA.
- Хельмут Продингер, 1992, Некоторая информация о биномиальном преобразовании
- Майкл З. Спайви и Лаура Л. Стейл, 2006, k-биномиальные преобразования и преобразование Ханкеля
- Борисов Б., Шкодров В., 2007, Расходящиеся ряды в обобщенном биномиальном преобразовании, Adv. Stud. Продолж. Матем., 14 (1): 77-82.
- Христо Н. Бояджиев, Заметки о биномиальном преобразовании , теории и таблице, с приложением о преобразовании Стирлинга (2018), World Scientific.