Polinomis de Bell

En combinatòria, els polinomis de Bell, nomenats en honor d'Eric Temple Bell, s'utilisen en l'estudi de les particions establides. Estan relacionats en els números de Stirling i en els números de Bell. També apareixen en moltes aplicacions, com en la fòrmula de Faà vaig donar Bruno.

Polinomis de Bell

Polinomis de Bell exponencials

Els polinomis de Bell exponencials parcials o incomplets són una matriu triangular de polinomis donats per

$B_{n,k}(x_1,x_2,\dots ,x_{n-k+1})=\sum \frac{n!}{j_1!j_2!\cdots j_{n-k+1}!}{\left(\frac{x_1}{1!}\right)}^{j_1}{\left(\frac{x_2}{2!}\right)}^{j_2}\cdots {\left(\frac{x_{n-k+1}}{(n-k+1)!}\right)}^{j_{n-k+1}},$

a on la suma es pren sobre totes les seqüències j₁, j₂, j₃, ..., j_n−k+1 d'número entero no negatius tals que estes dos condicions són satisfetes:

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

La suma

$B_n(x_1,\dots ,x_n)=\sum _{k=1}^n{B}_{n,k}(x_1,x_2,\dots ,x_{n-k+1})$

es diu n-ésimo polinomi de Bell exponencial complet.

Polinomis de Bell ordinaris

De la mateixa manera, un polinomi de Bell parcial ordinari, en contrast en el polinomi de Bell exponencial habitual definit anteriorment, ve dau per

${\hat{B}}_{n,k}(x_1,x_2,\dots ,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}},$

a on la suma s'eixecuta en totes les seqüències j₁, j₂, j₃, ..., j_n−k+1 de sancers no negatius tals que

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

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

Els polinomis de Bell ordinaris es poden expressar en térmens de polinomis de Bell exponencials:

${\hat{B}}_{n,k}(x_1,x_2,\dots ,x_{n-k+1})=\frac{k!}{n!}{B}_{n,k}(1!\cdot x_1,2!\cdot x_2,\dots ,(n-k+1)!\cdot x_{n-k+1}).$

En general, el terme polinomi de Bell es referix al polinomi de Bell exponencial, a menos que s'establixca explícitament lo contrari.

Significat combinatori

El polinomi de Bell exponencial codifica l'informació relacionada en les formes en que es pot particionar un conjunt. Per eixemple, si es considera un conjunt {A, B, C}, es pot dividir en dos subconjunts no buits que no se superponen, que també es coneix com a parts o blocs, de tres maneres diferents:

{{A}, {B, C}}

{{B}, {A, C}}

{{C}, {B, A}}

Per lo tant, es pot codificar l'informació sobre estes particions com

$B_{3,2}(x_1,x_2)=3x_1{x}_2.$

Ací, els subíndexs de B_3,2 indiquen que s'està considerant la partició del conjunt en 3 elements en 2 blocs. El subíndex de cada x_i indica la presència d'un bloc en elements i (o bloc de tamany i) en una partició donada. Llavors ací, x₂ indica la presència d'un bloc en dos elements. De la mateixa manera, x₁ indica la presència d'un bloc en un sol element. L'exponent de x_i^j indica que hi ha j blocs de tamany i en una sola partició. Ací, ya que tant x₁ i x₂ tenen l'exponent 1, açò indica que solament hi ha un bloc d'eixe tipo en una partició donada. El coeficient del monomi indica quantes particions hi ha. En este cas, hi ha 3 particions d'un conjunt en 3 elements en 2 blocs, a on en cada partició els elements es dividixen en dos blocs de tamanys 1 i 2.

Com qualsevol conjunt es pot dividir en un sol bloc d'una sola manera, l'interpretació anterior significa que B_n,1 = x_n. De la mateixa manera, ya que solament hi ha una forma de dividir un conjunt en n elements en n blocs, B_n,n = x₁ⁿ.

Com un eixemple més complicat, considere's

$B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5{x}_1+15x_4{x}_2+10x_3^2.$

Açò indica que si un conjunt en 6 elements es dividix en 2 blocs, llavors es poden tindre 6 particions en blocs de tamany 1 i 5, 15 particions en blocs de tamany 4 i 2 i 10 particions en 2 blocs de tamany 3.

