Полиномы Белла - Bell polynomials

Для другого семейства многочленов B_п(Икс) иногда называемые полиномами Белла, см. Полиномы Тушара.

В комбинаторный математика, то Полиномы Белла, названный в честь Эрик Темпл Белл, используются при изучении множества разделов. Они связаны с Стирлинг и Номера звонков. Они также встречаются во многих приложениях, например, в Формула Фаа ди Бруно.

Полиномы Белла

Экспоненциальные полиномы Белла

В частичный или же неполный экспоненциальные полиномы Белла являются треугольная решетка многочленов, заданных

${\displaystyle B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})=\sum {n! \over j_{1}!j_{2}!\cdots j_{n-k+1}!}\left({x_{1} \over 1!}\right)^{j_{1}}\left({x_{2} \over 2!}\right)^{j_{2}}\cdots \left({x_{n-k+1} \over (n-k+1)!}\right)^{j_{n-k+1}},}$

где сумма берется по всем последовательностям j₁, j₂, j₃, ..., j_п−k+1 неотрицательных целых чисел, при которых выполняются эти два условия:

${\displaystyle j_{1}+j_{2}+\cdots +j_{n-k+1}=k,}$

${\displaystyle j_{1}+2j_{2}+3j_{3}+\cdots +(n-k+1)j_{n-k+1}=n.}$

Сумма

${\displaystyle B_{n}(x_{1},\dots ,x_{n})=\sum _{k=1}^{n}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}$

называется пth полный экспоненциальный полином Белла.

Обыкновенные полиномы Белла

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

${\displaystyle {\hat {B}}_{n,k}(x_{1},x_{2},\ldots ,x_{n-k+1})=\sum {\frac {k!}{j_{1}!j_{2}!\cdots j_{n-k+1}!}}x_{1}^{j_{1}}x_{2}^{j_{2}}\cdots x_{n-k+1}^{j_{n-k+1}},}$

где сумма пробегает все последовательности j₁, j₂, j₃, ..., j_п−k+1 неотрицательных целых чисел, таких что

${\displaystyle j_{1}+j_{2}+\cdots +j_{n-k+1}=k,}$

${\displaystyle j_{1}+2j_{2}+\cdots +(n-k+1)j_{n-k+1}=n.}$

Обычные многочлены Белла могут быть выражены через экспоненциальные многочлены Белла:

${\displaystyle {\hat {B}}_{n,k}(x_{1},x_{2},\ldots ,x_{n-k+1})={\frac {k!}{n!}}B_{n,k}(1!\cdot x_{1},2!\cdot x_{2},\ldots ,(n-k+1)!\cdot x_{n-k+1}).}$

В общем, многочлен Белла относится к экспоненциальному многочлену Белла, если явно не указано иное.

Комбинаторное значение

Экспоненциальный полином Белла кодирует информацию, относящуюся к способам разделения множества. Например, если мы рассмотрим набор {A, B, C}, его можно разделить на два непустых, неперекрывающихся подмножества, которые также называются частями или блоками, тремя разными способами:

{{A}, {B, C}}

{{B}, {A, C}}

{{C}, {B, A}}

Таким образом, мы можем закодировать информацию об этих разделах как

${\displaystyle B_{3,2}(x_{1},x_{2})=3x_{1}x_{2}.}$

Здесь индексы B_3,2 сообщает нам, что мы рассматриваем разбиение набора из 3 элементов на 2 блока. Нижний индекс каждого Икс_я указывает на наличие блока с я элементы (или блок размера я) в данном разделе. Так вот, Икс₂ указывает на наличие блока с двумя элементами. По аналогии, Икс₁ указывает на наличие блока с одним элементом. Показатель Икс_я^j указывает, что есть j такие блоки размера я в одном разделе. Здесь, поскольку оба Икс₁ и Икс₂ имеет экспоненту 1, это означает, что в данном разделе есть только один такой блок. Коэффициент одночлен указывает, сколько существует таких разделов. В нашем случае есть 3 раздела набора из 3 элементов на 2 блока, где в каждом разделе элементы разделены на два блока размером 1 и 2.

Поскольку любой набор можно разделить на единый блок только одним способом, приведенная выше интерпретация будет означать, что B_п,1 = Икс_п. Точно так же, поскольку существует только один способ, которым набор с п элементы можно разделить на п синглтоны B_п,п = Икс₁^п.

В качестве более сложного примера рассмотрим

${\displaystyle B_{6,2}(x_{1},x_{2},x_{3},x_{4},x_{5})=6x_{5}x_{1}+15x_{4}x_{2}+10x_{3}^{2}.}$

