Белловские полиномы

Полиномы в комбинаторной математике

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

Определения

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

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

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

${\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 {\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- м полным экспоненциальным полиномом Белла .

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

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

${\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 _{n − 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})=\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}},}$

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

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

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

{{А}, {Б, В}}

{{Б}, {А, С}}

{{С}, {Б, А}}

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

${\displaystyle 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 указывает на то, что в одном разбиении имеется j таких блоков размера i . Здесь тот факт, что и x ₁ , и x ₂ имеют показатель степени 1, указывает на то, что в данном разбиении имеется только один такой блок. Коэффициент монома указывает , сколько таких разбиений имеется. Здесь имеется 3 разбиения набора с 3 элементами на 2 блока, где в каждом разбиении элементы разделены на два блока размером 1 и 2.

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

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

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

Сумма нижних индексов в одночлене равна общему числу элементов. Таким образом, число одночленов, которые появляются в частичном многочлене Белла, равно числу способов, которыми целое число 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 1 _раз , «2» встречается j ₂ раз и т. д., то число разбиений множества размера n , которые сжимаются до этого разбиения целого числа n , когда члены множества становятся неразличимыми, является соответствующим коэффициентом в многочлене.

Примеры

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

${\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 способов разбить набор из 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}}$

потому что способы разбиения набора из 6 элементов на 3 блока следующие:

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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

Когда , ${\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 )}.}$

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

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

Производные

Частные производные полных полиномов Белла определяются как ^[4]

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

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

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

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

${\displaystyle {\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 ₂ ,...) на последовательности факториалов равно беззнаковому числу Стирлинга первого рода :

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

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

${\displaystyle 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 ₂ ,...) на последовательности единиц равно числу Стирлинга второго рода :

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

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

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

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

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

Полином Тушара можно выразить как значение полного полинома Белла для всех аргументов, равных x : ${\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).}$

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

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

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

В более общем смысле, ^{[5] [6]} учитывая некоторую функцию, допускающую обратную , ${\displaystyle f}$ ${\displaystyle g=f^{-1}}$

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

Определительные формы

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

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

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

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

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

Границы суммирования — 1 и n  − 1, а не 0 и n .

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

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

Тогда ^[2]

${\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,3,\ldots ,n-k+1)={\binom {n}{k}}k^{n-k}}$что дает идемпотентное число .
• ${\displaystyle 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})}$.
• Полные полиномы Белла удовлетворяют соотношению биномиального типа:

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

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

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

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

Примеры

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

${\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=0}^{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=0}^{\infty }{b_{n} \over n!}x^{n}.}$

Затем

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

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

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

Реверсия серии

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

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

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

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

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

${\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; и что разложение f может быть дифференцировано почленно. Тогда теорема Лапласа–Эрдели утверждает, что асимптотическое разложение интеграла I ( λ ) задается выражением

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Mathematica как BellY
• Maple как IncompleteBellB
• SageMath как bell_polynomial

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

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

Примечания

1. Комет 1974.
2. Cvijović 2011.
3. Алексеев, Пологова и Алексеев 2017, разд. 4.2.
4. Белл 1934, тождество (5.1) на стр. 266.
5. Chou, W.-S.; Hsu, Leetsch C.; Shiue, Peter J.-S. (2006-06-01). "Применение формулы Фаа ди Бруно в характеризации обратных отношений". Журнал вычислительной и прикладной математики . 190 (1–2): 151–169. doi : 10.1016/j.cam.2004.12.041 .
6. Чу, Вэньчан (19 ноября 2021 г.). «Многочлены Белла и нелинейные обратные отношения». Электронный журнал комбинаторики . 28 (4). doi : 10.37236/10390 . ISSN  1077-8926.
7. Comtet 1974, тождество [3l"] на стр. 136.
8. Хараламбидес 2002, стр. 437, уравнение (11.43).

Ссылки

• Аббас, М.; Буруби, С. (2005). «О новых тождествах для полинома Белла». Дискретная математика . 293 (1–3): 5–10. doi : 10.1016/j.disc.2004.08.023 . MR  2136048.
• Алексеев, Н.; Пологова, А.; Алексеев, МА (2017). «Обобщенные числа Хультмана и структуры циклов графов точек останова». Журнал вычислительной биологии . 24 (2): 93–105. arXiv : 1503.05285 . doi :10.1089/cmb.2016.0190. PMID  28045556. S2CID  9678733.
• Эндрюс, GE (1998). Теория разбиений . Кембриджская математическая библиотека (1-е изд.). Cambridge University Press . стр. 204–211. ISBN 0-521-63766-X.
• Белл, ET (1927–1928). «Разбиение многочленов». Annals of Mathematics . 29 (1/4): 38–46. doi :10.2307/1967979. JSTOR  1967979. MR  1502817.
• Белл, ET (1934). «Экспоненциальные многочлены». Annals of Mathematics . 35 (2): 258–277. doi :10.2307/1968431. JSTOR  1968431. MR  1503161.
• Бояджиев, КН (2009). «Экспоненциальные многочлены, числа Стирлинга и оценка некоторых гамма-интегралов». Abstract and Applied Analysis . 2009 : 1–18. arXiv : 0909.0979 . Bibcode : 2009AbApA2009....1B. doi : 10.1155/2009/168672 . S2CID  1608664.(содержит также элементарный обзор концепции полиномов Белла)
• Charalambides, CA (2002). Перечислительная комбинаторика . Chapman & Hall / CRC. стр. 632. ISBN 9781584882909.
• Контет, Л. (1974). Advanced Combinatorics: The Art of Finite and Infinite Expansions. Дордрехт, Голландия / Бостон, США: Reidel Publishing Company. Архивировано из оригинала 2017-06-01 . Получено 2019-07-02 .
• Cvijović, D. (2011). "Новые тождества для частичных полиномов Белла" (PDF) . Applied Mathematics Letters . 24 (9): 1544–1547. doi :10.1016/j.aml.2011.03.043. S2CID  45311678. Архивировано (PDF) из оригинала 2020-03-09 . Получено 2020-06-05 .
• Гриффитс, М. (2012). "Семейства последовательностей из класса многочленных сумм". Журнал целочисленных последовательностей . 15 : Статья 12.1.8. MR  2872465. Архивировано из оригинала 2014-05-02 . Получено 2012-06-27 .
• Кручинин, В. В. (2011). «Вывод полиномов Белла второго рода». arXiv : 1104.5065 [math.CO].
• Noschese, S.; Ricci, PE (2003). «Дифференциация многомерных составных функций и полиномы Белла». Журнал вычислительного анализа и приложений . 5 (3): 333–340. doi :10.1023/A:1023227705558. S2CID  118361207.
• Роман, С. (2013). The Umbral Calculus . Dover Publications . стр. 208. ISBN 9780486153421.
• Воинов, В.Г.; Никулин, М.С. (1994). «О степенных рядах, полиномах Белла, задаче Харди–Рамануджана–Радемахера и ее статистических приложениях». Кибернетика . 30 (3): 343–358. ISSN  0023-5954.