Número de campana

En matemáticas combinatorias , los números de Bell cuentan las posibles particiones de un conjunto . Estos números han sido estudiados por los matemáticos desde el siglo XIX y sus raíces se remontan al Japón medieval. En un ejemplo de la ley de epónimos de Stigler , se denominan así en honor a Eric Temple Bell , quien escribió sobre ellos en la década de 1930.

Los números de Bell se denotan , donde es un entero mayor o igual a cero . A partir de , los primeros números de Bell son$Estilo de visualización B_{n}$${\estilo de visualización n}$$Estilo de visualización B_{0}=B_{1}=1$

${\displaystyle 1,1,2,5,15,52,203,877,4140,\puntos}$(secuencia A000110 en la OEIS ).

El número de Bell cuenta las diferentes formas de particionar un conjunto que tiene exactamente elementos, o equivalentemente, las relaciones de equivalencia en él. También cuenta los diferentes esquemas de rima para poemas de 1 a 2 líneas. ^[1]$Estilo de visualización B_{n}$${\estilo de visualización n}$$Estilo de visualización B_{n}$${\estilo de visualización n}$

Además de aparecer en problemas de conteo, estos números tienen una interpretación diferente, como momentos de distribuciones de probabilidad . En particular, es el momento -ésimo de una distribución de Poisson con media 1.$Estilo de visualización B_{n}$${\estilo de visualización n}$

En general, es el número de particiones de un conjunto de tamaño . Una partición de un conjunto se define como una familia de subconjuntos no vacíos, disjuntos por pares, cuya unión es . Por ejemplo, debido a que el conjunto de 3 elementos se puede particionar de 5 maneras distintas:$Estilo de visualización B_{n}$${\estilo de visualización n}$${\estilo de visualización S}$${\estilo de visualización S}$${\estilo de visualización S}$$Estilo de visualización B3=5$${\estilo de visualización \{a,b,c\}}$

${\displaystyle \{\{a\},\{b\},\{c\}\},}$

${\displaystyle \{\{a\},\{b,c\}\},}$

${\displaystyle \{\{b\},\{a,c\}\},}$

${\displaystyle \{\{c\},\{a,b\}\},}$

${\displaystyle \{\{a,b,c\}\}.}$

Como lo sugiere la notación de conjuntos anterior, no se considera el orden de los subconjuntos dentro de la familia; las particiones ordenadas se cuentan por una secuencia diferente de números, los números de Bell ordenados . es 1 porque hay exactamente una partición del conjunto vacío . Esta partición es en sí misma el conjunto vacío; puede interpretarse como una familia de subconjuntos del conjunto vacío, que consta de cero subconjuntos. Es vacuamente cierto que todos los subconjuntos de esta familia son subconjuntos no vacíos del conjunto vacío y que son subconjuntos disjuntos por pares del conjunto vacío, porque no hay subconjuntos que tengan estas propiedades improbables.$Estilo de visualización B_{0}$

Las particiones de un conjunto se corresponden biunívocamente con sus relaciones de equivalencia . Se trata de relaciones binarias que son reflexivas , simétricas y transitivas . La relación de equivalencia correspondiente a una partición define dos elementos como equivalentes cuando pertenecen al mismo subconjunto de partición. A la inversa, toda relación de equivalencia corresponde a una partición en clases de equivalencia . ^[2] Por lo tanto, los números de Bell también cuentan las relaciones de equivalencia.

Si un número es un entero positivo sin cuadrados , es decir, que es el producto de una cierta cantidad de números primos distintos , entonces da el número de particiones multiplicativas diferentes de . Estas son factorizaciones de en números mayores que uno, tratando dos factorizaciones como iguales si tienen los mismos factores en un orden diferente. ^[3] Por ejemplo, 30 es el producto de los tres primos 2, 3 y 5, y tiene = 5 factorizaciones:${\estilo de visualización N}$${\estilo de visualización n}$$Estilo de visualización B_{n}$${\estilo de visualización N}$${\estilo de visualización N}$$Estilo de visualización B_{3}$

${\displaystyle 30=2\veces 15=3\veces 10=5\veces 6=2\veces 3\veces 5}$

