Alguna relación de equivalencia de voltear árboles binarios

Question

Sé casi nada en la combinatoria, por lo que esta pregunta puede ser muy fácil, o bien conocido.

Fijar un número $n$. Vamos a considerar arraigada planas de árboles binarios con $n$ hojas. Vamos a distinguir entre la raíz (algunos fijos vértice de valencia $1$), hojas (vértices de valencia $1$ que no son la raíz) y la interna de vértices (vértices de valencia $3$).

En estos árboles, podemos definir las siguientes operaciones. Para cualquier interior vértice $v$ de un árbol de $T$ podemos voltear las dos ramas que crecen de $v$ como se muestra en la imagen:

Entonces se dice que dos árboles de $T_1$ $T_2$ son equivalentes si uno puede ser obtenida de la otra por alguna combinación de las operaciones descritas anteriormente.

Así que mi pregunta es: ¿cómo podemos describir el conjunto de equivalencias de clases? Yo sería feliz con la respuesta del tipo: podemos (fácilmente) codificar los árboles en algunos "datos" y, a continuación, cada clase de equivalencia está representado por los "datos" que se cumplan algunas condiciones. Aquí los "datos" es tal vez una secuencia de números, o algo más (no sé combinatoria, así que no sé qué son las herramientas eficaces para tratar con este tipo de problema).

Muchas gracias por su ayuda!

Answer 1

Para ayudarle a aprender más acerca de esta clase de árboles en cuenta que ellos tienen el ordinario de generación de función $T(z)$ con la ecuación funcional (donde $[z^n] T(z)$ cuenta las clases de equivalencia en $n$ nodos) $$T(z) = 1 + \frac{1}{2} z T(z)^2 + \frac{1}{2} z T(z^2).$$ por el Polya enumeración teorema aplicado a $D_2,$ cuyo ciclo de índice es $\frac{1}{2}(q_1^2+q_2).$

Entrar en esta ecuación a tu favorito CAS para obtener la siguiente secuencia: $$1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, \ldots$$

Esta es la cantidad suficiente de datos para consultar la OEIS, donde encontramos que estos son los llamados Wedderburn-Etherington números.

Sabiendo que, a su vez, podamos consultar el MathWorld entrada, que tiene algunas buenas fotos. ¡A disfrutar!

El Arce de código para el segmento inicial de la ecuación funcional es este:

T_approx := q -> add(a[k]*z^k, k=0..p);

r := 1 + 1/2*z*T_approx(15)^2 + 1/2*z*subs(z=z^2, T_approx(15));
r_ex := expand(r):
nca := {seq(coef(r_ex, z, k) = a[k], k=0..15)}:

resolver(%);
subs(%, [seq(a[k], k=0..15)]);

Anexo 2015-02-16. Una manera mucho más eficiente de cálculo está dada por la relación de recurrencia $$t_n = \frac{1}{2}\sum_{q=0}^{n-1} t_q t_{n-1-p} + [[n-1\equiv 0\bmod 2]]\frac{1}{2} t_{(n-1)/2}$$ donde hemos usado la Iverson soporte y $t_0 = 1.$

Answer 2

Usted está buscando una representación canónica de árbol enraizado. Una tal representación puede dar como sigue (Aho, Hopcroft, Ullman):

Espero que esto ayude a $\ddot\smile$