Bellovy polynomy

V matematice , zejména v kombinatorice , jsou Bellovy polynomy polynomy tvaru

B_{n,k}(x_{1},x_{2},\tečky ,x_{n-k+1})=\součet {n!  \over j_{1}!j_{2}!\cdots j_{n-k+1}!}\left({x_{1} \over 1!}\right)^{j_{1}}\left( {x_{2} \přes 2!}\vpravo)^{j_{2}}\cdots \left({x_{n-k+1} \přes (n-k+1)!}\vpravo)^{ j_{n-k+1}},

kde součet přebírá všechny posloupnosti j 1 , j 2 , j 3 , ..., j n − k +1 nezáporných celých čísel tak, že

j_{1}+j_{2}+\cdots =k

j_{1}+2j_{2}+3j_{3}+\cdots =n.

Bellovy polynomy jsou pojmenovány po matematikovi E. Bellovi .

Kompletní Bellovy polynomy

Součet

B_{n}(x_{1},\tečky ,x_{n})=\sum _{k=1}^{n}B_{n,k}(x_{1},x_{2} ,\tečky ,x_{n-k+1})

někdy nazývaný n-tý kompletní Bellův polynom . Aby se to odlišilo od úplných Bellových polynomů, B n , k polynomy definované výše se někdy označují jako "částečné" Bellovy polynomy.

Kompletní Bellovy polynomy splňují následující podmínky:

B_{n}(x_{1},\tečky ,x_{n})=\det {\begin{bmatrix}x_{1}&{n-1 \choose 1}x_{2}&{n -1 \vyberte 2}x_{3}&{n-1 \vyberte 3}x_{4}&{n-1 \vyberte 4}x_{5}&\ctečky &\ctečky &x_{n}\\\\ -1&x_{1}&{n-2 \vyberte 1}x_{2}&{n-2 \vyberte 2}x_{3}&{n-2 \vyberte 3}x_{4}&\cdots &\cdots &x_{n-1}\\\\0&-1&x_{1}&{n-3 \vyberte 1}x_{2}&{n-3 \vyberte 2}x_{3}&\cdots &\cdots &x_{ n-2}\\\\0&0&-1&x_{1}&{n-4 \vyberte 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}}.

Kombinační výklad

Jestliže se v dělení čísla n objeví člen 1 j 1krát , 2 se objeví j 2krát atd., pak je počet oddílů množiny mohutnosti n , ve kterých mohutnosti částí tvoří toto rozdělení n , stejný . na odpovídající koeficient Bellova polynomu.

Příklady

Pro n = 6, k = 2 máme

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

protože to je

6 způsobů, jak rozdělit množinu mohutností 6 na podmnožiny mohutností 5 + 1,
15 způsobů, jak rozdělit množinu mohutností 6 na podmnožiny mohutností 4 + 2,
10 způsobů, jak rozdělit množinu mohutností 6 na podmnožiny mohutností 3 + 3.

Rovněž,

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}

protože to je

15 způsobů, jak rozdělit sadu mohutností 6 do podmnožin mohutností 4 + 1 + 1, 60 způsobů, jak rozdělit sadu mohutností 6 na podmnožiny mohutností 3 + 2 + 1 a 15 způsobů, jak rozdělit množinu mohutnosti 6 na podmnožiny mohutnosti 2 + 2 + 2.

Vlastnosti

$B_{n,k}(1!,2!,\tečky ,(n-k+1)!)={\binom {n}{k)){\binom {n-1}{k- 1}}(nk)!$

Vztah se Stirlingovými a Bellovými čísly

Hodnota Bellova polynomu B n , k ( x 1 , x 2 , …), kde všechna x i jsou rovna 1, je Stirlingovo číslo druhého druhu :

B_{n,k}(1,1,\tečky )=S(n,k)=\left\{{n \atop k}\right\}.

Součet

\sum _{k=1}^{n}B_{n,k}(1,1,1,\tečky )=\sum _{k=1}^{n}\left\{{n \atop k}\vpravo\}

je n-té Bellovo číslo (počet oddílů množiny mohutnosti n ).

Konvoluční identita

Pro posloupnost x n , y n , n = 1, 2, … je konvoluce definována :

(x\diamondsuit y)_{n}=\sum _{j=1}^{n-1}{n \vyberte j}x_{j}y_{nj}.

(Všimněte si, že limity součtu jsou zde 1 an − 1, nikoli 0 an .)

Předpokládejme, že existuje n-tý člen posloupnosti ${\displaystyle x_{n}^{k\diamondsuit ))$

\displaystyle \underbrace {x\diamondsuit \cdots \diamondsuit x} _{k\ \mathrm {factors} }.

