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

Для другого семейства полиномов B _n ( x ), иногда называемых полиномами Белла, см. Полиномы Тушара .

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

Определения

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

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

${\begin{aligned}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}}\\&=n!\sum \prod _{i=1}^{n-k+1}{\frac {x_{i}^{j_{i}}}{(i!)^{j_{i}}j_{i}!}},\end{aligned}}$

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

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

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

Сумма

${\begin{aligned}B_{n}(x_{1},\dots ,x_{n})&=\sum _{k=1}^{n}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})\\&=n!\sum _{1j_{1}+\ldots +nj_{n}=n}\prod _{i=1}^{n}{\frac {x_{i}^{j_{i}}}{(i!)^{j_{i}}j_{i}!}}\end{aligned}}$

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

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

Аналогично, частичный обычный полином Белла определяется формулой

${\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 _{n − k +1} таких неотрицательных целых чисел, что

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

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

Благодаря первому условию на индексы мы можем переписать формулу как

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

где мы использовали полиномиальный коэффициент .

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

${\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}, его можно разделить на два непустых, непересекающихся подмножества, которые также называются частями или блоками, тремя различными способами:

{{А}, {Б, С}}

{{В}, {А, С}}

{{С}, {Б, А}}

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

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

Здесь индексы B _3,2 говорят нам, что мы рассматриваем разбиение множества из 3 элементов на 2 блока. Нижний индекс каждого x _i указывает на наличие блока с i элементами (или блока размера i ) в данном разделе. Итак, здесь x ₂ указывает на наличие блока с двумя элементами. Аналогично, x ₁ указывает на наличие блока с одним элементом. Показатель степени x _i ^дж имеется j таких блоков размера i указывает, что в одном разделе . Здесь тот факт, что и x ₁ , и x ₂ имеют показатель степени 1, указывает на то, что в данном разделе есть только один такой блок. Коэффициент при мономе показывает, сколько таких разбиений имеется. Здесь имеется 3 разбиения набора по 3 элемента на 2 блока, где в каждом разделе элементы разбиты на два блока размеров 1 и 2.

Поскольку любое множество можно разделить на один блок только одним способом, приведенная выше интерпретация будет означать, что B _{n ,1} = x _n . набор из n Аналогично, поскольку существует только один способ разделить элементов на n одиночных элементов: B _{n , n} = x ₁ ^н .

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

$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 разделов с двумя блоками размера 3.

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

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

Наконец, если мы пренебрегаем размерами блоков и положим все x _i = x , то суммирование коэффициентов частичного полинома Белла B _{n , k} даст общее количество способов, которыми множество из n элементов может быть разделено на k блоков, что совпадает с числами Стирлинга второго рода . Кроме того, суммирование всех коэффициентов полного полинома Белла B _n даст нам общее количество способов разделения множества из n элементов на непересекающиеся подмножества, что совпадает с числом Белла.

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

Примеры

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

$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 способов разделить набор из 6 штук как 5 + 1,

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

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

Сходным образом,

$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}$

потому что способы разбить набор из 6 элементов на 3 блока

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

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

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

Таблица значений

Ниже приведен треугольный массив неполных полиномов Белла. $B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})$:

к н	0	1	2	3	4	5	6
0	$1$
1	$0$	$x_{1}$
2	$0$	$x_{2}$	$x_{1}^{2}$
3	$0$	$x_{3}$	$3x_{1}x_{2}$	$x_{1}^{3}$
4	$0$	$x_{4}$	$3x_{2}^{2}+4x_{1}x_{3}$	$6x_{1}^{2}x_{2}$	$x_{1}^{4}$
5	$0$	$x_{5}$	$10x_{2}x_{3}+5x_{1}x_{4}$	$15x_{1}x_{2}^{2}+10x_{1}^{2}x_{3}$	$10x_{1}^{3}x_{2}$	$x_{1}^{5}$
6	$0$	$x_{6}$	$10x_{3}^{2}+15x_{2}x_{4}+6x_{1}x_{5}$	$15x_{2}^{3}+60x_{1}x_{2}x_{3}+15x_{1}^{2}x_{4}$	$45x_{1}^{2}x_{2}^{2}+20x_{1}^{3}x_{3}$	$15x_{1}^{4}x_{2}$	$x_{1}^{6}$

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

Генерирующая функция

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

