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

Часткові або неповні експоненційні поліноми Белла — це трикутний масив поліномів, заданий

${\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_{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 B_{n}(x_{1},\dots ,x_{n})=\sum _{k=1}^{n}B_{n,k}(x_{1},x_{2},\dots ,x_{n-k+1})}$

називається 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})={\frac {k!}{n!}}B_{n,k}(1!\cdot x_{1},2!\cdot x_{2},\ldots ,(n-k+1)!\cdot x_{n-k+1}).}$

Як правило, під поліномами Белла маються на увазі експоненційні поліноми Белла, якщо не зазначено іншого.

Нехай, ми маємо

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

Таким чином, 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}.}$

Дивись також перетворення твірної функції для розкладу у ряд твірної функцій поліномів Белла що є композицією послідовностей твірних функцій та степенів, логаритмів та експоненційної функції, що послідовності твірних функцій. Кожна з цих формул можна знайти у відповідних розділах праці Комтета[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}&{n-1 \choose 4}x_{5}&\cdots &\cdots &x_{n}\\\\-1&x_{1}&{n-2 \choose 1}x_{2}&{n-2 \choose 2}x_{3}&{n-2 \choose 3}x_{4}&\cdots &\cdots &x_{n-1}\\\\0&-1&x_{1}&{n-3 \choose 1}x_{2}&{n-3 \choose 2}x_{3}&\cdots &\cdots &x_{n-2}\\\\0&0&-1&x_{1}&{n-4 \choose 1}x_{2}&\cdots &\cdots &x_{n-3}\\\\0&0&0&-1&x_{1}&\cdots &\cdots &x_{n-4}\\\\0&0&0&0&-1&\cdots &\cdots &x_{n-5}\\\\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\\\0&0&0&0&0&\cdots &-1&x_{1}\end{bmatrix}}.}$

Значення поліномів Белла 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].}$

Поліноми Белла 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 x_{n}=\sum _{k=1}^{n}(-1)^{k-1}(k-1)!B_{n,k}(y_{1},\ldots ,y_{n-k+1}).}$

то ми маємо таке зворотне співвідношення

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

Поліноми Тушара ${\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).}$

Для послідовностей 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.

Дозволяти ${\displaystyle x_{n}^{k\diamondsuit }\,}$ — n-й член послідовності

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

Нехай дві функції 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, то явна форма коефіцієнтів оберненої може бути задана в терміні многочленів Белла як[5]

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

з ${\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 e_{n}}$ і степеневий многочлен суми потужності ${\displaystyle p_{n}}$ можуть бути пов'язані один з одним за допомогою поліномів Белла як:

${\displaystyle {\begin{aligned}e_{n}&={\frac {(-1)^{n}}{n!}}\;B_{n}(p_{1},-1!p_{2},2!p_{3},-3!p_{4},\ldots ,(-1)^{n-1}(n-1)!p_{n}),\\[6pt]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 через сліди її потужностей:

${\displaystyle \det(A)={\frac {(-1)^{n}}{n!}}B_{n}(s_{1},s_{2},\ldots ,s_{n}),~\qquad {\text{where }}s_{k}=(-1)^{k-1}(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 \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!}}}$

з поліномами Белла.