Número de Bell

En combinatoria, el n-ésimo número de Bell, llamado así por Eric Temple Bell, es el número de particiones de un conjunto de n elementos, o equivalentemente, el número de relaciones de equivalencia en el mismo. Comenzando con B₀ = B₁ = 1, los primeros números de Bell son:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, … (sucesión A000110 en OEIS).

La enésima de estas cifras, B_n, cuenta la cantidad de formas diferentes de dividir un conjunto que tiene exactamente n elementos, o equivalentemente, el número de relaciones de equivalencia. Fuera de las matemáticas, el mismo número también cuenta la cantidad de esquemas de rima diferentes para poemas de línea 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, B_n es el enésimo momento de una distribución de Poisson con media de 1.

Contando

Particiones de un conjunto

Artículo principal: Partición de un conjunto

En general, $B_{n}$ es el número de particiones de un conjunto de tamaño $n$ . Una partición de un conjunto $S$ es definida como un conjunto no vacío, formado por subconjuntos separados de $S$ cuya unión es $S$ .

Ejemplo

$B_{3}=5$ porque el conjunto de tres elementos $\{a,b,c\}$ se puede dividir de 5 formas distintas.

\{\{a\},\{b\},\{c\}\}

\{\{a\},\{b,c\}\}

\{\{b\},\{a,c\}\}

\{\{c\},\{a,b\}\}

\{\{a,b,c\}\}

B_{0}

es 1 debido a que sólo hay una partición del conjunto vacío. El único subconjunto del conjunto vacío es él mismo

A\subseteq \varnothing \Longleftrightarrow A=\varnothing

. Entonces utilizando la notación del conjunto anterior, no tenemos en cuenta ni el orden de las particiones ni el orden de los elementos dentro de cada partición, por lo que las siguientes particiones son idénticas:

\{\{b\},\{a,c\}\}

\{\{a,c\},\{b\}\}

\{\{b\},\{c,a\}\}

\{\{c,a\},\{b\}\}

Si tuviéramos tenemos en cuenta el orden de los conjuntos siendo conjuntos diferentes, entonces el número de particiones vendría dado por los números de Bell ordenados.

Factorizaciones

Si $N$ es un número entero sin cuadrados (Es decir, el número es el producto de $n$ números primos distintos), entonces $B_{n}$ nos da el número de particiones diferentes multiplicadas de $N$ . Estas son las factorizaciones de $N$ en números mayores que 1, siendo dos factorizaciones iguales si tienen los mismos factores pero en orden diferente.

Ejemplo

$30$ es el producto de los tres primos 2, 3 y 5, y tiene $B_{3}=5$ factorizaciones:

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

Permutaciones

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 retirando repetidamente la carta superior y reinsertandola en cualquier lugar 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ⁿ diferentes barajados que pueden ser realizado. De estos, el número que devuelve el mazo a su orden original ordenado es exactamente B_n. Por lo tanto, la probabilidad de que la baraja esté en su orden original después de mezclarla de esta manera es B_n/nⁿ, ¡que es significativamente más grande que la 1/n! probabilidad que describiría una permutación uniformemente aleatoria de la baraja.

En relación con la baraja de cartas, existen otros problemas para contar tipos especiales de permutaciones que también responden los números de Bell. Por ejemplo, el enésimo número de Bell equivale al número de permutaciones en n elementos en los que no hay tres valores que están en orden ordenado tienen los últimos dos de estos tres consecutivos. En una notación para patrones de permutación generalizada donde los valores que deben ser consecutivos se escriben adyacentes entre sí, y los valores que pueden aparecer de manera no consecutiva están separados por un guion, 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 son contadas por los números de Bell. Las permutaciones en las que cada patrón 321 (sin restricción en valores consecutivos) se pueden extender a un patrón 3241 también se cuentan por los números de Bell. Sin embargo, los números de Bell crecen demasiado rápido para contar las permutaciones que evitan un patrón que no se ha generalizado de esta manera: mediante la (ahora probada) conjetura de Stanley-Wilf, el número de tales permutaciones es individualmente exponencial, y los números de Bell tienen una mayor tasa de crecimiento asintótico que eso.

