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

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

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

Биномиальное преобразование , Т , из последовательности { _п }, является последовательностью { ы _п } определяется

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

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

${\ 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) ^ {nk} {n \ select k} a_ {k}}$

чье обратное

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

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

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

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

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

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

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

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

и

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

где p = 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).}$

Биномиальное преобразование и его вариация в виде преобразования Эйлера примечательны своей связью с представлением числа в виде непрерывной дроби . Пусть имеет представление непрерывной дроби${\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 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}\}}$

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

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

Падения к -binomial преобразование

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

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

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

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

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

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

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