Número de Wedderburn-Etherington

Los números de Wedderburn-Etherington son una secuencia de enteros que lleva el nombre de Ivor Malcolm Haddon Etherington ^{[1] [2]} y Joseph Wedderburn ^[3] que se puede utilizar para contar ciertos tipos de árboles binarios . Los primeros números de la secuencia son

0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, ... ( OEIS : A001190 )

Interpretación combinatoria

Árboles nutria y árboles débilmente binarios, dos tipos de árboles binarios enraizados contados según los números de Wedderburn-Etherington

Estos números se pueden utilizar para resolver varios problemas de enumeración combinatoria . El enésimo número de 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 sobre su enumeración combinatoria. ^[6] También pueden interpretarse como dendrogramas sin etiquetar ni clasificar con el número de hojas dado. ^[7]
• El número de árboles con raíces desordenadas 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 tengan como máximo dos hijos define los árboles débilmente binarios. En la teoría química de grafos , 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 clasificar a los jugadores en el torneo). ^[9] Los emparejamientos de dicho torneo pueden describirse mediante un árbol Otter.
• 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 es conmutativa pero no asociativa ni idempotente . ^[4] Por ejemplo, se pueden agrupar 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 Otter puede interpretarse como una expresión agrupada en la que cada nodo hoja corresponde a una de las copias y 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, puede interpretarse como el magma conmutativo libre en un generador (el árbol con un nodo ). En esta estructura algebraica, cada agrupación de tiene como valor uno de los árboles Otter de n hojas. ^[10] ${\displaystyle x^{n}}$ ${\displaystyle x^{5}}$ ${\displaystyle x(x(x(xx)))}$ ${\displaystyle x((xx)(xx))}$ ${\displaystyle (xx)(x(xx))}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x^{n}}$

Fórmula

Los números de Wedderburn-Etherington se pueden calcular utilizando la relación de recurrencia

${\displaystyle a_{2n-1}=\sum _{i=1}^{n-1}a_{i}a_{2n-i-1}}$

${\displaystyle a_{2n}={\frac {a_{n}(a_{n}+1)}{2}}+\sum _{i=1}^{n-1}a_{i}a_{2n-i}}$

comenzando con el caso base . ^[4] ${\displaystyle a_{1}=1}$

En términos de la interpretación de estos números como contar á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 tiene 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 para evitar el doble conteo 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

${\displaystyle a_{n}\approx {\sqrt {\frac {\rho +\rho ^{2}B'(\rho ^{2})}{2\pi }}}{\frac {\rho ^{-n}}{n^{3/2}}},}$

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 de un diseño para un sistema de cifrado que contiene una puerta trasera oculta . Cuando una entrada que su sistema va a cifrar puede comprimirse lo suficiente mediante la codificación Huffman , se reemplaza por el formato comprimido 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 manera, la codificación utiliza una cantidad muy pequeña de bits, el logaritmo de base 2 del número de 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 una cantidad de bits cercana al límite inferior de la teoría de la información (el logaritmo de base 2 del número de Wedderburn-Etherington) y al mismo tiempo permite operaciones de navegación en 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

1. Etherington, IMH (1937), "Potencias no asociadas y una ecuación funcional", Mathematical Gazette , 21 (242): 36–39, 153, doi :10.2307/3605743, JSTOR  3605743, S2CID  126360684.
2. Etherington, IMH (1939), "Sobre combinaciones no asociativas", Proc. R. Soc. Edimburgo , 59 (2): 153–162, doi :10.1017/S0370164600012244.
3. Wedderburn, JHM (1923), "La ecuación funcional ", Annals of Mathematics , 24 (2): 121–140, doi :10.2307/1967710, JSTOR  1967710 ${\displaystyle g(x^{2})=2ax+[g(x)]^{2}}$.
4. Sloane, Nueva Jersey (ed.). "Secuencia A001190". La enciclopedia en línea de secuencias enteras . Fundación OEIS..
5. Bona, 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, señor  2582703, S2CID  5452364.
6. Otter, Richard (1948), "El número de árboles", Annals of Mathematics , segunda serie, 49 (3): 583–599, doi :10.2307/1969046, JSTOR  1969046, MR  0025715.
7. Murtagh, Fionn (1984), "Contar dendrogramas: una encuesta", Matemáticas aplicadas discretas , 7 (2): 191–199, doi : 10.1016/0166-218X(84)90066-0 , SEÑOR  0727923.
8. 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.
9. Maurer, Willi (1975), "Sobre los planes de torneos más efectivos con menos juegos que los competidores", The Annals of Statistics , 3 (3): 717–727, doi : 10.1214/aos/1176343135 , JSTOR  2958441, MR  0371712.
10. ^ Rosenberg, IG (1986), "Rigidez estructural. II. Estructuras de barras casi infinitamente rígidas", Discrete Applied esta equivalencia entre árboles y elementos del magma conmutativo libre en un generador es "bien conocida y fácil de ver". Matemáticas , 13 (1): 41–59, doi : 10.1016/0166-218X(86)90068-5 , SEÑOR  0829338.
11. 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.
12. Joven, Adán; Yung, Moti (2003), "Ataques de puerta trasera a cifrados de caja negra que explotan textos planos de baja entropía", Actas de la octava Conferencia de Australasia sobre seguridad y privacidad de la información (ACISP'03) , Lecture Notes in Computer Science , vol. 2727, Springer, págs. 297–311, doi :10.1007/3-540-45067-X_26, ISBN 978-3-540-40515-3.
13. 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, vol. 5124, Springer, págs. 173–184, doi :10.1007/978-3-540-69903-3_17, ISBN 978-3-540-69900-2, señor  2497008.
14. Iserles, A.; Nørsett, SP (1999), "Sobre la solución de ecuaciones diferenciales lineales en grupos de Lie", Philosophical Transactions of the Royal Society of London. Serie A: Ciencias matemáticas, físicas y de 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, vol. 94, Cambridge: Cambridge University Press, págs. 295–316, doi :10.1017/CBO9780511550447, ISBN 978-0-521-81805-6, SEÑOR  2003519.