Los números de Wedderburn-Etherington son una secuencia entera llamada así por Ivor Malcolm Haddon Etherington [1] [2] y Joseph Wedderburn [3] que se pueden usar para contar ciertos tipos de árboles binarios . Los primeros números de la secuencia son
Interpretación combinatoria
Estos números se pueden utilizar para resolver varios problemas de enumeración combinatoria . El n- ésimo número en la secuencia (comenzando con el número 0 para n = 0) cuenta
- El número de árboles enraizados desordenados con n hojas en los que todos los nodos, incluida la raíz, tienen cero o exactamente dos hijos. [4] Estos árboles han sido llamados árboles Otter , [5] por el trabajo de Richard Otter en su enumeración combinatoria. [6] También se pueden interpretar como dendrogramas sin etiquetar y sin clasificar con el número de hojas dado. [7]
- El número de árboles enraizados desordenados con n nodos en los que la raíz tiene grado cero o uno y todos los demás nodos tienen como máximo dos hijos. [4] Los árboles en los que la raíz tiene como máximo un hijo se denominan árboles plantados , y la condición adicional de que los otros nodos tienen como máximo dos hijos define los árboles débilmente binarios . En la teoría de grafos químicos , estos árboles pueden interpretarse como isómeros de polienos con un átomo de hoja designado elegido como raíz. [8]
- El número de formas diferentes de organizar un torneo de eliminación simple para n jugadores (con los nombres de los jugadores en blanco, antes de sembrar jugadores en el torneo). [9] Las parejas de un torneo de este tipo pueden describirse mediante un árbol de nutria.
- El número de resultados diferentes que podrían generarse mediante diferentes formas de agrupar la expresión. para una operación de multiplicación binaria que se supone conmutativa pero no asociativa ni idempotente . [4] Por ejemplo pueden agruparse en multiplicaciones binarias de tres formas, como , , o . Esta fue la interpretación considerada originalmente tanto por Etherington [1] [2] como por Wedderburn. [3] Un árbol de nutria se puede interpretar como una expresión agrupada en la que cada nodo hoja corresponde a una de las copias dey cada nodo no hoja corresponde a una operación de multiplicación. En la otra dirección, el conjunto de todos los árboles Otter, con una operación de multiplicación binaria que combina dos árboles convirtiéndolos en los dos subárboles de un nuevo nodo raíz, se puede interpretar como el magma conmutativo libre en un generador.(el árbol con un nodo). En esta estructura algebraica, cada agrupación detiene como valor uno de los árboles de nutria de n hojas. [10]
Fórmula
Los números de Wedderburn-Etherington se pueden calcular utilizando la relación de recurrencia
comenzando con el caso base . [4]
En términos de la interpretación de estos números como el recuento de árboles binarios enraizados con n hojas, la suma en la recurrencia cuenta las diferentes formas de dividir estas hojas en dos subconjuntos y de formar un subárbol que tenga cada subconjunto como sus hojas. La fórmula para valores pares de n es un poco más complicada que la fórmula para valores impares con el fin de evitar el conteo doble de árboles con el mismo número de hojas en ambos subárboles. [7]
Tasa de crecimiento
Los números de Wedderburn-Etherington crecen asintóticamente a medida que
donde B es la función generadora de los números y ρ es su radio de convergencia , aproximadamente 0.4027 (secuencia A240943 en la OEIS ), y donde la constante dada por la parte de la expresión en la raíz cuadrada es aproximadamente 0.3188 (secuencia A245651 en la OEIS ). [11]
Aplicaciones
Young y Yung (2003) utilizan los números de Wedderburn-Etherington como parte del diseño de un sistema de cifrado que contiene una puerta trasera oculta . Cuando una entrada para ser encriptada por su sistema puede ser suficientemente comprimida por la codificación de Huffman , se reemplaza por la forma comprimida junto con información adicional que filtra datos clave al atacante. En este sistema, la forma del árbol de codificación de Huffman se describe como un árbol de Otter y se codifica como un número binario en el intervalo de 0 al número de Wedderburn-Etherington para el número de símbolos en el código. De esta forma, la codificación utiliza un número muy pequeño de bits, el logaritmo en base 2 del número Wedderburn-Etherington. [12]
Farzan y Munro (2008) describen una técnica de codificación similar para árboles binarios desordenados enraizados, basada en dividir los árboles en pequeños subárboles y codificar cada subárbol como un número limitado por el número de Wedderburn-Etherington para su tamaño. Su esquema permite que estos árboles se codifiquen en un número de bits cercano al límite inferior de la teoría de la información (el logaritmo en base 2 del número de Wedderburn-Etherington) al mismo tiempo que permite operaciones de navegación de tiempo constante dentro del árbol. [13]
Iserles y Nørsett (1999) utilizan árboles binarios desordenados, y el hecho de que los números de Wedderburn-Etherington son significativamente más pequeños que los números que cuentan árboles binarios ordenados, para reducir significativamente el número de términos en una representación en serie de la solución de ciertas ecuaciones diferenciales. . [14]
Ver también
- Número catalán
Referencias
- ↑ a b Etherington, IMH (1937), "Poderes no asociados y una ecuación funcional", Mathematical Gazette , 21 (242): 36–39, 153, doi : 10.2307 / 3605743 , JSTOR 3605743.
- ^ a b Etherington, IMH (1939), "Sobre combinaciones no asociativas", Proc. Royal Soc. Edimburgo , 59 (2): 153–162, doi : 10.1017 / S0370164600012244.
- ^ a b Wedderburn, JHM (1923), "La ecuación funcional", Annals of Mathematics , 24 (2): 121–140, doi : 10.2307 / 1967710 , JSTOR 1967710.
- ^ a b c d Sloane, N. J. A. (ed.). "Secuencia A001190" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS..
- ^ Bóna, Miklós ; Flajolet, Philippe (2009), "Isomorfismo y simetrías en árboles filogenéticos aleatorios", Journal of Applied Probability , 46 (4): 1005-1019, arXiv : 0901.0696 , Bibcode : 2009arXiv0901.0696B , doi : 10.1239 / jap / 1261670685 , MR 2582703 , S2CID 5452364.
- ^ Otter, Richard (1948), "El número de árboles", Annals of Mathematics , Second Series, 49 (3): 583–599, doi : 10.2307 / 1969046 , JSTOR 1969046 , MR 0025715.
- ^ a b Murtagh, Fionn (1984), "Contando dendrogramas: una encuesta", Matemáticas aplicadas discretas , 7 (2): 191-199, doi : 10.1016 / 0166-218X (84) 90066-0 , MR 0727923.
- ^ Cyvin, SJ; Brunvoll, J .; Cyvin, BN (1995), "Enumeración de isómeros constitucionales de polienos", Journal of Molecular Structure: THEOCHEM , 357 (3): 255-261, doi : 10.1016 / 0166-1280 (95) 04329-6.
- ^ Maurer, Willi (1975), "Sobre los planes de torneo más eficaces con menos juegos que los competidores", The Annals of Statistics , 3 (3): 717–727, doi : 10.1214 / aos / 1176343135 , JSTOR 2958441 , MR 0371712.
- ^ Esta equivalencia entre árboles y elementos del magma conmutativo libre en un generador se afirma que es "bien conocida y fácil de ver" por Rosenberg, IG (1986), "Rigidez estructural. II. Armazones de barras casi infinitesimalmente rígidos", Matemáticas aplicadas discretas , 13 (1): 41–59, doi : 10.1016 / 0166-218X (86) 90068-5 , MR 0829338.
- ^ Landau, BV (1977), "Una expansión asintótica para la secuencia de Wedderburn-Etherington", Mathematika , 24 (2): 262-265, doi : 10.1112 / s0025579300009177 , MR 0498168.
- ^ Young, Adam; Yung, Moti (2003), "Ataques de puerta trasera a cifrados de caja negra que explotan textos sin formato de baja entropía", Actas de la 8a Conferencia Australasia sobre Seguridad y Privacidad de la Información (ACISP'03) , Lecture Notes in Computer Science , 2727 , Springer, págs . 297–311, doi : 10.1007 / 3-540-45067-X_26 , ISBN 978-3-540-40515-3.
- ^ Farzan, Arash; Munro, J. Ian (2008), "Un enfoque uniforme hacia la representación sucinta de árboles", Teoría de algoritmos — SWAT 2008 , Lecture Notes in Computer Science, 5124 , Springer, pp. 173-184, doi : 10.1007 / 978-3- 540-69903-3_17 , MR 2497008.
- ^ Iserles, A .; Nørsett, SP (1999), "Sobre la solución de ecuaciones diferenciales lineales en grupos de Lie" , Transacciones filosóficas de la Royal Society de Londres. Serie A: Ciencias Matemáticas, Físicas e Ingeniería , 357 (1754): 983–1019, Bibcode : 1999RSPTA.357..983I , doi : 10.1098 / rsta.1999.0362 , MR 1694700 , S2CID 90949835.
Otras lecturas
- Finch, Steven R. (2003), Constantes matemáticas , Enciclopedia de las matemáticas y sus aplicaciones, 94 , Cambridge: Cambridge University Press, págs. 295–316 , doi : 10.1017 / CBO9780511550447 , ISBN 978-0-521-81805-6, Señor 2003519.