Esquema de triángulo para cálculos

Los números de Bell se pueden calcular fácilmente creando el llamado triángulo de Bell, también llamado conjunto de Aitken o el triángulo de Peirce después de Alexander Aitken y Charles Sanders Peirce.

Comience con el número uno. Pon esto en una fila por sí mismo. $x_{0,1}=1$
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 ( $x_{i,1}\leftarrow x_{i-1,r}$ donde r es el último elemento de (i-1) -ª fila)
Determine los números que no están en la columna 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 arriba y a la izquierda del número que estamos calculando $(x_{i,j}\leftarrow x_{i,j-1}+x_{i-1,j-1})$
Repita el paso tres hasta que haya una nueva fila con un número más que la fila anterior (haga el paso 3 hasta $j=r+1$ )
El número en el lado izquierdo de una fila dada es el número de Bell para esa fila. $B_{i}\leftarrow x_{i,1}$

Estas son las primeras cinco filas del triángulo construido por estas reglas:

 1
 1   2
 2   3   5
 5   7  10  15
15  20  27  37  52

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

Propiedades de los números de Bell

Los números de Bell satisfacen la siguiente fórmula recursiva:

B_{n+1}=\sum _{k=0}^{n}{{n \choose k}B_{k}}

Puede explicarse observando que, a partir de una partición arbitraria de n + 1 elementos, la eliminación del conjunto que contiene el primer elemento deja una partición de un conjunto menor de k elementos para algún número k que puede ir de 0 a n. Hay ${\bigl (}{\begin{smallmatrix}n\\k\end{smallmatrix}}{\bigr )}$ opciones para los k elementos que quedan después de que se elimine un conjunto, y Bk opciones de cómo dividirlos.

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

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

El número de Stirling $\left\{{n \atop k}\right\}$ es el número de formas de dividir 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 exactamente en uno de los términos de la suma en el lado derecho, aquel para el cual k es el número de juegos en la partición.

Spivey (2008) ha dado una fórmula que combina estas dos sumas:

$B_{n+m}=\sum _{k=0}^{n}\sum _{j=0}^{m}\left\{{m \atop j}\right\}{n \choose k}j^{n-k}B_{k}$

Función de generación

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

$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 de generación exponencial para cualquier secuencia de números, y la fórmula de la derecha es el resultado de realizar la sumatoria en el caso específico de los números de Bell. Una forma de derivar este resultado es 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 establecida puede describirse como un conjunto de urnas no vacías en la que los elementos etiquetados de 1 a n se han distribuido, y la clase combinatoria de todas las particiones (para todos los n) puede expresarse mediante la notación

$\mathrm {S\scriptstyle ET} (\mathrm {S\scriptstyle ET} _{\geq 1}({\mathcal {Z}})).$ Aquí, ${\mathcal {Z}}$ es una clase combinatoria con un solo miembro de tamaño uno, un elemento que se puede colocar en una urna. El operador interno $\mathrm {S\scriptstyle ET} _{\geq 1}$ describe un conjunto o urna que contiene uno o más elementos etiquetados, y el outer $\mathrm {S\scriptstyle ET}$ describe la partición general como un conjunto de estas urnas. La función de generación exponencial se puede leer a partir de esta notación trasladando el operador $\mathrm {S\scriptstyle ET}$ a la función exponencial y la restricción de no eliminación ≥1 a la resta en uno .

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 mostrar que la función de generación exponencial satisface la ecuación diferencial $B'(x)=e^{x}B(x)$ . La función en sí se puede encontrar al resolver esta ecuación.

Representación integral

Una aplicación de la Fórmula integral de Cauchy a la función exponencial, genera la representación de la integral compleja

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

Alguna representaciones asintóticas, pueden derivarse por la aplicación estándar del método del descenso más pronunciado, también conocido como método Gradiente.

Concavidad del registro

