Биномиальный тип

Тип полиномиальной последовательности

В математике полиномиальная последовательность , т. е. последовательность полиномов, индексированных неотрицательными целыми числами , в которой индекс каждого полинома равен его степени , называется биномиальной, если она удовлетворяет последовательности тождеств ${\textstyle \left\{0,1,2,3,\ldots \right\}}$

${\displaystyle p_{n}(x+y)=\sum _{k=0}^{n}{n \choose k}\,p_{k}(x)\,p_{n-k}(y).}$

Существует много таких последовательностей. Набор всех таких последовательностей образует группу Ли при операции теневой композиции , описанной ниже. Каждая последовательность биномиального типа может быть выражена в терминах полиномов Белла . Каждая последовательность биномиального типа является последовательностью Шеффера (но большинство последовательностей Шеффера не являются биномиальными). Полиномиальные последовательности прочно обосновали смутные понятия теневого исчисления 19-го века .

Примеры

• Вследствие этого определения биномиальную теорему можно сформулировать, сказав, что последовательность имеет биномиальный тип. ${\displaystyle \{x^{n}:n=0,1,2,\ldots \}}$
• Последовательность « нижних факториалов » определяется как (В теории специальных функций эта же нотация обозначает верхние факториалы , но это современное использование является универсальным среди комбинаториков .) Произведение понимается как 1, если n = 0, поскольку в этом случае это пустое произведение . Эта полиномиальная последовательность имеет биномиальный тип. ^[1] $${\displaystyle (x)_{n}=x(x-1)(x-2)\cdot \cdots \cdot (x-n+1).}$$
• Аналогично « верхние факториалы » представляют собой полиномиальную последовательность биномиального типа. $${\displaystyle x^{(n)}=x(x+1)(x+2)\cdot \cdots \cdot (x+n-1)}$$
• Полиномы Абеля представляют собой полиномиальную последовательность биномиального типа. $${\displaystyle p_{n}(x)=x(x-an)^{n-1}}$$
• Полиномы Тушара , где — число разбиений множества размера на непересекающиеся непустые подмножества , — это полиномиальная последовательность биномиального типа. Эрик Темпл Белл назвал их «экспоненциальными полиномами», и этот термин также иногда встречается в литературе. Коэффициенты — это « числа Стирлинга второго рода». Эта последовательность имеет любопытную связь с распределением Пуассона : если — случайная величина с распределением Пуассона с ожидаемым значением , то . В частности, когда , мы видим, что й момент распределения Пуассона с ожидаемым значением — это число разбиений множества размера , называемое й числом Белла . Этот факт о й моменте этого конкретного распределения Пуассона — « формула Добински ». $${\displaystyle p_{n}(x)=\sum _{k=0}^{n}S(n,k)x^{k}}$$ ${\displaystyle S(n,k)}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle S(n,k)}$ ${\displaystyle X}$ ${\displaystyle \lambda }$ ${\displaystyle E(X^{n})=p_{n}(\lambda )}$ ${\displaystyle \lambda =1}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Характеристика дельта-операторов

Можно показать, что полиномиальная последовательность { p _n (x) : n  = 0, 1, 2, … } имеет биномиальный тип тогда и только тогда, когда выполняются все три из следующих условий:

• Линейное преобразование в пространстве многочленов от x , характеризующееся тем, что является сдвигово-эквивариантным , и $${\displaystyle p_{n}(x)\mapsto np_{n-1}(x)}$$
• p ₀ ( x ) = 1 для всех x , и
• p _n (0) = 0 для n > 0.

(Утверждение, что этот оператор является сдвигово-эквивариантным, равносильно утверждению, что полиномиальная последовательность является последовательностью Шеффера ; множество последовательностей биномиального типа надлежащим образом включено в множество последовательностей Шеффера.)

Операторы Дельта

Это линейное преобразование, очевидно, является дельта-оператором , т.е. сдвигово-эквивариантным линейным преобразованием на пространстве многочленов от x, которое уменьшает степени многочленов на 1. Наиболее очевидными примерами дельта-операторов являются операторы разности ^[1] и дифференцирования . Можно показать, что каждый дельта-оператор может быть записан в виде степенного ряда вида

${\displaystyle Q=\sum _{n=1}^{\infty }c_{n}D^{n}}$