Это говорит нам о том, что если набор из 6 элементов разделен на 2 блока, то у нас может быть 6 разделов с блоками размера 1 и 5, 15 разделов с блоками размера 4 и 2 и 10 разделов с 2 блоками размера 3.

Сумма индексов в одночленах равна общему количеству элементов. Таким образом, количество одночленов, которые входят в частичный многочлен Белла, равно количеству способов, которыми целое число п можно выразить как сумму k положительные целые числа. Это то же самое, что и целочисленный раздел из п в k части. Например, в приведенных выше примерах целое число 3 можно разделить на две части только как 2 + 1. Таким образом, имеется только один моном в B_3,2. Однако целое число 6 можно разделить на две части: 5 + 1, 4 + 2 и 3 + 3. Таким образом, есть три одночлена в B_6,2. В самом деле, индексы переменных в одночлене такие же, как и в целочисленном разбиении, указывая размеры различных блоков. Общее количество одночленов, входящих в полный многочлен Белла B_п таким образом, равно общему количеству целых разбиенийп.

Также степень каждого монома, которая представляет собой сумму показателей каждой переменной в мономе, равна количеству блоков, на которые разделен набор. То есть, j₁ + j₂ + ... = k . Таким образом, для полного полинома Белла B_п, можно выделить частичный полином Белла B_{п, к} собрав все эти одночлены со степенью k.

Наконец, если не учитывать размеры блоков и поставить все Икс_я = Икс, то суммирование коэффициентов частичного полинома Белла B_п,k даст общее количество способов, которыми набор с п элементы можно разделить на k блоки, что совпадает с Числа Стирлинга второго рода. Кроме того, суммирование всех коэффициентов полного полинома Белла B_п даст нам общее количество способов, которыми набор с п элементы могут быть разделены на неперекрывающиеся подмножества, что совпадает с числом Белла.

В общем, если целое число п является разделенный в сумму, в которой фигурирует "1" j₁ раз появляется "2" j₂ раз и так далее, то количество перегородки набора размера п которые коллапсируют на этот раздел целого числа п когда члены множества становятся неразличимыми, это соответствующий коэффициент в полиноме.

Примеры

Например, у нас есть

${\displaystyle B_{6,2}(x_{1},x_{2},x_{3},x_{4},x_{5})=6x_{5}x_{1}+15x_{4}x_{2}+10x_{3}^{2}}$

потому что есть

6 способов разделить набор из 6 на 5 + 1,

15 способов разделить набор из 6 на 4 + 2 и

10 способов разделить набор из 6 на 3 + 3.

По аналогии,

${\displaystyle B_{6,3}(x_{1},x_{2},x_{3},x_{4})=15x_{4}x_{1}^{2}+60x_{3}x_{2}x_{1}+15x_{2}^{3}}$

потому что есть

15 способов разделить набор из 6 на 4 + 1 + 1,

60 способов разделить набор из 6 на 3 + 2 + 1, и

15 способов разделить набор из 6 на 2 + 2 + 2.

Характеристики

Производящая функция

Экспоненциальные частичные полиномы Белла могут быть определены двойным разложением его производящей функции в ряд:

${\displaystyle {\begin{aligned}\Phi (t,u)&=\exp \left(u\sum _{j=1}^{\infty }x_{j}{\frac {t^{j}}{j!}}\right)=\sum _{n\geq k\geq 0}B_{n,k}(x_{1},\ldots ,x_{n-k+1}){\frac {t^{n}}{n!}}u^{k}\\&=1+\sum _{n=1}^{\infty }{\frac {t^{n}}{n!}}\sum _{k=1}^{n}u^{k}B_{n,k}(x_{1},\ldots ,x_{n-k+1}).\end{aligned}}}$

Другими словами, то же самое - разложением в ряд k-я степень:

${\displaystyle {\frac {1}{k!}}\left(\sum _{j=1}^{\infty }x_{j}{\frac {t^{j}}{j!}}\right)^{k}=\sum _{n=k}^{\infty }B_{n,k}(x_{1},\ldots ,x_{n-k+1}){\frac {t^{n}}{n!}},\qquad k=0,1,2,\ldots }$

Полный экспоненциальный полином Белла определяется формулой ${\displaystyle \Phi (t,1)}$, или другими словами:

${\displaystyle \Phi (t,1)=\exp \left(\sum _{j=1}^{\infty }x_{j}{\frac {t^{j}}{j!}}\right)=\sum _{n=0}^{\infty }B_{n}(x_{1},\ldots ,x_{n}){\frac {t^{n}}{n!}}.}$