Los números de Bell también cuentan los esquemas de rima de un poema o estrofa de n versos . Un esquema de rima describe qué versos riman entre sí, y por lo tanto puede interpretarse como una partición del conjunto de versos en subconjuntos que riman. Los esquemas de rima se escriben generalmente como una secuencia de letras romanas, una por verso, con los versos que riman con la misma letra que los demás, y con los primeros versos de cada conjunto que rima etiquetados en orden alfabético. Por lo tanto, los 15 posibles esquemas de rima de cuatro versos son AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC y ABCD. ^[1]

Los números de Bell aparecen en un problema de barajado de cartas mencionado en el apéndice de Gardner 1978. Si se baraja una baraja de n cartas quitando repetidamente la carta superior y volviéndola a insertar en cualquier parte de la baraja (incluida su posición original en la parte superior de la baraja), con exactamente n repeticiones de esta operación, entonces hay n ⁿ barajadas diferentes que se pueden realizar. De estas, la cantidad que devuelve la baraja a su orden original es exactamente B _n . Por lo tanto, la probabilidad de que la baraja esté en su orden original después de barajarla de esta manera es B _n / n ⁿ , que es significativamente mayor que la probabilidad 1/ n ! que describiría una permutación aleatoria uniforme de la baraja.

En relación con el barajado de cartas existen otros problemas de conteo de tipos especiales de permutaciones que también se responden con los números de Bell. Por ejemplo, el n -ésimo número de Bell es igual al número de permutaciones en n elementos en los que no hay tres valores que estén en orden ordenado que tengan los dos últimos de estos tres consecutivos. En una notación para patrones de permutación generalizados donde los valores que deben ser consecutivos se escriben adyacentes entre sí, y los valores que pueden aparecer de forma no consecutiva se separan con un guión, estas permutaciones se pueden describir como las permutaciones que evitan el patrón 1-23. Las permutaciones que evitan los patrones generalizados 12-3, 32-1, 3-21, 1-32, 3-12, 21-3 y 23-1 también se cuentan con los números de Bell. ^[4] Las permutaciones en las que cada patrón 321 (sin restricción de valores consecutivos) se puede extender a un patrón 3241 también se cuentan con los números de Bell. ^[5] Sin embargo, los números de Bell crecen demasiado rápido para contar las permutaciones que evitan un patrón que no ha sido generalizado de esta manera: por la conjetura de Stanley-Wilf (ahora probada) , el número de tales permutaciones es simplemente exponencial, y los números de Bell tienen una tasa de crecimiento asintótico más alta que esa.

Los números de Bell se pueden calcular fácilmente creando el llamado triángulo de Bell , también llamado matriz de Aitken o triángulo de Peirce en honor a Alexander Aitken y Charles Sanders Peirce . ^[6]

1. Empieza con el número uno. Colócalo en una fila aparte. ( )${\displaystyle x_{0,1}=1}$
2. Comience una nueva fila con el elemento más a la derecha de la fila anterior como el número más a la izquierda ( donde r es el último elemento de la ( i -1)-ésima fila)${\displaystyle x_{i,1}\leftarrow x_{i-1,r}}$
3. Determinar los números que no están en la columna de la izquierda tomando la suma del número a la izquierda y el número sobre el número a la izquierda, es decir, el número diagonalmente hacia arriba y a la izquierda del número que estamos calculando${\displaystyle (x_{i,j}\leftarrow x_{i,j-1}+x_{i-1,j-1})}$
4. Repita el paso tres hasta que haya una nueva fila con un número más que la fila anterior (repita el paso 3 hasta que )${\displaystyle j=r+1}$
5. El número en el lado izquierdo de una fila dada es el número de Bell para esa fila. ( )${\displaystyle B_{i}\leftarrow x_{i,1}}$

Aquí están las primeras cinco filas del triángulo construido con estas reglas:

${\displaystyle {\begin{array}{l}1\\1&2\\2&3&5\\5&7&10&15\\15&20&27&37&52\end{array}}}$

Los números de campana aparecen tanto en el lado izquierdo como en el derecho del triángulo.

