Número de Wedderburn-Etherington

Los números de Wedderburn-Etherington son una secuencia de números enteros que lleva el nombre de Ivor Malcolm Haddon Etherington ^{[1] [2]} y Joseph Wedderburn ^[3] y que se pueden 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 de nutria y árboles binarios débiles, dos tipos de árboles binarios con raíces contados mediante los números de Wedderburn-Etherington

Estos números se pueden utilizar para resolver varios problemas de enumeración combinatoria . El número n de la secuencia (que comienza con el número 0 para n  = 0) cuenta

• Número de árboles con raíces desordenados con n hojas en los que todos los nodos, incluida la raíz, tienen cero o exactamente dos hijos. ^[4] Estos árboles se han denominado árboles Otter, ^[5] en honor al trabajo de Richard Otter sobre su enumeración combinatoria. ^[6] También se pueden interpretar como dendrogramas sin etiquetar ni clasificar con el número de hojas dado. ^[7]
• 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 demás nodos tengan como máximo dos hijos define los árboles binarios débiles. En la teoría de grafos químicos , estos árboles se pueden interpretar 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 para el torneo). ^[9] Los emparejamientos de un torneo de este tipo se pueden describir 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 que 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 se puede interpretar como una expresión agrupada en la que cada nodo hoja corresponde a una de las copias de 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, se puede interpretar 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}}$

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

En términos de la interpretación de estos números como el conteo de árboles binarios con raíz y n hojas, la suma en la recurrencia cuenta las diferentes maneras 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 ligeramente más complicada que la fórmula para valores impares con el fin de evitar el doble conteo de árboles con el mismo número de hojas en ambos subárboles. ^[7]

Índice 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 se va a cifrar mediante su sistema puede comprimirse lo suficiente mediante 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 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 un número muy pequeño de bits, el logaritmo en 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 con raíz, basada en la partición de los árboles en subárboles pequeños y la codificación de cada subárbol como un número limitado por el número de Wedderburn-Etherington para su tamaño. Su esquema permite codificar estos árboles 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 tiempo que permite operaciones de navegación en tiempo constante dentro del árbol. ^[13]

Iserles y Nørsett (1999) utilizan árboles binarios no ordenados y el hecho de que los números de Wedderburn-Etherington son significativamente más pequeños que los números que cuentan los á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]

Véase 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 ", Anales de Matemáticas , 24 (2): 121–140, doi :10.2307/1967710, JSTOR  1967710 ${\displaystyle g(x^{2})=2ax+[g(x)]^{2}}$.
4. Sloane, N. J. A. (ed.). "Secuencia A001190". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS..
5. 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.
6. Otter, Richard (1948), "El número de árboles", Anales de Matemáticas , Segunda Serie, 49 (3): 583–599, doi :10.2307/1969046, JSTOR  1969046, MR  0025715.
7. Murtagh, Fionn (1984), "Conteo de dendrogramas: una encuesta", Matemáticas Aplicadas Discretas , 7 (2): 191–199, doi : 10.1016/0166-218X(84)90066-0 , MR  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 torneo 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), "Structural rigidity. II. Almost infinitesimally rigid bar frameworks", Discrete Applied Mathematics , 13 (1): 41–59, doi : 10.1016/0166-218X(86)90068-5 , MR  0829338 , afirma que esta equivalencia entre árboles y elementos del magma conmutativo libre en un generador es "bien conocida y fácil de ver "..
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. Young, Adam; Yung, Moti (2003), "Ataques de puerta trasera a cifrados de caja negra que explotan textos planos de baja entropía", Actas de la 8.ª Conferencia Australasiana sobre Seguridad de la Información y Privacidad (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", Algorithm theory—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, Sr.  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. Series A: Mathematical, Physical and Engineering Sciences , 357 (1754): 983–1019, Bibcode :1999RSPTA.357..983I, doi :10.1098/rsta.1999.0362, MR  1694700, S2CID  90949835.

Lectura adicional

• Finch, Steven R. (2003), Constantes matemáticas, Enciclopedia de 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, Sr.  2003519.