1.5: Números de Campana
- Page ID
- 117118
Comenzamos con una definición:
Definición\(\PageIndex{1}\): Partition
Una partición de un conjunto\(S\) es una colección de subconjuntos no vacíos\(A_i\subseteq S\),\(1\le i\le k\) (las partes de la partición), tal que\(\bigcup_{i=1}^k A_i=S\) y para cada\(i\not=j\),\(A_i\cap A_j=\emptyset\).
Ejemplo\(\PageIndex{1}\):
Las particiones del conjunto\(\{a,b,c\}\) son\(\{\{a\},\{b\},\{c\}\}\),\(\{\{a,b\},\{c\}\}\),\(\{\{a,c\},\{b\}\}\),\(\{\{b,c\},\{a\}\}\), y\(\{\{a,b,c\}\}\).
Las particiones surgen en una serie de áreas de las matemáticas. Por ejemplo, si\(\equiv\) es una relación de equivalencia en un conjunto\(S\), las clases de equivalencia de\(\equiv\) forman una partición de\(S\). Aquí consideramos el número de particiones de un conjunto finito\(S\), que bien podríamos tomar como ser\([n]=\{1,2,3,\ldots,n\}\), a menos que algún otro conjunto sea de interés. Denotamos el número de particiones de un\(n\) -elemento establecido por\(B_n\); estos números son los números de Bell. Por el ejemplo anterior, vemos eso\(B_3=5\). Por conveniencia dejamos\(B_0=1\). Es bastante fácil ver eso\(B_1=1\) y\(B_2=2\).
No se conocen fórmulas simples para\(B_n\), por lo que nos contentamos con una relación de recurrencia.
Teorema \(\PageIndex{1}\): Bell Numbers
Los números de Bell satisfacen\[ B_{n+1} = \sum_{k=0}^n {n\choose k} B_k.\nonumber \]
- Prueba
-
Considera una partición de\(S=\{1,2,\ldots,n+1\}\),\(A_1\),...,\(A_m\). Podemos suponer que\(n+1\) está en\(A_1\), y eso\(|A_1|=k+1\), para algunos\(k\),\(0\le k\le n\). Entonces\(A_2\),...,\(A_{m}\) formar una partición de los\(n-k\) elementos restantes de\(S\), es decir, de\(S\backslash A_1\). Hay\(B_{n-k}\) particiones de este conjunto, por lo que hay\(B_{n-k}\) particiones de\(S\) en las que una parte es el conjunto\(A_1\). Hay\({n\choose k}\) conjuntos de tamaño\(k+1\) que contienen\(n+1\), por lo que el número total de particiones de\(S\) en las que\(n+1\) se encuentra en un conjunto de tamaño\(k+1\) es\({n\choose k}B_{n-k}\). Sumando sobre todos los valores posibles de\(k\), esto significa\[\label{eq:1} \eqalignno{ B_{n+1} &= \sum_{k=0}^n {n\choose k} B_{n-k}. }\]
Podemos reescribir esto, usando el Teorema 1.4.2, como\[B_{n+1} = \sum_{k=0}^n {n\choose n-k} B_{n-k},\nonumber\] y luego notar que esto es lo mismo que la suma\[B_{n+1} = \sum_{k=0}^n {n\choose k} B_k,\nonumber\] escrita al revés.
Ejemplo\(\PageIndex{2}\)
Aplicamos la recurrencia para calcular los primeros números de Bell:
\[ \eqalign{ B_1&=\sum_{k=0}^0 {0\choose 0}B_0 = 1\cdot 1 = 1\cr B_2&=\sum_{k=0}^1 {1\choose k}B_k = {1\choose 0}B_0 + {1\choose 1}B_1 = 1\cdot 1+1\cdot 1 =1+1 =2\cr B_3&=\sum_{k=0}^2 {2\choose k}B_k = 1\cdot 1 + 2\cdot 1 + 1\cdot 2 = 5\cr B_4&=\sum_{k=0}^3 {3\choose k}B_k = 1\cdot 1 + 3\cdot 1 + 3\cdot 2 + 1\cdot 5 = 15\cr }\nonumber \]
Los números de Bell crecen exponencialmente rápido; los primeros son 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437.
Los números de Bell aparecen en muchos otros problemas; aquí hay un ejemplo interesante. Una necesidad común en algunos programas de computadora es generar una permutación aleatoria de\(1,2,3,\ldots,n\), que podemos pensar como una barajación de los números, visualizada como cartas numeradas en una baraja. Aquí hay un método atractivo que es fácil de programar: Comience con los números en orden, luego en cada paso, elimine un número al azar (esto es fácil en la mayoría de los lenguajes de programación) y póngalo al frente de la lista de números. (Visto como un barajado de una baraja de cartas, esto corresponde a quitar una carta y colocarla en la parte superior de la baraja). ¿Cuántas veces debemos hacer esto? No hay un número mágico, pero ciertamente no debería ser pequeño en relación con el tamaño de\(n\). Vamos a elegir\(n\) como el número de pasos.
Podemos escribir tal shuffle como una lista de\(n\) enteros,\((m_1,m_2,\ldots,m_n)\). Esto indica que en el paso\(i\), el número\(m_i\) se mueve al frente.
Ejemplo\(\PageIndex{3}\)
Sigamos el barajado\((3,2,2,4,1)\):\[ \eqalign{ (3)&:\quad 3 1 2 4 5\cr (2)&:\quad 2 3 1 4 5\cr (2)&:\quad 2 3 1 4 5\cr (4)&:\quad 4 2 3 1 5\cr (1)&:\quad 1 4 2 3 5\cr } \nonumber\]
Solución
Tenga en cuenta que permitimos movimientos de “no hacer nada”, quitando la carta superior y luego colocándola encima. El número de barajados posibles es entonces fácil de contar: hay\(n\) opciones para que la tarjeta se quite, y esto se repite\(n\) veces, por lo que el número total es\(n^n\). (Si continuamos un barajado para\(m\) los pasos, el número de barajados es\(n^m\).) Dado que solo hay\(n!\) diferentes permutaciones de\(1,2,\ldots,n\), esto significa que muchos barajados dan el mismo orden final.
Ejemplo\(\PageIndex{4}\)
Aquí está nuestra pregunta: ¿cuántos barajados resultan en el orden original?
Solución
Estos barajados vuelven al orden original:\((1,1,1,1,1)\),\((5,4,3,2,1)\),\((4,1,3,2,1)\).
Teorema \(\PageIndex{2}\)
El número de barajados de\([n]\) ese resultado en el orden ordenado original es\(B_n\).
- Prueba
-
Como sabemos que\(B_n\) cuenta el número de particiones de\(\{1,2,3,\ldots,n\}\), podemos probar el teorema estableciendo una correspondencia 1—1 entre los barajados que dejan la baraja ordenada y las particiones. Dado un barajado\((m_1,m_2,\ldots,m_n)\), ponemos en un solo conjunto todo\(i\) lo que\(m_i\) tiene un solo valor. Por ejemplo, usando la barajación\((4,1,3,2,1)\), Desde\(m_2=m_5\), un conjunto es\(\{2,5\}\). Todos los demás valores son distintos, por lo que los otros conjuntos en la partición son\(\{1\}\),\(\{3\}\), y\(\{4\}\).
Tenga en cuenta que cada barajado, sin importar cuál sea el orden final, produce una partición por este método. Sólo nos interesan los barajados que dejan la baraja ordenada. Lo que ahora necesitamos es demostrar que cada partición resulta exactamente de una de esas barajadas.
Supongamos que tenemos una partición con\(k\) partes. Si un barajado deja la baraja ordenada, la última entrada,\(m_n\), debe ser 1. Si la parte que contiene\(n\) es\(A_1\), entonces debe ser que\(m_i=1\) si y sólo si\(i\in A_1\). Si\(k=1\), entonces la única parte contiene todo\(\{1,2,\ldots,n\}\), y la barajación debe ser\((1,1,1,\ldots,1)\).
Si\(k>1\), el último movimiento que no sea 1 debe ser 2, ya que 2 debe terminar inmediatamente después de 1. Así, si\(j_2\) es el índice más grande tal que\(j_2\notin A_1\), deje\(A_2\) ser la parte que contenga\(j_2\), y debe ser eso\(m_i=2\) si y sólo si\(i\in A_2\). Seguimos de esta manera: Una vez que hayamos descubierto cuál de los valores\(m_i\) debe tener\(1,2,\ldots,p\), deje\(j_{p+1}\) ser el índice más grande tal que\(j_{p+1}\notin A_1\cup\cdots\cup A_p\), deje\(A_{p+1}\) ser la parte que contenga\(j_{p+1}\), y luego\(m_i=p+1\) si y sólo si\(i\in A_{p+1}\). Cuando\(p=k\), se\(m_i\) han determinado todos los valores, y este es el barajado único que corresponde a la partición.
Ejemplo\(\PageIndex{5}\)
Considera la partición\(\{\{1,5\},\{2,3,6\},\{4,7\}\}\). Debemos tener\(m_7=m_4=1\),\(m_6=m_3=m_2=2\), y\(m_5=m_1=3\), así es la barajación\((3,2,2,1,3,2,1)\).
Volviendo al problema de escribir un programa de computadora para generar una partición: ¿es este un buen método? Cuando decimos que queremos una permutación aleatoria, queremos decir que queremos que cada permutación ocurra con la misma probabilidad, es decir,\(1/n!\). Dado que el orden original es una de las permutaciones, queremos que el número de barajados que lo producen sea exactamente\(n^n/n!\), pero\(n!\) no divide\(n^n\), por lo que esto es imposible. La probabilidad de obtener la permutación original es\(B_n/n^n\), y esto resulta ser bastante mayor que\(1/n!\). Por lo tanto, este no es un método adecuado para generar permutaciones aleatorias.
La relación de recurrencia anterior es una forma algo engorrosa de calcular los números de Bell. Otra forma de calcularlos es con una recurrencia diferente, expresada en el triángulo Bell, cuya construcción es similar a la del triángulo de Pascal:\[\matrix{ A_{1,1}\cr A_{2,1}&A_{2,2}\cr A_{3,1}&A_{3,2}&A_{3,3}\cr A_{4,1}&A_{4,2}&A_{4,3}&A_{4,4}\cr} \qquad\matrix{ 1\cr 1&2\cr 2&3&5\cr 5&7&10&15\cr}\nonumber\]
La regla para construir este triángulo es:\(A_{1,1}=1\); la primera entrada en cada fila es la última entrada de la fila anterior; otras entradas son\(A_{n,k}=A_{n,k-1}+A_{n-1,k-1}\); fila\(n\) tiene\(n\) entradas. Tanto la primera columna como la diagonal consisten en los números de Campana, con\(A_{n,1}=B_{n-1}\) y\(A_{n,n}=B_n\).
\(A_{n,k}\)puede interpretarse como el número de particiones\(\{1,2,\ldots,n+1\}\) en las que\(\{k+1\}\) se encuentra el conjunto singleton con la entrada más grande en la partición. Por ejemplo,\(A_{3,2}=3\); las particiones de\(3+1=4\) en las que\(2+1=3\) es el mayor número que aparece en un conjunto singleton son\(\{\{1\},\{2,4\},\{3\}\}\),\(\{\{2\},\{1,4\},\{3\}\}\), y\(\{\{1,2,4\},\{3\}\}\).
Para ver que esto efectivamente funciona como se anuncia, necesitamos confirmar algunas cosas. Primero, considere\(A_{n,n}\), el número de particiones\(\{1,2,\ldots,n+1\}\) en las que\(\{n+1\}\) se encuentra el conjunto singleton con la entrada más grande en la partición. Dado que\(n+1\) es el elemento más grande del conjunto, todas las particiones que contienen el singleton\(\{n+1\}\) satisfacen el requisito, y así las\(B_n\) particiones de\(\{1,2,\ldots,n\}\) junto con\(\{n+1\}\) son exactamente las particiones de interés, es decir,\(A_{n,n}=B_n\).
A continuación, verificamos que bajo la interpretación deseada, efectivamente es cierto que\(A_{n,k}=A_{n,k-1}+A_{n-1,k-1}\) para\(k>1\). Considera una partición contada por\(A_{n,k-1}\). Esto contiene el singleton\(\{k\}\), y el elemento no\(k+1\) está en un singleton. Si cambiamos\(k\) y\(k+1\), obtenemos el singleton\(\{k+1\}\), y ningún elemento más grande está en un singleton. Esto nos da particiones en las que\(\{k+1\}\) es un singleton y no lo\(\{k\}\) es. Ahora considere una partición de\(\{1,2,\ldots,n\}\) contado por\(A_{n-1,k-1}\). Reemplace todos los números\(j>k\) por\(j+1\), y agregue el singleton\(\{k+1\}\). Esto produce una partición en la que ambos\(\{k+1\}\) y\(\{k\}\) aparecen. De hecho, hemos descrito cómo producir cada partición contada por\(A_{n,k}\) exactamente una vez, y así\(A_{n,k}=A_{n,k-1}+A_{n-1,k-1}\).
Por último, tenemos que verificarlo\(A_{n,1}=B_{n-1}\). Eso lo sabemos\(A_{1,1}=1=B_0\). Ahora afirmamos que para\(n>1\),\[ A_{n,1}=\sum_{k=0}^{n-2}{n-2\choose k}A_{k+1,1}. \nonumber\]
En una partición contada por\(A_{n,1}\), 2 es el elemento más grande en un singleton, por lo que no\(\{n+1\}\) está en la partición. Elija cualquier\(k\ge 1\) elemento de\(\{3,4,\ldots,n\}\) para formar el conjunto que contiene\(n+1\). Hay\(A_{n-k-1,1}\) particiones de los\(n-k\) elementos restantes en las que 2 es el elemento más grande en un singleton. Esto da cuenta de\({n-2\choose k}A_{n-k-1,1}\) particiones de\(\{1,2,\ldots,n+1\}\), o sobre todo\(k\):\[ \sum_{k=1}^{n-2}{n-2\choose k}A_{n-k-1,1}= \sum_{k=1}^{n-2}{n-2\choose n-k-2}A_{n-k-1,1}= \sum_{k=0}^{n-3} {n-2\choose k}A_{k+1,1}.\nonumber\]
Nos faltan esas particiones en las que 1 está en la parte que contiene\(n+1\). Podemos producir todas esas particiones comenzando con una partición contada por\(A_{n-1,1}\) y agregando\(n+1\) a la parte que contiene 1. Ahora tenemos\[A_{n,1} = A_{n-1,1}+\sum_{k=0}^{n-3} {n-2\choose k}A_{k+1,1}= \sum_{k=0}^{n-2} {n-2\choose k}A_{k+1,1}.\nonumber\]
Aunque ligeramente disfrazado por la indexación desplazada del\(A_{n,1}\), esta es la misma que la relación de recurrencia para el\(B_n\), y así\(A_{n,1}=B_{n-1}\) como se desee.