Número de campana

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

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

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

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

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

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

Como sugiere la notación de conjuntos anterior, no se considera el orden de los subconjuntos dentro de la familia; las particiones ordenadas se cuentan mediante una secuencia diferente de números, los números de Bell ordenados .${\displaystyle B_{0}}$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 trivialmente cierto que todos los subconjuntos de esta familia son subconjuntos no vacíos del conjunto vacío y que son subconjuntos disjuntos dos a dos del conjunto vacío, porque no hay subconjuntos que tengan estas propiedades improbables.

Las particiones de un conjunto se corresponden biunívocamente con sus relaciones de equivalencia . Estas son relaciones binarias 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 la partición. A la inversa, toda relación de equivalencia se corresponde con una partición en clases de equivalencia . ^{[ 2 ]} Por lo tanto, los números de Bell también tienen en cuenta las relaciones de equivalencia.

Si un número${\displaystyle N}$es un entero positivo libre de cuadrados , lo que significa que es el producto de algún número${\displaystyle n}$de números primos distintos , entonces${\displaystyle B_{n}}$da el número de particiones multiplicativas diferentes de${\displaystyle N}$Estas son factorizaciones de${\displaystyle N}$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${\displaystyle B_{3}}$= 5 factorizaciones:

${\displaystyle 30=2\times 15=3\times 10=5\times 6=2\times 3\times 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 generalmente se escriben como una secuencia de letras romanas, una por verso, donde los versos que riman reciben la misma letra entre sí, y los primeros versos de cada conjunto que rima se etiquetan en orden alfabético. Así, 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 reinsertándola ^en cualquier lugar de la baraja (incluida su posición original en la parte superior), con exactamente n repeticiones de esta operación, entonces hay n barajadas diferentes que se pueden realizar. De estas, el número 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 de 1/ n ! que describiría una permutación aleatoria uniforme de la baraja.

Relacionados con el barajado de cartas, existen otros problemas de conteo de tipos especiales de permutaciones que también se resuelven con los números de Bell. Por ejemplo, el n -ésimo número de Bell es igual al número de permutaciones de n elementos en las que ningún trío de valores ordenados tiene los dos últimos consecutivos. En una notación para patrones de permutación generalizados , donde los valores que deben ser consecutivos se escriben uno al lado del otro, y los valores que pueden aparecer de forma no consecutiva se separan con 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 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 se ha generalizado de esta manera: por la conjetura de Stanley-Wilf (ahora demostrada) , el número de tales permutaciones es exponencial simple, y los números de Bell tienen una tasa de crecimiento asintótico más alta que esa.

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

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 queda una partición de un conjunto más pequeño de k elementos para algún número k que puede variar de 0 a n . Hay${\displaystyle {\tbinom {n}{k}}}$opciones para los k elementos que quedan después de eliminar un conjunto, y B _k opciones sobre cómo dividirlos.

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

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

El número Stirling${\displaystyle \left\{{n \atop k}\right\}}$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 del lado derecho, aquel para el cual k es el número de conjuntos en la partición. ^{[ 8 ]}

Por lo tanto, utilizando la última fórmula se pueden calcular los números de Bell de forma no recursiva como

${\displaystyle B_{n}=\sum _{k=0}^{n}\left\{{n \atop k}\right\}=\sum _{k=0}^{n}{\frac {1}{k!}}\sum _{i=0}^{k}(-1)^{ki}{\binom {k}{i}}i^{n},}$

utilizando una de las fórmulas explícitas para los números de Stirling de segunda especie. ^{[ 9 ]}

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 \atop 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: ^{[ 10 ]}

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

Otras fórmulas de suma finita que utilizan números de Stirling de primera especie incluyen ^{[ 10 ].}

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

que se simplifica con${\displaystyle k=1}$a

$${\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${\displaystyle a=1}$,${\displaystyle b=k}$ a

$${\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}}$$ lo cual puede considerarse como la fórmula de inversión para 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 sumatoria del medio es la forma general que se utiliza 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 sumatoria en el caso específico de los números de Bell.

Una forma de obtener 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 conjuntos puede describirse como un conjunto de urnas no vacías en las que se han distribuido elementos etiquetados del 1 al n , y la clase combinatoria de todas las particiones (para todo n ) puede expresarse mediante la notación

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

Aquí,${\displaystyle {\mathcal {Z}}}$es una clase combinatoria con un único miembro de tamaño uno, un elemento que se puede colocar en una urna. El interior${\displaystyle \mathrm {S\scriptstyle ET} _{\geq 1}}$El operador describe un conjunto o urna que contiene uno o más elementos etiquetados, y el exterior ${\displaystyle \mathrm {S\scriptstyle ET} }$describe la partición general como un conjunto de estas urnas. La función generadora exponencial se puede leer a partir de esta notación traduciendo la${\displaystyle \mathrm {S\scriptstyle ET} }$operador en la función exponencial y la restricción de no vacuidad ≥1 en la resta por uno. ^{[ 11 ]}

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.${\displaystyle B'(x)=e^{x}B(x)}$La función en sí se puede encontrar resolviendo esta ecuación. ^{[ 12 ] [ 13 ] [ 14 ]}

Los números de Bell satisfacen la fórmula de Dobiński ^{[ 15 ] [ 12 ] [ 14 ]}

${\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 usando la serie de Taylor para la función exponencial y luego agrupando términos con el mismo exponente. ^{[ 11 ]} 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 como una función de los primeros n cumulantes .

Los números de Bell obedecen la congruencia de Touchard : si p es cualquier número primo, entonces ^{[ 16 ]}

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

o, generalizando ^{[ 17 ]}

${\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 un período de 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${\displaystyle p\leq 101}$y${\displaystyle p=113,163,167}$, o${\displaystyle 173}$Es exactamente este número (secuencia A001039 en el OEIS ) . ^{[ 18 ] [ 19 ]}

El período de los números de Bell módulo n es

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

La 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 derivarse mediante una aplicación estándar del método del descenso más pronunciado . ^{[ 20 ]}

Los números de Bell forman una sucesión logarítmicamente convexa . Al dividirlos por los factoriales, B _n / n !, se obtiene una sucesión logarítmicamente cóncava. ^{[ 21 ] [ 22 ] [ 23 ]}

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

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

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

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

dónde ${\displaystyle ~n_{0}(\varepsilon )=\max \left\{e^{4},d^{-1}(\varepsilon )\right\}~}$ y ${\displaystyle ~d(x):=\ln \ln(x+1)-\ln \ln x+{\frac {1+e^{-1}}{\ln x}}\,.}$ 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 ^{[ 24 ].}

${\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${\displaystyle h=O(\ln(n))}$como${\displaystyle n\rightarrow \infty }$, dónde${\displaystyle B}$y cada uno${\displaystyle P_{i}}$y${\displaystyle Q_{i}}$son expresiones conocidas en${\displaystyle W(n)}$. ^{[ 25 ]}

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 .