Таким образом п-й полный полином Белла имеет вид

${\displaystyle B_{n}(x_{1},\ldots ,x_{n})=\left.\left({\frac {\partial }{\partial t}}\right)^{n}\exp \left(\sum _{j=1}^{\infty }x_{j}{\frac {t^{j}}{j!}}\right)\right|_{t=0}.}$

Точно так же обычный частичный многочлен Белла может быть определен производящей функцией

${\displaystyle {\hat {\Phi }}(t,u)=\exp \left(u\sum _{j=1}^{\infty }x_{j}t^{j}\right)=\sum _{n\geq k\geq 0}{\hat {B}}_{n,k}(x_{1},\ldots ,x_{n-k+1})t^{n}{\frac {u^{k}}{k!}}.}$

Или, что то же самое, разложением в ряд k-я степень:

${\displaystyle \left(\sum _{j=1}^{\infty }x_{j}t^{j}\right)^{k}=\sum _{n=k}^{\infty }{\hat {B}}_{n,k}(x_{1},\ldots ,x_{n-k+1})t^{n}.}$

Смотрите также преобразования производящей функции для полинома Белла производящей функции разложения композиций последовательности производящие функции и полномочия, логарифмы, и экспоненты производящей функции последовательности. Каждая из этих формул цитируется в соответствующих разделах Comtet.^[1]

Повторяющиеся отношения

Полные полиномы Белла могут быть периодически определяется как

${\displaystyle B_{n+1}(x_{1},\ldots ,x_{n+1})=\sum _{i=0}^{n}{n \choose i}B_{n-i}(x_{1},\ldots ,x_{n-i})x_{i+1}}$

с начальным значением ${\displaystyle B_{0}=1}$.

Частичные полиномы Белла также можно эффективно вычислить с помощью рекуррентного соотношения:

${\displaystyle B_{n,k}=\sum _{i=1}^{n-k+1}{\binom {n-1}{i-1}}x_{i}B_{n-i,k-1},}$

куда

${\displaystyle B_{0,0}=1;}$

${\displaystyle B_{n,0}=0{\text{ for }}n\geq 1;}$

${\displaystyle B_{0,k}=0{\text{ for }}k\geq 1.}$

Полные многочлены Белла также удовлетворяют следующей рекуррентной дифференциальной формуле:^[2]

${\displaystyle {\begin{aligned}B_{n}(x_{1},\ldots ,x_{n})={\frac {1}{n-1}}\left[\sum _{i=2}^{n}\right.&\sum _{j=1}^{i-1}(i-1){\binom {i-2}{j-1}}x_{j}x_{i-j}{\frac {\partial B_{n-1}(x_{1},\dots ,x_{n-1})}{\partial x_{i-1}}}\\[5pt]&\left.{}+\sum _{i=2}^{n}\sum _{j=1}^{i-1}{\frac {x_{i+1}}{\binom {i}{j}}}{\frac {\partial ^{2}B_{n-1}(x_{1},\dots ,x_{n-1})}{\partial x_{j}\partial x_{i-j}}}\right.\\[5pt]&\left.{}+\sum _{i=2}^{n}x_{i}{\frac {\partial B_{n-1}(x_{1},\dots ,x_{n-1})}{\partial x_{i-1}}}\right].\end{aligned}}}$

Детерминантные формы

Полный полином Белла может быть выражен как детерминанты:

${\displaystyle B_{n}(x_{1},\dots ,x_{n})=\det {\begin{bmatrix}x_{1}&{n-1 \choose 1}x_{2}&{n-1 \choose 2}x_{3}&{n-1 \choose 3}x_{4}&\cdots &\cdots &x_{n}\\\\-1&x_{1}&{n-2 \choose 1}x_{2}&{n-2 \choose 2}x_{3}&\cdots &\cdots &x_{n-1}\\\\0&-1&x_{1}&{n-3 \choose 1}x_{2}&\cdots &\cdots &x_{n-2}\\\\0&0&-1&x_{1}&\cdots &\cdots &x_{n-3}\\\\0&0&0&-1&\cdots &\cdots &x_{n-4}\\\\\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\\\0&0&0&0&\cdots &-1&x_{1}\end{bmatrix}}}$

и