${\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 -й степени:

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

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

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

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

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

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

${\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 -й степени:

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

Рекуррентные отношения

Полные полиномы Белла можно рекуррентно определить как

$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}$

с начальной стоимостью $B_{0}=1$.

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

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

где

$B_{0,0}=1;$

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

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

Кроме того:

$B_{n,k_{1}+k_{2}}(x_{1},\ldots ,x_{n-k_{1}-k_{2}+1})={\frac {k_{1}!\,k_{2}!}{(k_{1}+k_{2})!}}\sum _{i=0}^{n}{\binom {n}{i}}B_{i,k_{1}}(x_{1},\ldots ,x_{i-k_{1}+1})B_{n-i,k_{2}}(x_{1},\ldots ,x_{n-i-k_{2}+1}).$

Полные полиномы Белла также удовлетворяют следующей рекуррентной дифференциальной формуле:

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

Производные

Частные производные полных полиномов Белла имеют вид

${\frac {\partial B_{n}}{\partial x_{i}}}(x_{1},\ldots ,x_{n})={\binom {n}{i}}B_{n-i}(x_{1},\ldots ,x_{n-i}).$

Аналогично, частные производные частных полиномов Белла задаются формулами

${\frac {\partial B_{n,k}}{\partial x_{i}}}(x_{1},\ldots ,x_{n-k+1})={\binom {n}{i}}B_{n-i,k-1}(x_{1},\ldots ,x_{n-i-k+2}).$

Если аргументы полиномов Белла являются одномерными функциями, можно использовать цепное правило для получения

${\frac {d}{dx}}\left(B_{n,k}(a_{1}(x),\cdots ,a_{n-k+1}(x))\right)=\sum _{i=1}^{n-k+1}{\binom {n}{i}}a_{i}'(x)B_{n-i,k-1}(a_{1}(x),\cdots ,a_{n-i-k+2}(x)).$

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

Значение полинома Белла B _{n , k} ( x ₁ , x ₂ ,...) на последовательности факториалов равно беззнаковому числу Стирлинга первого рода :

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

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

$B_{n}(0!,1!,\dots ,(n-1)!)=\sum _{k=1}^{n}B_{n,k}(0!,1!,\dots ,(n-k)!)=\sum _{k=1}^{n}\left[{n \atop k}\right]=n!.$

Значение полинома Белла B _{n , k} ( x ₁ , x ₂ ,...) на последовательности единиц равно числу Стирлинга второго рода :

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

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

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

что является n- м числом Белла .

$B_{n,k}(1!,2!,\ldots ,(n-k+1)!)={\binom {n-1}{k-1}}{\frac {n!}{k!}}=L(n,k)$

что дает число Лаха .

Полиномы

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

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

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

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

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

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

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

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

В более общем смысле, задана некоторая функция $f$ допуская обратное $g=f^{-1}$,

$y_{n}=\sum _{k=0}^{n}f^{(k)}(a)\,B_{n,k}(x_{1},\ldots ,x_{n-k+1})\quad \Leftrightarrow \quad x_{n}=\sum _{k=0}^{n}g^{(k)}{\big (}f(a){\big )}\,B_{n,k}(y_{1},\ldots ,y_{n-k+1}).$

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

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

$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}}$

и

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

Идентичность свертки

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

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

Границами суммирования являются 1 и n − 1, а не 0 и n .

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

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

Затем

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

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

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

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

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

и таким образом,

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

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

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

  $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}),$

  $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 ).$

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

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

  $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 )}.$

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

${\begin{aligned}B_{n,1}(x_{1},\ldots ,x_{n})={}&x_{n}\\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}\\B_{n,n}(x_{1})={}&x_{1}^{n}\\B_{n,n-1}(x_{1},x_{2})={}&{\binom {n}{2}}x_{1}^{n-2}x_{2}\\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}\\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}\\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}(3x_{2}x_{4}+2x_{3}^{2})+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}}$

Примеры

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

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

Приложения

Получить формулу Бруно

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

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

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

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

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

Затем

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

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

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

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

Реверс серии

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

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

$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!}},$

такой, что g является композиционной обратной функцией f, определенной формулой g ( f ( w )) = w или f ( g ( z )) = z . Если f ₀ = 0 и f ₁ ≠ 0, то явный вид коэффициентов обратного может быть задан через полиномы Белла как

$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,$