Tinga's en conte que la suma dels subíndexs en un monomi és igual a la cantitat total d'elements. Per lo tant, el número de monomis que apareixen en el polinomi parcial de Bell és igual al número de maneres en que el sancer n es pot expressar com una suma de sancers positius k. Açò és lo mateix que la partició de n en k partixes. Per eixemple, en els eixemples anteriors, el número entero 3 pot dividir-se en dos parts solament com 2 + 1. Per lo tant, solament hi ha un monomi en B_3,2. No obstant, el sancer 6 es pot dividir en dos parts com 5 + 1, 4 + 2 i 3 + 3. Per lo tant, hi ha tres monomis en B_6,2. De fet, els subíndexs de les variables en un monomi són els mateixos que els daus per la partició sancera, indicant els tamanys dels diferents blocs. El número total de monomis que apareixen en un polinomi de Bell complet B_n és per lo tant igual al número total de particions sanceres de n.

També deu tindre's en conte que el grau de cada monomi, que és la suma dels exponents de cada variable en el monomi, és igual al número de blocs en els que es dividix el conjunt. És dir, j₁ + j₂ + ... = k. Per lo tant, donat un polinomi complet de Bell B_n, es pot separar el polinomi parcial de Bell B_n,k per mig de la recopilació de tots els monomis en grau k.

Finalment, si es fa cas omís dels tamanys dels blocs i es posen tots els x_i = x, llavors la suma dels coeficients del polinomi parcial de Bell B_n,k donarà el número total de formes que un conjunt en n elements es pot dividir en k blocs, que és el mateix que el número de Stirling de segona espècie. Ademés, la suma de tots els coeficients del polinomi de Bell complet B_n donarà el número total de formes en que un conjunt en n elements pot ser particionado en subconjunts no superposts, que és el mateix que el número de Bell.

En general, si l'número entero n és particionado en una suma en la que "1" apareix j₁ voltes, "2" apareix j₂ voltes, i aixina successivament, després el número de particions d'un conjunt de tamany n que colapsen en eixa partició de l'número entero n quan els membres del conjunt es tornen indistinguibles és el coeficient corresponent en el polinomi.

Eixemples

Per eixemple, es té

$B_{6,2}(x_1,x_2,x_3,x_4,x_5)=6x_5{x}_1+15x_4{x}_2+10x_3^2$

perque hi ha

6 maneres de dividir un conjunt de 6 com 5 + 1,

15 formes de dividir un conjunt de 6 com 4 + 2, i

10 maneres de dividir un conjunt de 6 com 3 + 3.

Similarment,

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

perque hi ha

15 formes de dividir un conjunt de 6 com 4 + 1 + 1,

60 maneres de dividir un conjunt de 6 com 3 + 2 + 1, i

15 formes de dividir un conjunt de 6 com 2 + 2 + 2.

Vore també

• Matriu de Bell
• Fòrmula exponencial

Bibliografia

• “On new identities for Bell's polynomial” (2005). Discrete Math. 293: 5–10. doi:10.1016/j.disc.2004.08.023.
• (2017).«Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs».Journal of Computational Biology.24(2)

93–105.doi:10.1089/cmb.2016.0190.

• Andrews, G. E. (1998). The Theory of Partitions, 1st pbk edició, Cambridge University Press, pp. 204–211. ISBN 0-521-63766-X.

• (1927–1928).«Partition Polynomials».Annals of Mathematics.29(1/4)

38–46.doi:10.2307/1967979.

• (2009).«Exponential Polynomials, Stirling Numbers, and Evaluation of Some Gamma Integrals».Abstract and Applied Analysis.2009

Article ID 168672.doi:10.1155/2009/168672. (conté també una revisió elemental del concepte Bell-polinomis)

• Charalambides, C. A. (2002). Enumerative Combinatorics, Chapman & Hall / CRC, pp. 632. ISBN 9781584882909.
• Comtet, L. (1974). Advanced Combinatorics: The Art of Finite and Infinite Expansions, Reidel Publishing Company.
• (2012).«Families of sequences from a class of multinomial sums».Journal of Integer Sequences.15

Article 12.1.8.

• Plantilla:Cite arXiv
• (2003).«Differentiation of Multivariable Composite Functions and Bell Polynomials».Journal of Computational Analysis and Applications.5(3)

333–340.doi:10.1023/A:1023227705558.

• Roman, S. (2013). The Llindar Calculus, Dover Publications, pp. 208. ISBN 9780486153421.
• (1994).«On power séries, Bell polynomials, Hardy–Ramanujan–Rademacher problem and its statistical applications».Kybernetika.30(3)

343–358.ISSN 0023-5954.