Биномиальное преобразование - 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 раз, то следует, что,

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

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

где - оператор сдвига .

Его обратное

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

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

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