En matemáticas, el triángulo de Bell es un triángulo de números análogo al triángulo de Pascal , cuyos valores cuentan las particiones de un conjunto en el que un elemento dado es el singleton más grande . Se llama así por su estrecha conexión con los números de Bell , [1] que se pueden encontrar en ambos lados del triángulo, y que a su vez llevan el nombre de Eric Temple Bell . El triángulo de Bell ha sido descubierto de forma independiente por múltiples autores, comenzando con Charles Sanders Peirce ( 1880 ) e incluyendo también a Alexander Aitken ( 1933 ) y Cohn et al. (1962), y por esa razón también se le ha llamado matriz de Aitken o triángulo de Peirce . [2]
Valores
Diferentes fuentes dan el mismo triángulo en diferentes orientaciones, algunas volteadas entre sí. [3] En un formato similar al del triángulo de Pascal, y en el orden que aparece en la Enciclopedia en línea de secuencias de enteros , sus primeras filas son: [2]
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 52 67 87114151203203255322409523674877
Construcción
El triángulo de Bell se puede construir colocando el número 1 en su primera posición. Después de esa ubicación, el valor más a la izquierda en cada fila del triángulo se rellena copiando el valor más a la derecha en la fila anterior. Las posiciones restantes en cada fila se llenan con una regla muy similar a la del triángulo de Pascal : son la suma de los dos valores a la izquierda y arriba a la izquierda de la posición.
Por lo tanto, después de la colocación inicial del número 1 en la fila superior, es la última posición en su fila y se copia en la posición más a la izquierda en la fila siguiente. El tercer valor en el triángulo, 2, es la suma de los dos valores anteriores arriba a la izquierda y a la izquierda. Como último valor de su fila, el 2 se copia en la tercera fila y el proceso continúa de la misma manera.
Interpretación combinatoria
Los propios números de Bell , en los lados izquierdo y derecho del triángulo, cuentan el número de formas de dividir un conjunto finito en subconjuntos, o de manera equivalente, el número de relaciones de equivalencia en el conjunto. Sun y Wu (2011) proporcionan la siguiente interpretación combinatoria de cada valor en el triángulo. Después de Sun y Wu, dejar que A n, k denota el valor que es k posiciones de la izquierda en el n º fila del triángulo, con la parte superior del triángulo numerada como A 1,1 . Entonces A n, k cuenta el número de particiones del conjunto {1, 2, ..., n + 1} en el que el elemento k + 1 es el único elemento de su conjunto y cada elemento de número superior está en un conjunto de más de un elemento. Es decir, k + 1 debe ser el singleton más grande de la partición.
Por ejemplo, el número 3 en el medio de la tercera fila del triángulo se etiquetaría, en su notación, como A 3,2 , y cuenta el número de particiones de {1, 2, 3, 4} en las que 3 es el elemento singleton más grande. Hay tres particiones de este tipo:
- {1}, {2, 4}, {3}
- {1, 4}, {2}, {3}
- {1, 2, 4}, {3}.
Las particiones restantes de estos cuatro elementos no tienen 3 en un conjunto por sí mismas, o tienen un conjunto singleton más grande {4}, y en cualquier caso no se cuentan en A 3,2 .
En la misma notación, Sun & Wu (2011) aumentan el triángulo con otra diagonal a la izquierda de sus otros valores, de los números
contando particiones del mismo conjunto de n + 1 elementos en los que solo el primer elemento es un singleton. Su triángulo aumentado es [4]
1 0 1 1 1 2 1 2 3 5 4 5 7 10 15 11 15 20 27 37 52 41 52 67 87114151203162203255322409523674877
Este triángulo se puede construir de manera similar a la versión original del triángulo de Bell, pero con una regla diferente para comenzar cada fila: el valor más a la izquierda en cada fila es la diferencia de los valores más a la derecha y más a la izquierda de la fila anterior.
Quaintance & Kwong (2013) dan una interpretación alternativa pero más técnica de los números en el mismo triángulo aumentado .
Diagonales y sumas de filas
Las diagonales más a la izquierda y más a la derecha del triángulo de Bell contienen la secuencia 1, 1, 2, 5, 15, 52, ... de los números de Bell (con el elemento inicial que falta en el caso de la diagonal más a la derecha). La siguiente diagonal paralela a la diagonal más a la derecha da la secuencia de diferencias de dos números de Bell consecutivos, 1, 3, 10, 37, ..., y cada diagonal paralela subsiguiente da la secuencia de diferencias de diagonales anteriores.
De esta manera, como observó Aitken (1933) , este triángulo se puede interpretar como implementando la fórmula de interpolación de Gregory-Newton , que encuentra los coeficientes de un polinomio a partir de la secuencia de sus valores en números enteros consecutivos usando diferencias sucesivas. Esta fórmula se parece mucho a una relación de recurrencia que se puede utilizar para definir los números de Bell.
Las sumas de cada fila del triángulo, 1, 3, 10, 37, ..., son la misma secuencia de las primeras diferencias que aparecen en la segunda diagonal desde la derecha del triángulo. [5] El número n en esta secuencia también cuenta el número de particiones de n elementos en subconjuntos, donde uno de los subconjuntos se distingue de los demás; por ejemplo, hay 10 formas de dividir tres elementos en subconjuntos y luego elegir uno de los subconjuntos. [6]
Construcciones relacionadas
Aigner (1999) describió un triángulo de números diferente, con los números de Bell en un solo lado, y con cada número determinado como una suma ponderada de números cercanos en la fila anterior .
Notas
- ↑ Según Gardner (1978) , este nombre fue sugerido por Jeffrey Shallit , cuyo artículo sobre el mismo triángulo se publicó más tarde como Shallit (1980) . A su vez, deberá acreditar a Cohn et al. (1962) para la definición del triángulo, pero Cohn et al. no nombró el triángulo.
- ↑ a b Sloane, N. J. A. (ed.). "Secuencia A011971 (matriz de Aitken)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ↑ Por ejemplo, Gardner (1978) muestra dos orientaciones, ambas diferentes a la de aquí.
- ^ Sloane, N. J. A. (ed.). "Secuencia A106436" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ Gardner (1978) .
- ^ Sloane, N. J. A. (ed.). "Secuencia A005493" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS..
Referencias
- Aigner, Martin (1999), "Una caracterización de los números de Bell", Discrete Mathematics , 205 (1-3): 207-210, doi : 10.1016 / S0012-365X (99) 00108-9 , MR 1703260.
- Aitken, AC (1933), "Un problema en combinaciones", Notas matemáticas , 28 : 18–23, doi : 10.1017 / S1757748900002334.
- Cohn, Martin; Incluso, Shimon ; Menger, Karl, Jr .; Hooper, Philip K. (1962), "Notas matemáticas: sobre el número de particiones de un conjunto de n objetos distintos", American Mathematical Monthly , 69 (8): 782–785, doi : 10.2307 / 2310780 , MR 1531841.
- Gardner, Martin (1978), "The Bells: números versátiles que pueden contar particiones de un conjunto, números primos e incluso rimas", Scientific American , 238 : 24–30, doi : 10.1038 / scientificamerican0578-24. Reimpreso con un apéndice como "The Tinkly Temple Bells", Capítulo 2 de Fractal Music, Hypercards, y más ... Recreaciones matemáticas de Scientific American , WH Freeman, 1992, págs. 24–38.
- Peirce, CS (1880), "Sobre el álgebra de la lógica", American Journal of Mathematics , 3 (1): 15–57, doi : 10.2307 / 2369442 , JSTOR 2369442. El triángulo está en la p. 48.
- Quaintance, Jocelyn; Kwong, Harris (2013), "Una interpretación combinatoria de las tablas de diferencias numéricas de Catalán y Bell" (PDF) , Integers , 13 : A29.
- Shallit, Jeffrey (1980), "Un triángulo para los números de Bell", Una colección de manuscritos relacionados con la secuencia de Fibonacci (PDF) , Santa Clara, Calif .: Fibonacci Association, págs. 69–71, MR 0624091.
- Sun, Yidong; Wu, Xiaojuan (2011), "Los mayores singletons de particiones de conjuntos", European Journal of Combinatorics , 32 (3): 369–382, arXiv : 1007.1341 , doi : 10.1016 / j.ejc.2010.10.011 , MR 2764800.
enlaces externos
- Weisstein, Eric W. "Bell Triangle" . MathWorld .