Pak

B_{n,k}(x_{1},\tečky ,x_{n-k+1})={x_{n}^{k\diamondsuit } \over k!}.

Například spočítejme . Protože $B_{4,3}(x_{1},x_{2})$

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

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

x\diamondsuit x\diamondsuit x=(0,\ 0,\ ​​​​6x_{1}^{3},\ 36x_{1}^{2}x_{2},\ldots ),

pak

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

Aplikace

Vzorec Faa di Bruna

Vzorec Faa di Bruno může být formulován pomocí Bellových polynomů takto:

{d^{n} \over dx^{n}}f(g(x))=\sum _{k=0}^{n}f^{(k)}(g(x)) B_{n,k}\left(g'(x),g''(x),\tečky ,g^{(n-k+1)}(x)\vpravo).

Také můžeme použít Bellovy polynomy if

f(x)=\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\qquad

\qquad g(x)=\sum _{n=1}^{\infty }{b_{n} \over n!}x^{n},

pak

g(f(x))=\sum _{n=1}^{\infty }{\sum _{k=1}^{n}b_{k}B_{n,k}(a_{ 1},\tečky ,a_{n-k+1}) \přes n!}x^{n}.

Zejména úplné Bellovy polynomy se objevují v expanzi exponentu formální mocninné řady

\exp \left(\sum _{n=1}^{\infty }{a_{n} \over n!}x^{n}\right)=\sum _{n=0}^{ \infty }{B_{n}(a_{1},\tečky ,a_{n}) \over n!}x^{n}.

Momenty a kumulanty

Součet

B_{n}(\kappa _{1},\tečky ,\kappa _{n})=\sum _{k=1}^{n}B_{n,k}(\kappa _{1 },\tečky ,\kappa _{n-k+1})

je n-tý moment rozdělení pravděpodobnosti , jehož prvních n kumulantů se rovná κ 1 , … , κn . Jinými slovy, n-tý moment je roven hodnotě n-tého úplného Bellova polynomu na prvních n kumulantech.

Reprezentace polynomiálních posloupností binomického typu

Pro danou posloupnost čísel dáme a 1 , a 2 , a 3 , …

p_{n}(x)=\sum _{k=1}^{n}B_{n,k}(a_{1},\tečky ,a_{n-k+1})x^{ k}.

Pak je tato posloupnost polynomů binomického typu , tzn. splňuje binomické podmínky

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

pro n ≥ 0. Věta: Všechny polynomické posloupnosti binomického typu jsou reprezentovány v této podobě.

Pokud vezmeme v úvahu

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

jako formální mocninná řada, pak pro všechna n ,

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

Software

BellY polynomy, úplné Bellovy polynomy a zobecněné Bellovy polynomy jsou implementovány v Mathematica jako BellY Archived 20. března 2014 na Wayback Machine .

Zdroje

Eric Temple Bell . Partition Polynomials (neopr.) // Annals of Mathematics . — 1927–1928. - T. 29 , č. 1/4 . - S. 38-46 . - doi : 10.2307/1967979 . — .
Louis Compet . Advanced Combinatorics: The Art of Finite and Infinite Expansions (anglicky) . - Dordrecht, Holandsko / Boston, USA: Reidel Publishing Company, 1974.
Steven Roman Umbrální počet (neopr.) . — Doverské publikace .
Khristo N. Bojadžiev. Exponenciální polynomy, Stirlingova čísla a vyhodnocení některých gama integrálů // Abstraktní a aplikovaná analýza : deník. - 2009. - Sv. 2009 _ — P. ID článku 168672 . - doi : 10.1155/2009/168672 . (obsahuje také základní přehled konceptu Bell-polynomials)
Silvia Noschese, Paolo E. Ricci. Diferenciace víceproměnných složených funkcí a Bellových polynomů // Journal of Computational Analysis and Applications: journal. - 2003. - Sv. 5 , č. 3 . - str. 333-340 . - doi : 10.1023/A:1023227705558 . '
Vasilij G. Voinov, Michail S. Nikulin. O mocninných řadách, Bellových polynomech, Hardy-Ramanujan-Rademacherově problému a jeho statistických aplikacích (anglicky) // Kybernetika : journal. - 1994. - Sv. 30 , č. 3 . - str. 343-358 . — ISSN 00235954 .
Kruchinin, VV, 2011, Odvození Bellových polynomů druhého druhu Archivováno 11. září 2015 na Wayback Machine ( ArXiv )
Poznámky k přednášce Archivováno 4. března 2016 na Wayback Machine na Bellových polynomech, příklady