где D — дифференциация (обратите внимание, что нижняя граница суммирования равна 1). Каждый дельта-оператор Q имеет уникальную последовательность «базовых полиномов», т.е. полиномиальную последовательность, удовлетворяющую

1. ${\displaystyle p_{0}(x)=1,}$
2. ${\displaystyle p_{n}(0)=0\quad {\rm {for\ }}n\geq 1,{\rm {\ and}}}$
3. ${\displaystyle Qp_{n}(x)=np_{n-1}(x).}$

В 1973 году Рота , Каханером и Одлыжко показали , что полиномиальная последовательность имеет биномиальный тип тогда и только тогда, когда она является последовательностью базовых полиномов некоторого дельта-оператора. Таким образом, этот параграф представляет собой рецепт для генерации стольких полиномиальных последовательностей биномиального типа, сколько пожелаете.

Характеристика полиномами Белла

Для любой последовательности скаляров a ₁ , a ₂ , a ₃ , … пусть

${\displaystyle p_{n}(x)=\sum _{k=1}^{n}B_{n,k}(a_{1},\dots ,a_{n-k+1})x^{k}}$

где B _{n , k} ( a ₁ , …, a _{n − k +1} ) — многочлен Белла . Тогда эта многочленная последовательность имеет биномиальный тип. Обратите внимание, что для каждого n ≥ 1,