Los números de Bell satisfacen una relación de recurrencia que involucra coeficientes binomiales : ^[7]

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}.}$

Esto se puede explicar observando que, a partir de una partición arbitraria de n  + 1 elementos, al eliminar el conjunto que contiene el primer elemento se obtiene una partición de un conjunto más pequeño de k elementos para un número k que puede variar de 0 a n . Hay opciones para los k elementos que quedan después de eliminar un conjunto y B _k opciones de cómo dividirlos.${\displaystyle {\tbinom {n}{k}}}$

Una fórmula de suma diferente representa cada número de Bell como una suma de números de Stirling del segundo tipo.

${\displaystyle B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}.}$

El número de Stirling es el número de maneras de particionar un conjunto de cardinalidad n en exactamente k subconjuntos no vacíos. Por lo tanto, en la ecuación que relaciona los números de Bell con los números de Stirling, cada partición contada en el lado izquierdo de la ecuación se cuenta en exactamente uno de los términos de la suma en el lado derecho, aquel para el cual k es el número de conjuntos en la partición. ^[8]${\displaystyle \left\{{n \encima de k}\right\}}$

Spivey 2008 ha proporcionado una fórmula que combina ambas sumas:

${\displaystyle B_{n+m}=\sum _{k=0}^{n}\sum _{j=0}^{m}\left\{{m \encima de j}\right\}{n \choose k}j^{nk}B_{k}.}$

Aplicando la fórmula de inversión de Pascal a la relación de recurrencia, obtenemos

$${\displaystyle B_{n}=\sum _ {k=0}^{n}{\binom {n}{k}}(-1)^{nk}B_{k+1},}$$

que puede generalizarse de esta manera: ^[9]

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}B_{k+j}=\sum _{i=0}^{k}{\binom {k} {i}}(-1)^{ki}B_{n+i+1}.}$$

Otras fórmulas de suma finita que utilizan números de Stirling del primer tipo incluyen ^[9]

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}a^{j}b^{nj}B_{j}=\sum _{i=0}^{ k}\left[{k \atop i}\right](-1)^{ki}\sum _{j=0}^{n}{\binom {n}{j}}a^{j}(b-ak)^{nj}B_{j+i},}$$

que se simplifica con${\estilo de visualización k=1}$

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}a^{j}b^{n-j}B_{j}=\sum _{j=0}^{n}{\binom {n}{j}}a^{j}(b-a)^{n-j}B_{j+1}}$$

y con , a${\displaystyle a=1}$${\displaystyle b=k}$

$${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}B_{j}k^{n-j}=\sum _{i=0}^{k}\left[{k \atop i}\right]B_{n+i}(-1)^{k-i}}$$que puede verse como la fórmula de inversión de los números de Stirling aplicada a la fórmula de Spivey.

La función generadora exponencial de los números de Bell es

${\displaystyle B(x)=\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=e^{e^{x}-1}.}$

En esta fórmula, la suma en el medio es la forma general utilizada para definir la función generadora exponencial para cualquier secuencia de números, y la fórmula de la derecha es el resultado de realizar la suma en el caso específico de los números de Bell.

Una forma de derivar este resultado utiliza la combinatoria analítica , un estilo de razonamiento matemático en el que los conjuntos de objetos matemáticos se describen mediante fórmulas que explican su construcción a partir de objetos más simples, y luego esas fórmulas se manipulan para derivar las propiedades combinatorias de los objetos. En el lenguaje de la combinatoria analítica, una partición de conjunto puede describirse como un conjunto de urnas no vacías en las que se han distribuido elementos etiquetados de 1 a n , y la clase combinatoria de todas las particiones (para todos los n ) puede expresarse mediante la notación

${\displaystyle \mathrm {S\scriptstyle ET} (\mathrm {S\scriptstyle ET} _{\geq 1}({\mathcal {Z}})).}$

