Número de Bell

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 B0 = B1 = 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, Bn, 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, Bn es el enésimo momento de una distribución de Poisson con media.

Contando[editar]

Particiones de un conjunto[editar]

Artículo principal: Partición de un conjunto

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

Ejemplo

porque el conjunto de tres elementos se puede dividir de 5 formas distintas.

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 . 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:
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[editar]

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

Ejemplo

es el producto de los tres primos 2, 3 y 5, y tiene factorizaciones:

Permutaciones[editar]

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 nn diferentes barajados que pueden ser realizado. De estos, el número que devuelve el mazo a su orden original ordenado es exactamente Bn. Por lo tanto, la probabilidad de que la baraja esté en su orden original después de mezclarla de esta manera es Bn/nn, ¡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 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 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[editar]

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.

  1. Comience con el número uno. Pon esto en una fila por sí mismo.
  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 (i-1) -ª fila)
  3. 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
  4. 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 )
  5. El número en el lado izquierdo de una fila dada es el número de Bell para esa fila.

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[editar]

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

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

El número de Stirling 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:

Función de generación[editar]

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

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

Aquí, es una clase combinatoria con un solo miembro de tamaño uno, un elemento que se puede colocar en una urna. El operador interno describe un conjunto o urna que contiene uno o más elementos etiquetados, y el outer 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 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 . La función en sí se puede encontrar al resolver esta ecuación.

Representación integral[editar]

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

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[editar]

Los números de Bell forman una secuencia logarítmica convexa. Dividiéndolos por los factoriales,, obtienes la secuencia logarítmica convexa.

Momentos de las distribuciones de probabilidades[editar]

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

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 pueda ser interpretado como el enésimo momento de una distribución de Poisson con el valor esperado .

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 cumulantes.

Aritmética Modular[editar]

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

o generalizando:

Por consecuencia de la congruencia de Touchard, los números de Bell son periódicos con módulo , por cada número primo . Por ejemplo si , 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 , debe ser un divisor de:

Y para todos los números primos o o el número de la secuencia A001039 en OEIS

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

(Es la secuencia A054767 en OEIS)

Bell principales[editar]

Gardner (1978) planteó la cuestión de si infinitamente muchos números Bell también son números 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 próximo Bell principal es B2841, que es aproximadamente 9.30740105 × 106538. A partir de 2006, es el número de Bell principal más grande conocido. Phil Carmody demostró que era probable su mejor momento 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 el mejor en 2004. Descartó otros posibles números primos por debajo de B6000, luego extendidos a B30447 por Eric Weisstein.

Historia del Número de Bell[editar]

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 Bn 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 B5 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[editar]

Referencias[editar]

  • 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. Amsterdam, Países Bajos: North-Holland, 1993.

Enlaces externos[editar]