${\displaystyle p_{n}'(0)=a_{n}.}$

Вот основной результат этого раздела:

Теорема: Все полиномиальные последовательности биномиального типа имеют этот вид.

Результат Маллина и Роты, повторенный Ротой, Каханером и Одлыжко (см. Ссылки ниже), утверждает, что каждая полиномиальная последовательность {  p _n ( x ) } _n биномиального типа определяется последовательностью {  p _n ′(0) } _n , но эти источники не упоминают полиномы Белла.

Эта последовательность скаляров также связана с дельта-оператором. Пусть

${\displaystyle P(t)=\sum _{n=1}^{\infty }{a_{n} \over n!}t^{n}.}$

Затем

${\displaystyle P^{-1}\left({d \over dx}\right),}$

где , — дельта-оператор этой последовательности. ${\displaystyle P^{-1}(P(x))=P(P^{-1}(x))=1}$

Характеристика с помощью тождества свертки

Для последовательностей a _n , b _n , n = 0, 1, 2, …, определим вид свертки следующим образом:

${\displaystyle (a{\mathbin {\diamondsuit }}b)_{n}=\sum _{j=0}^{n}{n \choose j}a_{j}b_{n-j}.}$

Пусть будет n- м членом последовательности ${\displaystyle a_{n}^{k\diamondsuit }}$

${\displaystyle \underbrace {a\mathbin {\diamondsuit } \cdots \mathbin {\diamondsuit } a} _{k{\text{ factors}}}.}$

Тогда для любой последовательности a _i , i = 0, 1, 2, ..., при a ₀ = 0, последовательность, определяемая соотношением p ₀ ( x ) = 1 и

${\displaystyle p_{n}(x)=\sum _{k=1}^{n}{a_{n}^{k\diamondsuit }x^{k} \over k!}\,}$

при n ≥ 1 имеет биномиальный тип, и каждая последовательность биномиального типа имеет этот вид.

Характеристика с помощью производящих функций

Полиномиальные последовательности биномиального типа — это именно те, производящие функции которых являются формальными (не обязательно сходящимися ) степенными рядами вида

${\displaystyle \sum _{n=0}^{\infty }{p_{n}(x) \over n!}t^{n}=e^{xf(t)}}$

где f ( t ) — формальный степенной ряд , постоянный член которого равен нулю, а член первой степени не равен нулю. ^[2] С помощью версии степенного ряда формулы Фаа ди Бруно можно показать , что

${\displaystyle f(t)=\sum _{n=1}^{\infty }{p_{n}'(0) \over n!}t^{n}.}$

Дельта-оператор последовательности является композиционно обратным , так что ${\displaystyle f^{-1}(D)}$

${\displaystyle f^{-1}(D)p_{n}(x)=np_{n-1}(x).}$

Способ размышления об этих производящих функциях

Коэффициенты в произведении двух формальных степенных рядов

${\displaystyle \sum _{n=0}^{\infty }{a_{n} \over n!}t^{n}}$

и

${\displaystyle \sum _{n=0}^{\infty }{b_{n} \over n!}t^{n}}$

являются

${\displaystyle c_{n}=\sum _{k=0}^{n}{n \choose k}a_{k}b_{n-k}}$

(см. также произведение Коши ). Если мы думаем о x как о параметре, индексирующем семейство таких степенных рядов, то биномиальное тождество фактически говорит, что степенной ряд, индексированный x + y, является произведением рядов, индексированных x и y . Таким образом, x является аргументом функции, которая отображает суммы в произведения: показательная функция

${\displaystyle g(t)^{x}=e^{xf(t)}}$

где f ( t ) имеет вид, указанный выше.

Умбральная композиция полиномиальных последовательностей

Множество всех полиномиальных последовательностей биномиального типа представляет собой группу , в которой групповая операция — «теневая композиция» полиномиальных последовательностей. Эта операция определяется следующим образом. Предположим, что { p _n ( x ) : n = 0, 1, 2, 3, ... } и { q _n ( x ) : n = 0, 1, 2, 3, ... } — полиномиальные последовательности, и

${\displaystyle p_{n}(x)=\sum _{k=0}^{n}a_{n,k}\,x^{k}.}$

Тогда теневая композиция p o q представляет собой полиномиальную последовательность, n- й член которой равен

${\displaystyle (p_{n}\circ q)(x)=\sum _{k=0}^{n}a_{n,k}\,q_{k}(x)}$

(индекс n появляется в p _n , поскольку это n-й член этой последовательности, но не в q , поскольку он относится к последовательности в целом, а не к одному из ее членов).

При наличии дельта-оператора, определенного степенным рядом в D , как указано выше, естественная биекция между дельта-операторами и полиномиальными последовательностями биномиального типа, также определенными выше, является групповым изоморфизмом , в котором групповая операция над степенными рядами является формальной композицией формальных степенных рядов.

Кумулянты и моменты

Последовательность κ _n коэффициентов членов первой степени в полиномиальной последовательности биномиального типа можно назвать кумулянтами полиномиальной последовательности. Можно показать, что вся полиномиальная последовательность биномиального типа определяется своими кумулянтами, способом, обсуждаемым в статье под названием кумулянт . Таким образом

${\displaystyle p_{n}'(0)=\kappa _{n}=}$n - й кумулянт

и

${\displaystyle p_{n}(1)=\mu _{n}'=}$n -й момент.

Это «формальные» кумулянты и «формальные» моменты , в отличие от кумулянтов распределения вероятностей и моментов распределения вероятностей.

Позволять

${\displaystyle f(t)=\sum _{n=1}^{\infty }{\frac {\kappa _{n}}{n!}}t^{n}}$

быть (формальной) функцией, генерирующей кумулянт. Тогда

${\displaystyle f^{-1}(D)}$

— дельта-оператор, связанный с полиномиальной последовательностью, т.е. мы имеем

${\displaystyle f^{-1}(D)p_{n}(x)=np_{n-1}(x).}$

Приложения

Концепция биномиального типа находит применение в комбинаторике , теории вероятностей , статистике и ряде других областей.

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

• Список тем по факториалу и биному
• Биномиальный QMF (вейвлет-фильтры Добеши)

Ссылки

• G.-C. Rota , D. Kahaner и A. Odlyzko , «Конечно-операторное исчисление», Journal of Mathematical Analysis and its Applications , т. 42, № 3, июнь 1973 г. Перепечатано в книге с тем же названием, Academic Press, Нью-Йорк, 1975 г.
• Р. Маллин и Г.-К. Рота, «Об основах комбинаторной теории III: Теория биномиального перечисления», в книге «Теория графов и ее приложения » , под редакцией Бернарда Харриса, Academic Press, Нью-Йорк, 1970.
• Роман, Стивен (2008). Продвинутая линейная алгебра . Graduate Texts in Mathematics (Третье изд.). Springer. ISBN 978-0-387-72828-5.

Как следует из названия, вторая часть статьи посвящена приложениям к комбинаторному перечислению.

• ди Буккьянико, Алессандро. Вероятностные и аналитические аспекты теневого исчисления , Амстердам, CWI , 1997.
• Вайсштейн, Эрик В. «Последовательность биномиального типа». MathWorld .

1. Roman 2008, стр. 488-489, гл. 19.
2. Роман 2008, стр. 482-483, гл. 19.