Aquí, hay una clase combinatoria con un solo miembro de tamaño uno, un elemento que puede colocarse en una urna. El operador interno describe un conjunto o urna que contiene uno o más elementos etiquetados, y el externo describe la partición general como un conjunto de estas urnas. La función generadora exponencial puede entonces leerse a partir de esta notación traduciendo el operador en la función exponencial y la restricción de no vacío ≥1 en una resta por uno. ^[10]${\displaystyle {\mathcal {Z}}}$${\displaystyle \mathrm {S\scriptstyle ET} _{\geq 1}}$${\displaystyle \mathrm {S\scriptstyle ET} }$${\displaystyle \mathrm {S\scriptstyle ET} }$

Un método alternativo para derivar la misma función generadora utiliza la relación de recurrencia para los números de Bell en términos de coeficientes binomiales para demostrar que la función generadora exponencial satisface la ecuación diferencial . La función en sí se puede encontrar resolviendo esta ecuación. ^{[11] [12] [13]}${\displaystyle B'(x)=e^{x}B(x)}$

Los números de Bell satisfacen la fórmula de Dobinski ^{[14] [11] [13]}

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}.}$

Esta fórmula se puede derivar expandiendo la función generadora exponencial utilizando la serie de Taylor para la función exponencial y luego recopilando términos con el mismo exponente. ^[10] Permite interpretar B _n como el n- ésimo momento de una distribución de Poisson con valor esperado 1.

El n -ésimo número de Bell es también la suma de los coeficientes del n- ésimo polinomio de Bell completo , que expresa el n- ésimo momento de cualquier distribución de probabilidad en función de los primeros n cumulantes .

Los números de Bell obedecen a la congruencia de Touchard: si p es cualquier número primo entonces ^[15]

${\displaystyle B_{p+n}\equiv B_{n}+B_{n+1}{\pmod {p}}}$

o, generalizando ^[16]

${\displaystyle B_{p^{m}+n}\equiv mB_{n}+B_{n+1}{\pmod {p}}.}$

Debido a la congruencia de Touchard, los números de Bell son periódicos módulo p , para cada número primo p ; por ejemplo, para p  = 2, los números de Bell repiten el patrón impar-impar-par con período tres. El período de esta repetición, para un número primo arbitrario p , debe ser un divisor de

${\displaystyle {\frac {p^{p}-1}{p-1}}}$

y para todos los primos y , o es exactamente este número (secuencia A001039 en la OEIS ). ^{[17] [18]}${\displaystyle p\leq 101}$${\displaystyle p=113,163,167}$${\displaystyle 173}$

Los períodos de los números de Bell en módulo n son

1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, ... (secuencia A054767 en la OEIS )

Una aplicación de la fórmula integral de Cauchy a la función generadora exponencial produce la representación integral compleja

${\displaystyle B_{n}={\frac {n!}{2\pi ie}}\int _{\gamma }{\frac {e^{e^{z}}}{z^{n+1}}}\,dz.}$

Algunas representaciones asintóticas pueden entonces derivarse mediante una aplicación estándar del método de descenso más pronunciado . ^[19]

Los números de Bell forman una secuencia logarítmicamente convexa . Dividiéndolos por los factoriales, B _n / n !, se obtiene una secuencia logarítmicamente cóncava. ^{[20] [21] [22]}

Se conocen varias fórmulas asintóticas para los números de Bell. En Berend & Tassa 2010 se establecieron los siguientes límites:

${\displaystyle B_{n}<\left({\frac {0.792n}{\ln(n+1)}}\right)^{n}}$para todos los números enteros positivos ;${\displaystyle n}$

Además, si entonces para todos ,${\displaystyle \varepsilon >0}$${\displaystyle n>n_{0}(\varepsilon )}$

${\displaystyle B_{n}<\left({\frac {e^{-0.6+\varepsilon }n}{\ln(n+1)}}\right)^{n}}$

donde y Los números de Bell también se pueden aproximar utilizando la función W de Lambert , una función con la misma tasa de crecimiento que el logaritmo, como ^[23]${\displaystyle ~n_{0}(\varepsilon )=\max \left\{e^{4},d^{-1}(\varepsilon )\right\}~}$${\displaystyle ~d(x):=\ln \ln(x+1)-\ln \ln x+{\frac {1+e^{-1}}{\ln x}}\,.}$