${\displaystyle B_{n}(x_{1},\dots ,x_{n})=\det {\begin{bmatrix}{\frac {x_{1}}{0!}}&{\frac {x_{2}}{1!}}&{\frac {x_{3}}{2!}}&{\frac {x_{4}}{3!}}&\cdots &\cdots &{\frac {x_{n}}{(n-1)!}}\\\\-1&{\frac {x_{1}}{0!}}&{\frac {x_{2}}{1!}}&{\frac {x_{3}}{2!}}&\cdots &\cdots &{\frac {x_{n-1}}{(n-2)!}}\\\\0&-2&{\frac {x_{1}}{0!}}&{\frac {x_{2}}{1!}}&\cdots &\cdots &{\frac {x_{n-2}}{(n-3)!}}\\\\0&0&-3&{\frac {x_{1}}{0!}}&\cdots &\cdots &{\frac {x_{n-3}}{(n-4)!}}\\\\0&0&0&-4&\cdots &\cdots &{\frac {x_{n-4}}{(n-5)!}}\\\\\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\\\0&0&0&0&\cdots &-(n-1)&{\frac {x_{1}}{0!}}\end{bmatrix}}.}$

Числа Стирлинга и числа Белла

Значение полинома Белла B_п,k(Икс₁,Икс₂, ...) на последовательности факториалы равно беззнаковому Число Стирлинга первого рода:

${\displaystyle B_{n,k}(0!,1!,\dots ,(n-k)!)=c(n,k)=|s(n,k)|=\left[{n \atop k}\right].}$

Значение полинома Белла B_п,k(Икс₁,Икс₂, ...) на последовательности единиц равно a Число Стирлинга второго рода:

${\displaystyle B_{n,k}(1,1,\dots ,1)=S(n,k)=\left\{{n \atop k}\right\}.}$

Сумма этих значений дает значение полного полинома Белла от последовательности единиц:

${\displaystyle B_{n}(1,1,\dots ,1)=\sum _{k=1}^{n}B_{n,k}(1,1,\dots ,1)=\sum _{k=1}^{n}\left\{{n \atop k}\right\},}$

какой пth Номер звонка.

Обратные отношения

Если мы определим

${\displaystyle y_{n}=\sum _{k=1}^{n}B_{n,k}(x_{1},\ldots ,x_{n-k+1}),}$

тогда у нас есть обратная зависимость

${\displaystyle x_{n}=\sum _{k=1}^{n}(-1)^{k-1}(k-1)!B_{n,k}(y_{1},\ldots ,y_{n-k+1}).}$

Полиномы Тушара

Основная статья: Полиномы Тушара

Многочлен Тушара ${\displaystyle T_{n}(x)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}\cdot x^{k}}$ может быть выражено как значение полного полинома Белла для всех аргументов Икс:

${\displaystyle T_{n}(x)=B_{n}(x,x,\dots ,x).}$

Свертка идентичности

Для последовательностей Икс_п, у_п, п = 1, 2, ..., определим свертка к:

${\displaystyle (x{\mathbin {\diamondsuit }}y)_{n}=\sum _{j=1}^{n-1}{n \choose j}x_{j}y_{n-j}.}$

Границы суммирования равны 1 и п - 1, а не 0 и п .

Позволять ${\displaystyle x_{n}^{k\diamondsuit }\,}$ быть п-й член последовательности

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

потом^[3]

${\displaystyle B_{n,k}(x_{1},\dots ,x_{n-k+1})={x_{n}^{k\diamondsuit } \over k!}.\,}$

Например, вычислим ${\displaystyle B_{4,3}(x_{1},x_{2})}$. У нас есть

${\displaystyle x=(x_{1}\ ,\ x_{2}\ ,\ x_{3}\ ,\ x_{4}\ ,\dots )}$

${\displaystyle x{\mathbin {\diamondsuit }}x=(0,\ 2x_{1}^{2}\ ,\ 6x_{1}x_{2}\ ,\ 8x_{1}x_{3}+6x_{2}^{2}\ ,\dots )}$

${\displaystyle x{\mathbin {\diamondsuit }}x{\mathbin {\diamondsuit }}x=(0\ ,\ 0\ ,\ 6x_{1}^{3}\ ,\ 36x_{1}^{2}x_{2}\ ,\dots )}$

и поэтому,

${\displaystyle B_{4,3}(x_{1},x_{2})={\frac {(x{\mathbin {\diamondsuit }}x{\mathbin {\diamondsuit }}x)_{4}}{3!}}=6x_{1}^{2}x_{2}.}$

Другие личности