Los números de Bell forman una secuencia logarítmica convexa. Dividiéndolos por los factoriales, $B_{n}/n!$ , obtienes la secuencia logarítmica convexa.

Momentos de las distribuciones de probabilidades

Los números de Bell cumplen la fórmula de Dobinski

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

Esta fórmula puede ser derivada para expandir la función de generación exponencial utilizando la serie de Taylor para la función exponencial, y luego recoger términos con el mismo exponente. Esto nos permite que $B_{n}$ pueda ser interpretado como el enésimo momento de una distribución de Poisson con el valor esperado $1$ .

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

Aritmética Modular

Los números de Bell siguen la congruencia de Touchard, que dice si $p$ es cualquier número primo entonces:

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

o generalizando:

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

Por consecuencia de la congruencia de Touchard, los números de Bell son periódicos con módulo $p$ , por cada número primo $p$ . Por ejemplo si $p=2$ , los números de Bell repiten el patrón impar-impar incluso con el periodo 3. El periodo de la repetición, para un número arbitrario $p$ , debe ser un divisor de:

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

Y para todos los números primos $p\leq 101$ o $p=113,163,167$ o $173$ el número de la secuencia A001039 en OEIS

El periodo para los números de Bell con módulo $n$ son:

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

Números de Bell primos

Gardner (1978) planteó la cuestión de si hay infinitos números de Bell que son primos. Los primeros números de Bell que son primos son:

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

correspondiente a los índices 2, 3, 7, 13, 42 y 55 (secuencia A051130 en el OEIS).

El siguiente número de Bell primo es B₂₈₄₁, que es aproximadamente 9.30740105 × 10⁶⁵³⁸. Es el número de Bell primo más grande conocido. Ignacio Larrosa Cañestro mostró que era un probable primo en 2002. Después de 17 meses de cálculo con el programa ECPP de Marcel Martin, Primo, Ignacio Larrosa Cañestro demostró que era primo en 2004. Descartó otros posibles números primos por debajo de B₆₀₀₀, búsqueda extendida posteriormente hasta B₃₀₄₄₇ por Eric Weisstein, hasta B₅₀₀₀₀ por Vaclav Kotesovec (18/05/2021) y hasta B₁₀₀₀₀₀ por Mathieu Gouttenoire (31/10/2021).

Historia de los números de Bell

Los números de Bell llevan el nombre de Eric Temple Bell, quien escribió sobre ellos en 1938, siguiendo un artículo de 1934 en el que estudiaba los polinomios de Bell. 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 Dobinski para los números de Bell. Bell llamó a estos números "números exponenciales"; el nombre "Bell numbers" y la notación B_n para estos números fue dada por Becker & Riordan (1948).

La primera enumeración exhaustiva de las particiones establecidas parece haber ocurrido en el Japón medieval, donde (inspirado por la popularidad del libro El cuento de Genji) surgió un juego de salón llamado genji-ko, en el que los invitados recibieron cinco paquetes de incienso para oler y se les pidió que adivinaran cuáles eran iguales entre sí y cuáles eran diferentes. Las 52 soluciones posibles, contadas por el número B₅ de Bell, se registraron mediante 52 diagramas diferentes, que se imprimieron por encima de los títulos de los capítulos en algunas ediciones de The Tale of Genji.

En el segundo cuaderno de Srinivasa Ramanujan, investigó tanto los polinomios de Bell como los números de Bell. 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).

Véase también

Números de Stirling de segunda especie - número de formas de particionar un conjunto de n elementos en k subconjuntos no vacíos.

Referencias

Gian-Carlo Rota, 1964, "The Number of Partitions of a Set," American Mathematical Monthly 71(5): 498—504.
Lovász, L. Combinatorial Problems and Exercises, 2.ª ed. Ámsterdam, Países Bajos: North-Holland, 1993.

Enlaces externos

Diagramas de números de Bell.
Uso del Triángulo de Bell para calcular números de Bell.
Weisstein, Eric W. «Número de Bell». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
The period of the Bell numbers modulo a prime

Datos: Q816063