${\displaystyle B_{n}\sim {\frac {1}{\sqrt {n}}}\left({\frac {n}{W(n)}}\right)^{n+{\frac {1}{2}}}\exp \left({\frac {n}{W(n)}}-n-1\right).}$

Moser & Wyman 1955 estableció la expansión

${\displaystyle B_{n+h}={\frac {(n+h)!}{W(n)^{n+h}}}\times {\frac {\exp(e^{W(n)}-1)}{(2\pi B)^{1/2}}}\times \left(1+{\frac {P_{0}+hP_{1}+h^{2}P_{2}}{e^{W(n)}}}+{\frac {Q_{0}+hQ_{1}+h^{2}Q_{2}+h^{3}Q_{3}+h^{4}Q_{4}}{e^{2W(n)}}}+O(e^{-3W(n)})\right)}$

uniformemente para como , donde y cada uno y son expresiones conocidas en . ^[24]${\displaystyle h=O(\ln(n))}$${\displaystyle n\rightarrow \infty }$${\displaystyle B}$${\displaystyle P_{i}}$${\displaystyle Q_{i}}$${\displaystyle W(n)}$

La expresión asintótica

${\displaystyle {\begin{aligned}{\frac {\ln B_{n}}{n}}&=\ln n-\ln \ln n-1+{\frac {\ln \ln n}{\ln n}}+{\frac {1}{\ln n}}+{\frac {1}{2}}\left({\frac {\ln \ln n}{\ln n}}\right)^{2}+O\left({\frac {\ln \ln n}{(\ln n)^{2}}}\right)\\&{}\qquad {\text{as }}n\to \infty \end{aligned}}}$

fue establecido por de Bruijn 1981.

Gardner en 1978 planteó la cuestión de si una cantidad infinita de números de Bell son también números primos . Estos se denominan primos de Bell . Los primeros primos de Bell son:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 (secuencia A051131 en la OEIS )

correspondiente a los índices 2, 3, 7, 13, 42 y 55 (secuencia A051130 en la OEIS ) . El siguiente primo de Bell es B ₂₈₄₁ , que es aproximadamente 9,30740105 × 10 ^{6538. [25]}

Los números de Bell reciben su nombre de Eric Temple Bell , quien escribió sobre ellos en 1938, a raíz de un artículo de 1934 en el que estudiaba los polinomios de Bell . ^{[27] [28]} Bell no afirmó haber descubierto estos números; en su artículo de 1938, escribió que los números de Bell "han sido investigados con frecuencia" y "han sido redescubiertos muchas veces". Bell cita varias publicaciones anteriores sobre estos números, comenzando con Dobiński 1877 que da la fórmula de Dobiński para los números de Bell. Bell llamó a estos números "números exponenciales"; el nombre "números de Bell" y la notación B _n para estos números les fue dado por Becker & Riordan 1948. ^[29]

La primera enumeración exhaustiva de particiones de conjuntos parece haber ocurrido en el Japón medieval, donde (inspirado por la popularidad del libro La historia de Genji ) surgió un juego de salón llamado genji-ko , en el que se les daba a los invitados cinco paquetes de incienso para que los olieran y se les pedía que adivinaran cuáles eran iguales entre sí y cuáles eran diferentes. Las 52 posibles soluciones, contadas por el número de campana B ₅ , se registraban mediante 52 diagramas diferentes, que se imprimían sobre los títulos de los capítulos en algunas ediciones de La historia de Genji. ^{[26] [30]}

En el segundo cuaderno de notas de Srinivasa Ramanujan , investigó tanto los polinomios de Bell como los números de Bell. ^[31] Las primeras referencias para el triángulo de Bell , que tiene los números de Bell en ambos lados, incluyen Peirce 1880 y Aitken 1933.

• Polinomios de Touchard
• Número catalán
• Número de Stirling
• Números de Stirling del primer tipo

• Robert Dickau. "Diagramas de números de Bell".
• Weisstein, Eric W. "Número de campana". MathWorld .
• Gottfried Helms. "Otras propiedades y generalización de los números de Bell" (PDF) .