• ${\displaystyle B_{n,k}(1!,2!,\ldots ,(n-k+1)!)={\binom {n-1}{k-1}}{\frac {n!}{k!}}=L(n,k)}$ что дает Номер Ла.
• ${\displaystyle B_{n,k}(1,2,3,\ldots ,n-k+1)={\binom {n}{k}}k^{n-k}}$ что дает идемпотентное число.
• ${\displaystyle B_{n,k}(-x_{1},x_{2},-x_{3},\ldots ,(-1)^{n-k}x_{n-k+1})=(-1)^{n}B_{n,k}(x_{1},x_{2},x_{3},\ldots ,x_{n-k+1})}$ и ${\displaystyle B_{n}(-x_{1},x_{2},-x_{3},\ldots ,(-1)^{n-1}x_{n})=(-1)^{n}B_{n}(x_{1},x_{2},x_{3},\ldots ,x_{n})}$.
• Полные полиномы Белла удовлетворяют соотношению биномиального типа:

  ${\displaystyle B_{n}(x_{1}+y_{1},\ldots ,x_{n}+y_{n})=\sum _{i=0}^{n}{n \choose i}B_{n-i}(x_{1},\ldots ,x_{n-i})B_{i}(y_{1},\ldots ,y_{i}),}$

  ${\displaystyle B_{n,k}{\Bigl (}{\frac {x_{q+1}}{\binom {q+1}{q}}},{\frac {x_{q+2}}{\binom {q+2}{q}}},\ldots {\Bigr )}={\frac {n!(q!)^{k}}{(n+qk)!}}B_{n+qk,k}(\ldots ,0,0,x_{q+1},x_{q+2},\ldots ).}$

Это исправляет пропуск фактора ${\displaystyle (q!)^{k}}$ в книге Контета.^[4]

• Когда ${\displaystyle 1\leq a<n}$,

${\displaystyle B_{n,n-a}(x_{1},\ldots ,x_{a+1})=\sum _{j=a+1}^{2a}{\frac {j!}{a!}}{\binom {n}{j}}(x_{1})^{n-j}B_{a,j-a}{\Bigl (}{\frac {x_{2}}{2}},{\frac {x_{3}}{3}},\ldots ,{\frac {x_{2(a+1)-j}}{2(a+1)-j}}{\Bigr )}.}$

• Частные случаи частичных полиномов Белла:

${\displaystyle {\begin{aligned}B_{n,1}(x_{1},\ldots ,x_{n})={}&x_{n}\\[8pt]B_{n,2}(x_{1},\ldots ,x_{n-1})={}&{\frac {1}{2}}\sum _{k=1}^{n-1}{\binom {n}{k}}x_{k}x_{n-k}\\[8pt]B_{n,n}(x_{1})={}&(x_{1})^{n}\\[8pt]B_{n,n-1}(x_{1},x_{2})={}&{\binom {n}{2}}(x_{1})^{n-2}x_{2}\\[8pt]B_{n,n-2}(x_{1},x_{2},x_{3})={}&{\binom {n}{3}}(x_{1})^{n-3}x_{3}+3{\binom {n}{4}}(x_{1})^{n-4}(x_{2})^{2}\\[8pt]B_{n,n-3}(x_{1},x_{2},x_{3},x_{4})={}&{\binom {n}{4}}(x_{1})^{n-4}x_{4}+10{\binom {n}{5}}(x_{1})^{n-5}x_{2}x_{3}+15{\binom {n}{6}}(x_{1})^{n-6}(x_{2})^{3}\\[8pt]B_{n,n-4}(x_{1},x_{2},x_{3},x_{4},x_{5})={}&{\binom {n}{5}}(x_{1})^{n-5}x_{5}+5{\binom {n}{6}}(x_{1})^{n-6}{\bigl [}3x_{2}x_{4}+2(x_{3})^{2}{\bigr ]}+105{\binom {n}{7}}(x_{1})^{n-7}(x_{2})^{2}x_{3}\\{}&{}+105{\binom {n}{8}}(x_{1})^{n-8}(x_{2})^{4}.\end{aligned}}}$

Примеры

Первые несколько полных полиномов Белла:

${\displaystyle {\begin{aligned}B_{0}={}&1,\\[8pt]B_{1}(x_{1})={}&x_{1},\\[8pt]B_{2}(x_{1},x_{2})={}&x_{1}^{2}+x_{2},\\[8pt]B_{3}(x_{1},x_{2},x_{3})={}&x_{1}^{3}+3x_{1}x_{2}+x_{3},\\[8pt]B_{4}(x_{1},x_{2},x_{3},x_{4})={}&x_{1}^{4}+6x_{1}^{2}x_{2}+4x_{1}x_{3}+3x_{2}^{2}+x_{4},\\[8pt]B_{5}(x_{1},x_{2},x_{3},x_{4},x_{5})={}&x_{1}^{5}+10x_{2}x_{1}^{3}+15x_{2}^{2}x_{1}+10x_{3}x_{1}^{2}+10x_{3}x_{2}+5x_{4}x_{1}+x_{5}\\[8pt]B_{6}(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})={}&x_{1}^{6}+15x_{2}x_{1}^{4}+20x_{3}x_{1}^{3}+45x_{2}^{2}x_{1}^{2}+15x_{2}^{3}+60x_{3}x_{2}x_{1}\\&{}+15x_{4}x_{1}^{2}+10x_{3}^{2}+15x_{4}x_{2}+6x_{5}x_{1}+x_{6},\\[8pt]B_{7}(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7})={}&x_{1}^{7}+21x_{1}^{5}x_{2}+35x_{1}^{4}x_{3}+105x_{1}^{3}x_{2}^{2}+35x_{1}^{3}x_{4}\\&{}+210x_{1}^{2}x_{2}x_{3}+105x_{1}x_{2}^{3}+21x_{1}^{2}x_{5}+105x_{1}x_{2}x_{4}\\&{}+70x_{1}x_{3}^{2}+105x_{2}^{2}x_{3}+7x_{1}x_{6}+21x_{2}x_{5}+35x_{3}x_{4}+x_{7}.\end{aligned}}}$

Приложения

Формула Фаа ди Бруно

Основная статья: Формула Фаа ди Бруно

Формула Фаа ди Бруно можно сформулировать в терминах полиномов Белла следующим образом:

${\displaystyle {d^{n} \over dx^{n}}f(g(x))=\sum _{k=1}^{n}f^{(k)}(g(x))B_{n,k}\left(g'(x),g''(x),\dots ,g^{(n-k+1)}(x)\right).}$

Точно так же версия формулы Фаа ди Бруно в виде степенного ряда может быть сформулирована с использованием полиномов Белла следующим образом. Предполагать

${\displaystyle f(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\qquad {\text{and}}\qquad g(x)=\sum _{n=1}^{\infty }{b_{n} \over n!}x^{n}.}$

потом

${\displaystyle g(f(x))=\sum _{n=1}^{\infty }{\frac {\sum _{k=1}^{n}b_{k}B_{n,k}(a_{1},\dots ,a_{n-k+1})}{n!}}x^{n}.}$

В частности, полные многочлены Белла появляются в экспоненте формальный степенной ряд:

${\displaystyle \exp \left(\sum _{i=1}^{\infty }{a_{i} \over i!}x^{i}\right)=\sum _{n=0}^{\infty }{B_{n}(a_{1},\dots ,a_{n}) \over n!}x^{n},}$

который также представляет экспоненциальная производящая функция полных многочленов Белла на фиксированной последовательности аргументов ${\displaystyle a_{1},a_{2},\dots }$.

Реверс серии

Основная статья: Теорема обращения Лагранжа

Пусть две функции ж и грамм быть выраженным в формальных степенных рядах как

${\displaystyle f(w)=\sum _{k=0}^{\infty }f_{k}{\frac {w^{k}}{k!}},\qquad {\text{and}}\qquad g(z)=\sum _{k=0}^{\infty }g_{k}{\frac {z^{k}}{k!}},}$

такой, что грамм композиционно инверсия ж определяется грамм(ж(ш)) = ш или же ж(грамм(z)) = z. Если ж₀ = 0 и ж₁ 0, то явный вид коэффициентов обратного может быть задан в терминах полиномов Белла как^[5]

${\displaystyle g_{n}={\frac {1}{f_{1}^{n}}}\sum _{k=1}^{n-1}(-1)^{k}n^{\bar {k}}B_{n-1,k}({\hat {f}}_{1},{\hat {f}}_{2},\ldots ,{\hat {f}}_{n-k}),\qquad n\geq 2,}$

с ${\displaystyle {\hat {f}}_{k}={\frac {f_{k+1}}{(k+1)f_{1}}},}$ и ${\displaystyle n^{\bar {k}}=n(n+1)\cdots (n+k-1)}$ - возрастающий факториал, и ${\displaystyle g_{1}={\frac {1}{f_{1}}}.}$

Асимптотическое разложение интегралов типа Лапласа

Рассмотрим интеграл вида

${\displaystyle I(\lambda )=\int _{a}^{b}e^{-\lambda f(x)}g(x)\,\mathrm {d} x,}$

куда (а,б) - действительный (конечный или бесконечный) интервал, λ - большой положительный параметр, а функции ж и грамм непрерывны. Позволять ж иметь единый минимум в [а,б], который происходит в Икс = а. Предположим, что при Икс → а⁺,

${\displaystyle f(x)\sim f(a)+\sum _{k=0}^{\infty }a_{k}(x-a)^{k+\alpha },}$

${\displaystyle g(x)\sim \sum _{k=0}^{\infty }b_{k}(x-a)^{k+\beta -1},}$

с α > 0, Re (β)> 0; и что расширение ж могут быть дифференцированы по срокам. Тогда теорема Лапласа – Эрдели утверждает, что асимптотическое разложение интеграла я(λ) дан кем-то

${\displaystyle I(\lambda )\sim e^{-\lambda f(a)}\sum _{n=0}^{\infty }\Gamma {\Big (}{\frac {n+\beta }{\alpha }}{\Big )}{\frac {c_{n}}{\lambda ^{(n+\beta )/\alpha }}}\qquad {\text{as}}\quad \lambda \rightarrow \infty ,}$

где коэффициенты c_п выражаются в терминах а_п и б_п с использованием частичного обычный Полиномы Белла, заданные формулой Кэмпбелла – Фромана – Валлеса – Войдило:

${\displaystyle c_{n}={\frac {1}{\alpha a_{0}^{(n+\beta )/\alpha }}}\sum _{k=0}^{n}b_{n-k}\sum _{j=0}^{k}{\binom {-{\frac {n+\beta }{\alpha }}}{j}}{\frac {1}{a_{0}^{j}}}{\hat {B}}_{k,j}(a_{1},a_{2},\ldots ,a_{k-j+1}).}$

Симметричные полиномы

Основная статья: Личности Ньютона

В элементарный симметричный многочлен ${\displaystyle e_{n}}$ и симметричный полином степенной суммы ${\displaystyle p_{n}}$ могут быть связаны друг с другом с помощью полиномов Белла следующим образом:

${\displaystyle {\begin{aligned}e_{n}&={\frac {1}{n!}}\;B_{n}(p_{1},-1!p_{2},2!p_{3},-3!p_{4},\ldots ,(-1)^{n-1}(n-1)!p_{n})\\&={\frac {(-1)^{n}}{n!}}\;B_{n}(-p_{1},-1!p_{2},-2!p_{3},-3!p_{4},\ldots ,-(n-1)!p_{n}),\end{aligned}}}$

${\displaystyle {\begin{aligned}p_{n}&={\frac {(-1)^{n-1}}{(n-1)!}}\sum _{k=1}^{n}(-1)^{k-1}(k-1)!\;B_{n,k}(e_{1},2!e_{2},3!e_{3},\ldots ,(n-k+1)!e_{n-k+1})\\&=(-1)^{n}\;n\;\sum _{k=1}^{n}{\frac {1}{k}}\;{\hat {B}}_{n,k}(-e_{1},\dots ,-e_{n-k+1}).\end{aligned}}}$

Эти формулы позволяют выразить коэффициенты монических многочленов через многочлены Белла его нулей. Например, вместе с Теорема Кэли – Гамильтона они приводят к выражению определителя п × п квадратная матрица А по следам его полномочий:

${\displaystyle \det(A)={\frac {(-1)^{n}}{n!}}B_{n}(s_{1},s_{2},\ldots ,s_{n}),~\qquad {\text{where }}s_{k}=-(k-1)!\operatorname {tr} (A^{k}).}$

Индекс цикла симметрических групп

Основная статья: Индекс цикла

В индекс цикла из симметричная группа ${\displaystyle S_{n}}$ может быть выражено через полные многочлены Белла следующим образом:

${\displaystyle Z(S_{n})={\frac {B_{n}(0!\,a_{1},1!\,a_{2},\dots ,(n-1)!\,a_{n})}{n!}}.}$

Моменты и кумулянты

Сумма

${\displaystyle \mu _{n}'=B_{n}(\kappa _{1},\dots ,\kappa _{n})=\sum _{k=1}^{n}B_{n,k}(\kappa _{1},\dots ,\kappa _{n-k+1})}$

это пй сырой момент из распределение вероятностей чей первый п кумулянты находятся κ₁, ..., κ_п. Другими словами, пй момент - это п-й полный многочлен Белла, вычисленный на первом п кумулянты. Точно так же пth кумулянт может быть задан в терминах моментов как

${\displaystyle \kappa _{n}=\sum _{k=1}^{n}(-1)^{k-1}(k-1)!B_{n,k}(\mu '_{1},\ldots ,\mu '_{n-k+1}).}$

Полиномы Эрмита

Вероятностные Полиномы Эрмита можно выразить через полиномы Белла как

${\displaystyle \operatorname {He} _{n}(x)=B_{n}(x,-1,0,\ldots ,0),}$

куда Икс_я = 0 для всех я > 2; таким образом позволяя комбинаторную интерпретацию коэффициентов многочленов Эрмита. В этом можно убедиться, сравнив производящую функцию многочленов Эрмита

${\displaystyle \exp \left(xt-{\frac {t^{2}}{2}}\right)=\sum _{n=0}^{\infty }\operatorname {He} _{n}(x){\frac {t^{n}}{n!}}}$

с полиномами Белла.

Представление полиномиальных последовательностей биномиального типа

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

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

Тогда эта полиномиальная последовательность имеет вид биномиальный тип, т.е. удовлетворяет биномиальному тождеству

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

Пример: За а₁ = … = а_п = 1, многочлены ${\displaystyle p_{n}(x)}$ представлять Полиномы Тушара.

В общем, мы имеем такой результат:

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

Если мы определим формальный степенной ряд

${\displaystyle h(x)=\sum _{k=1}^{\infty }{a_{k} \over k!}x^{k},}$

тогда для всех п,

${\displaystyle h^{-1}\left({d \over dx}\right)p_{n}(x)=np_{n-1}(x).}$

Программного обеспечения

Полиномы Белла реализованы в:

• Mathematica в качестве Живот
• Клен в качестве НеполныйBellB
• SageMath в качестве bell_polynomial

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

• Белл матрица
• Экспоненциальная формула

Примечания

1. Контет 1974.
2. Алексеев, Пологова, Алексеев 2017, разд. 4.2.
3. Цвийович 2011.
4. Контет 1974, тождество [31] на стр. 136.
5. Хараламбидес 2002, п. 437, уравнение (11.43).

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

• Аббас, М .; Буруби, С. (2005). «О новых тождествах для полинома Белла». Дискретная математика. 293 (1–3): 5–10. Дои:10.1016 / j.disc.2004.08.023. МИСТЕР  2136048.
• Алексеев, Н .; Пологова, А .; Алексеев, М.А. (2017). "Обобщенные числа Халтмана и циклические структуры графов точек останова". Журнал вычислительной биологии. 24 (2): 93–105. arXiv:1503.05285. Дои:10.1089 / cmb.2016.0190. PMID  28045556.
• Эндрюс, Г. Э. (1998). Теория перегородок. Кембриджская математическая библиотека (1-е изд.). Издательство Кембриджского университета. С. 204–211. ISBN  0-521-63766-X.
• Белл, Э. Т. (1927–1928). «Полиномы разбиения». Анналы математики. 29 (1/4): 38–46. Дои:10.2307/1967979. JSTOR  1967979. МИСТЕР  1502817.
• Бояджиев, К. Н. (2009). «Экспоненциальные многочлены, числа Стирлинга и оценка некоторых гамма-интегралов». Аннотация и прикладной анализ. 2009: 1–18. arXiv:0909.0979. Bibcode:2009АбАпА2009 .... 1Б. Дои:10.1155/2009/168672. (содержит также элементарный обзор понятия полиномов Белла)
• Хараламбидес, К. А. (2002). Перечислительная комбинаторика. Чепмен и Холл / CRC. п. 632. ISBN  9781584882909.
• Контет, Л. (1974). Продвинутая комбинаторика: искусство конечных и бесконечных расширений. Дордрехт, Голландия / Бостон, США: издательство Reidel Publishing Company. В архиве из оригинала на 2017-06-01. Получено 2019-07-02.
• Цвийович, Д. (2011). «Новые тождества для частичных многочленов Белла» (PDF). Письма по прикладной математике. 24 (9): 1544–1547. Дои:10.1016 / j.aml.2011.03.043. В архиве (PDF) из оригинала 2020-03-09. Получено 2020-06-05.
• Гриффитс, М. (2012). «Семейства последовательностей из класса полиномиальных сумм». Журнал целочисленных последовательностей. 15: Статья 12.1.8. МИСТЕР  2872465. В архиве из оригинала 2014-05-02. Получено 2012-06-27.
• Кручинин, В. В. (2011). «Вывод полиномов Белла второго рода». arXiv:1104.5065 [math.CO ].
• Noschese, S .; Риччи, П. Э. (2003). «Дифференцирование составных функций многих переменных и полиномов Белла». Журнал вычислительного анализа и приложений. 5 (3): 333–340. Дои:10.1023 / А: 1023227705558.
• Роман, С. (2013). Темное исчисление. Dover Publications. п. 208. ISBN  9780486153421.
• Воинов, В.Г .; Никулин, М. С. (1994). «О степенных рядах, многочленах Белла, проблеме Харди – Рамануджана – Радемахера и ее статистических приложениях». Кибернетика. 30 (3): 343–358. ISSN  0023-5954.