с ${\hat {f}}_{k}={\frac {f_{k+1}}{(k+1)f_{1}}},$ и $n^{\bar {k}}=n(n+1)\cdots (n+k-1)$ является восходящим факториалом, и $g_{1}={\frac {1}{f_{1}}}.$

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

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

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

где ( a , b ) — вещественный (конечный или бесконечный) интервал, λ — большой положительный параметр, а функции f и g непрерывны. Пусть f имеет единственный минимум в [ a , b ], который происходит в точке x = a . Предположим, что при x → a ⁺ ,

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

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

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

$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 _n выражаются через an _{с использованием} и bn _{полиномов Белла ,} частичных обычных как задано формулой Кэмпбелла – Фромана – Уоллеса – Войдило:

$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}).$

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

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

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

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

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

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

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

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

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

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

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

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

Сумма

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

— n-й необработанный момент распределения вероятностей , первые n кумулянтов которого равны κ ₁ , ..., κ _n . Другими словами, n- й момент — это n- й полный полином Белла, оцененный по первым n кумулянтам. Аналогично, n- й кумулянт может быть задан через моменты как

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример: Для a ₁ = … = a _n = 1 полиномы $p_{n}(x)$ представляют собой полиномы Тушара .

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

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

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

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

тогда для n всех

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

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

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

• Mathematica как BellY
• Клен как IncompleteBellB
• SageMath как bell_polynomial

См. также

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

Ссылки

• Аббас, М.; Буруби, С. (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 . ПМИД   28045556 . S2CID   9678733 .
• Эндрюс, GE (1998). Теория разделов . Кембриджская математическая библиотека (1-е изд. PBK). Издательство Кембриджского университета . стр. 204–211. ISBN  0-521-63766-Х .
• Белл, ET (1927–1928). «Полиномы разбиения». Анналы математики . 29 (1/4): 38–46. дои : 10.2307/1967979 . JSTOR   1967979 . МР   1502817 .
• Белл, ET (1934). «Экспоненциальные полиномы». Анналы математики . 35 (2): 258–277. дои : 10.2307/1968431 . JSTOR   1968431 . МР   1503161 .
• Бояджиев, К.Н. (2009). «Экспоненциальные полиномы, числа Стирлинга и вычисление некоторых гамма-интегралов» . Аннотация и прикладной анализ . 2009 : 1–18. arXiv : 0909.0979 . Бибкод : 2009AbApA2009....1B . дои : 10.1155/2009/168672 . S2CID   1608664 . (содержит также элементарный обзор понятия Белл-полиномы)
• Хараламбидес, Калифорния (2002). Перечислительная комбинаторика . Чепмен и Холл / CRC. п. 632. ИСБН  9781584882909 .
• Конте, Л. (1974). Продвинутая комбинаторика: искусство конечных и бесконечных расширений . Дордрехт, Голландия / Бостон, США: Издательская компания Reidel. Архивировано из оригинала 1 июня 2017 г. Проверено 02 июля 2019 г.
• Цвийович, Д. (2011). «Новые тождества для частичных полиномов Белла» (PDF) . Письма по прикладной математике . 24 (9): 1544–1547. дои : 10.1016/j.aml.2011.03.043 . S2CID   45311678 . Архивировано (PDF) из оригинала 9 марта 2020 г. Проверено 5 июня 2020 г.
• Гриффитс, М. (2012). «Семейства последовательностей из класса полиномиальных сумм» . Журнал целочисленных последовательностей . 15 : Статья 12.1.8. МР   2872465 . Архивировано из оригинала 2 мая 2014 г. Проверено 27 июня 2012 г.
• Кручинин, В.В. (2011). «Вывод полиномов Белла второго рода». arXiv : 1104.5065 [ math.CO ].
• Ношезе, С.; Риччи, ЧП (2003). «Дифференцирование составных функций многих переменных и полиномов Белла». Журнал вычислительного анализа и приложений . 5 (3): 333–340. дои : 10.1023/А:1023227705558 . S2CID   118361207 .
• Роман, С. (2013). Умбральное исчисление . Дуврские публикации . п. 208. ИСБН  9780486153421 .
• Воинов В.Г.; Никулин, М.С. (1994). «О степенных рядах, полиномах Белла, проблеме Харди – Рамануджана – Радемахера и ее статистических приложениях». Кибернетика . 30 (3): 343–358. ISSN   0023-5954 .