En matemática combinatoria , la fórmula de Dobiński [1] establece que el n -ésimo número de Bell B n (es decir, el número de particiones de un conjunto de tamaño n ) es igual a
dónde denota el número de Euler . La fórmula lleva el nombre de G. Dobiński, quien la publicó en 1877.
Contenido probabilístico
En el marco de la teoría de la probabilidad , la fórmula de Dobiński representa el n- ésimo momento de la distribución de Poisson con media 1. A veces, la fórmula de Dobiński se establece diciendo que el número de particiones de un conjunto de tamaño n es igual al n- ésimo momento de esa distribución.
Fórmula reducida
El cálculo de la suma de las series de Dobiński se puede reducir a una suma finita de n + o (n) términos, teniendo en cuenta la información quees un número entero. Precisamente uno tiene, para cualquier entero K> 1
previsto (una condición que implica K> n , pero que se satisface con algún K de tamaño n + o (n) ). De hecho, uno tienepara todo j ≥ 0 de modo que la cola está dominado por la serie , lo que implica , de ahí la fórmula reducida.
Generalización
La fórmula de Dobiński puede verse como un caso particular, ya que , de la relación más general:
Prueba
Una prueba [2] se basa en una fórmula para la función generadora de números de Bell ,
La serie de potencias para la exponencial da
entonces
El coeficiente de en esta serie de potencia debe ser , entonces
Otro estilo de prueba lo dio Rota . [3] Recuerde que si x y n son números enteros no negativos, entonces el número de funciones uno a uno que mapean un conjunto de tamaño n en un conjunto de tamaño x es el factorial descendente.
Deje ƒ ser cualquier función de un tamaño- n conjunto A en un tamaño- x conjunto B . Para cualquier b ∈ B , sea ƒ −1 ( b ) = { a ∈ A : ƒ ( a ) = b }. Entonces { ƒ -1 ( b ): b ∈ B } es una partición de A . Rota llama a esta partición el " núcleo " de la función ƒ . Cualquier función de A en B factoriza en
- una función que mapea un miembro de A con el elemento del kernel al que pertenece, y
- otra función, que es necesariamente uno-a-uno, que mapea el núcleo en B .
El primero de estos dos factores está completamente determinado por la partición π que es el núcleo. El número de funciones uno a uno de π a B es ( x ) | π | , donde | π | es el número de partes de la partición π . Así, el número total de funciones de un tamaño- n conjunto A en un tamaño- x conjunto B es
el índice ¸ que atraviesa el conjunto de todas las particiones de A . Por otro lado, el número de funciones de A a B es claramente x n . Por lo tanto, tenemos
Rota continúa la prueba usando álgebra lineal, pero es esclarecedor introducir una variable aleatoria X distribuida por Poisson con media 1. La ecuación anterior implica que el n- ésimo momento de esta variable aleatoria es
donde E representa el valor esperado . Pero demostraremos que todas las cantidades E (( X ) k ) son iguales a 1. De ello se deduce que
y esto es sólo el número de particiones del conjunto A .
La cantidad E (( X ) k ) se llama el k ésimo momento factorial de la variable aleatoria X . Para mostrar que esto es igual a 1 para todo k cuando X es una variable aleatoria distribuida por Poisson con media 1, recuerde que esta variable aleatoria asume cada valor valor entero con probabilidad . Por lo tanto
notas y referencias
- ^ Dobiński, G. (1877). "Summirung der Reihefür m = 1, 2, 3, 4, 5,… " . Grunert's Archiv (en alemán). 61 : 333–336.
- ^ Bender, Edward A .; Williamson, S. Gill (2006). "Teorema 11.3, fórmula de Dobiński". Fundamentos de la combinatoria con aplicaciones (PDF) . Dover. págs. 319–320. ISBN 0-486-44603-4.
- ^ Rota, Gian-Carlo (1964), "El número de particiones de un conjunto" (PDF) , American Mathematical Monthly , 71 (5): 498–504, doi : 10.2307 / 2312585 , JSTOR 2312585 , MR 0161805.