Números de Schroeder-Hipparchus

Los números de Schroeder-Hipparchus forman una secuencia de enteros que se pueden usar para contar el número de plátanos con un número determinado de hojas , el número de formas de insertar corchetes en la secuencia y el número de formas de dividir un polígono convexo en polígonos más pequeños dibujando diagonales. Esta secuencia comienza con

1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ... Secuencia OEIS A001003 .

Estos números también se denominan números supercatalanos , pequeños números de Schroeder o números de Hipparchus ( Eugene Charles Catalan y sus números catalanes , Ernst Schroeder y los números de Schroeder estrechamente relacionados , el antiguo matemático griego Hipparchus , quien, según Plutarco , conocía estos números).

Aplicaciones para enumeraciones combinatorias

Los números de Schroeder-Hipparchus se pueden usar para contar algunos objetos combinatorios estrechamente relacionados [1] [2] [3] [4] :

Como muestra la figura, existe una equivalencia combinatoria simple entre estos objetos: una partición poligonal tiene un árbol plano como gráfico dual , las hojas de este árbol corresponden a los caracteres en la secuencia de paréntesis y los vértices internos del árbol distintos de la raíz corresponde a los grupos de corchetes. Se puede escribir una secuencia entre corchetes alrededor del perímetro de un polígono con símbolos en los lados y corchetes en los extremos de las diagonales elegidas. Esta equivalencia da una prueba biyectiva de que todos estos tipos de objetos se cuentan por una secuencia entera [2] .

Los mismos números también cuentan el número de permutaciones dobles (secuencias de números del 1 al n , cada número aparece dos veces, y cada número aparece por primera vez en orden ordenado), que evitan los patrones de permutación 12312 y 121323 [5 ] .

Secuencias relacionadas

Los grandes números de Schroeder estrechamente relacionados son iguales al doble de los números de Schroeder-Hipparchus y también se pueden usar para contar algunos tipos de objetos combinatorios, incluidos algunos tipos de caminos en una red, dividir un rectángulo en rectángulos más pequeños mediante división recursiva y paréntesis cuando también se permite un par de paréntesis, incluida la secuencia completa de elementos. Los números catalanes también cuentan conjuntos de objetos estrechamente relacionados, incluidas las subdivisiones de un polígono en triángulos, árboles planos en los que todos los vértices interiores tienen exactamente dos hijos y el espaciado entre corchetes donde cada par de corchetes rodea exactamente dos caracteres o grupos de corchetes [3] .

La secuencia numérica catalana y la secuencia numérica de Schroeder-Hipparchus, cuando se consideran vectores de dimensión infinita, son los únicos vectores propios para los dos primeros de la secuencia de operadores lineales definidos naturalmente en secuencias de números [6] [7] . Más generalmente, la k -ésima secuencia en esta secuencia de secuencias enteras es , donde los números x n se calculan como sumas de los números de Narayana multiplicados por potencias de k . Esto se puede representar como una función hipergeométrica :

Sustituyendo k  = 1 en esta fórmula da los números catalanes, y sustituyendo k  = 2 en esta fórmula da los números de Schroeder-Hipparchus [7] .

Si el número de caras del asociaedro viene dado por los números de Schroeder-Hipparchus, entonces el número de vértices del asociaedro viene dado por los números catalanes. Los números correspondientes para el poliedro de permutación son, respectivamente, los números de Bell ordenados y los factoriales .

Recursividad

Como en la fórmula de sumatoria anterior, los números de Schroeder-Hipparchus se pueden determinar mediante la fórmula recursiva :

Stanley demostró este hecho usando secuencias generadoras de funciones [8] , mientras que Foata y Zeilberger dieron una prueba combinatoria directa [9] .

Historia

El diálogo de Plutarch (de Table Talk) contiene la línea:

Crisipo dice que el número de enunciados compuestos que se pueden hacer a partir de diez enunciados simples alcanza el millón. (Hipparchus sin duda refutó esto, mostrando que hay 103.049 afirmaciones complejas afirmativas y 310.952 negativas) [8] .

Esta afirmación permaneció sin explicación hasta 1994, cuando David Hough, estudiante de maestría en la Universidad George Washington , notó que había 103,049 formas de insertar corchetes en una cadena de diez elementos [1] [8] [10] . Se puede dar una explicación similar para otro número: está muy cerca del promedio de los diez números de Schroeder-Hipparchus 310954 y enumera todos los arreglos de paréntesis para los diez elementos junto con la partícula negativa [10] .

Schroeder [11] introdujo el problema de contar paréntesis en las matemáticas modernas .

El cálculo de Plutarco de dos números de Hiparco revela un desacuerdo entre Hiparco y el filósofo griego anterior Crisipo , quien argumentó que la cantidad de declaraciones complejas que se podían hacer a partir de diez declaraciones simples era tan alta como un millón. Suzanne Bobzin [12] , representante de la filosofía moderna , objetó que el cálculo de Crisipo era correcto, basado en un análisis de la lógica estoica . Susanna Bobzin ha reconstruido los cálculos tanto de Crisipo como de Hiparco, y afirmó que el método por el cual Hiparco obtuvo sus resultados matemáticamente correctos de su lógica estoica defectuosa arroja nueva luz sobre las nociones estoicas de conjunción y aserción [13] .


Notas

  1. ↑ 12 Stanley , 1999 , pág. Ejercicio 1.45, VI/51; VIII, /176–178, 213.
  2. ↑ 1 2 Shapiro, Sulanke, 2000 , pág. 369–376.
  3. ↑ 12 Etherington , 1940 , pág. 1–6.
  4. ↑ Holtkamp, ​​​​2006 , pág. 544–565.
  5. ↑ Chen, Mansour, Yan, 2006 , pág. Documento de investigación 112, 17 págs.
  6. ↑ Bernstein y Sloane 1995 , pág. 57–72.
  7. ↑ 12 Coker , 2004 , pág. 249–250.
  8. ↑ 1 2 3 Stanley, 1997 , pág. 344–350.
  9. ↑ Foata, Zeilberger, 1997 , pág. 380–384.
  10. ↑ 1 2 Acerbi, 2003 , p. 465–502.
  11. ↑ Schröder, 1870 , pág. 361–376.
  12. ↑ Bobzen, 2011 .
  13. ↑ Bobzien, 2011 , pág. 157–188.

Literatura

Enlaces