Aquí es una solución a la arraigada caso, mientras esperamos a los expertos
unirse.
Las especies de arraigada sin etiquetar los árboles con los extremos marcados ha
especificación
$$\mathcal{T} = \mathcal{U}\mathcal{Z} +
\mathcal{Z}\mathfrak{M}_{\ge 1}(\mathcal{T}).$$
Esto le da a la funcional de la ecuación para la generación de la función
$$T(z, u) = uz+
z\left(-1+\exp\left(\sum_{l\ge 1} \frac{T(z^l, u^l)}{l}
\right)\right).$$
Una forma alternativa es
$$T(z, u) = uz+
z\left(-1+\prod_{l\ge 1} \exp\left(\frac{T(z^l, u^l)}{l}
\right)\right).$$
Esto le da la siguiente recurrencia para los coeficientes $T_n.$
Tenemos $T_1 = u$ $n\ge 2$ hemos
$$T_n = [z^{n-1}]
\left(-1 +
\exp\left(\sum_{l\ge 1} \frac{T(z^l, u^l)}{l}\right)\right).$$
Estos coeffients son polinomios en $u.$
Comenzar por la observación de que si
$$A(z, u) = \sum_{n\ge 1} A_n z^n =
\sum_{l\ge 1} \frac{T(z^l, u^l)}{l}$$
entonces
$$A_n = \sum_{l|n} \frac{\left.T_{n/l}\right|_{u=u^l}}{l}.$$
Re-escribir la ecuación funcional en términos de $A(z)$ rendimientos
$$T(z, u) = uz + z(-1 + \exp A(z, u))$$
y diferenciando con respecto a $z$ tenemos
$$T'(z, u) = u-1 + \exp A(z, u) + z \exp A(z, u) A'(z, u)$$
que es
$$T'(z, u) = u-1 + \frac{T(z,u)}{z} - u + 1 +
(T(z, u)- uz + z)'(z,u)$$
o $$z T'(z, u) = T(z, u) + z (T(z, u)- uz + z) A'(z,u).$$
La extracción de cofficients obtenemos
$$n T_n = T_n + [z^{n-1}] (T(z, u)- uz + z)'(z,u)
\\ = T_n + (1-u) [z^{n-2}] (z, u) +
\sum_{k=0}^{n-2} T_{n-1-k} (k+1) A_{k+1}
\\ = T_n + (1-u) (n-1) A_{n-1} +
\sum_{k=0}^{n-2} (k+1) A_{k+1} T_{n-1-k}.$$
Esto da para $T_n$ $n\ge 2$ la recurrencia
$$T_n = (1-u) A_{n-1} +
\frac{1}{n-1} \sum_{k=0}^{n-2} (k+1) A_{k+1} T_{n-1-k}.$$
Tenga en cuenta que el $A_n$ se definen recursivamente en términos de la $T_n$
por encima de.
Establecimiento $u=1$ en los polinomios $T_n$ los rendimientos de la secuencia:
$$1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973,
\\ 87811, 235381, 634847, 1721159, 4688676, 12826228,\ldots$$
que nos señala OEIS A000081donde
nos enteramos de que de verdad tiene los valores correctos.
Estas son las primeras distribuciones del número de estaciones de partida
con el árbol en un nodo:
$$u
\\u
\\{u}^{2}+u
\\{u}^{3}+2\,{u}^{2}+u
\\{u}^{4}+3\,{u}^{3}+4\,{u}^{2}+u
\\{u}^{5}+4\,{u}^{4}+8\,{u}^{3}+6\,{u}^{2}+u
\\{u}^{6}+5\,{u}^{5}+14\,{u}^{4}+18\,{u}^{3}+9\,{u}^{2}+u$$
Ahora, evidentemente, el número de árboles con un número par de puntos finales
está dada por
$$\frac{1}{2} \left(\left.T_n\right|_{u=1}+
\a la izquierda.T_n\right|_{u=-1}\right)$$
y para que sea impar el número de los extremos
$$\frac{1}{2} \left(\left.T_n\right|_{u=1}-
\a la izquierda.T_n\right|_{u=-1}\right).$$
Esto le da la siguiente secuencia de conteo de número de
extremos:
$$0, 0, 1, 2, 5, 10, 24, 57, 144, 360, 923, 2382, 6246, 16486, 43917,
\\ 117692, 317447, 860574, 2344396, 6413119, \ldots$$
y para que sea impar el número de los extremos
$$1, 1, 1, 2, 4, 10, 24, 58, 142, 359, 919, 2384, 6240, 16487, 43894,
\\ 117689, 317400, 860585, 2344280, 6413109, \ldots$$
La diferencia entre estos dos va como esto:
$$ -1, -1, 0, 0, 1, 0, 0, -1, 2, 1, 4, -2, 6, -1, 23, 3, 47, -11, 116,
\\ 10, 340, 13, 783, -14, 2181, 248, 5811, 321, 15026, 1335, 41660,
\\ 4938, 111237, 11384, 301857, 39610, 831896, 112673, 2263974, 315069,
\\ 6252982, 962897, 17280616, 2699066, 47760078, 7830950, 132931348,
\\ 22759720, 369884919, 64726655, 1032244936, 187331836, 2889218776,
\\ 537613196, 8093813288, 1540657359, 22732097026, 4436185030,
\\ 63945607606, 12718488294\ldots$$
así, en el caso de arraigada etiqueta árboles parecería haber un sesgo
hacia incluso los números de los extremos.
El siguiente Arce código fue usado para calcular estos valores. Es
incluye una rutina básica que puede ser utilizada para verificar los polinomios
para las pequeñas $n$ dice $n\le 7.$
con(numtheory);
T_basic :=
proc(n)
opción de recordar;
local gf, q, k, p, término;
si n=0 entonces devolver 0 fi;
si n=1 entonces devolver u fi;
gf := 1;
para q n-1 hacer
por k a q hacer
plazo :=
agregar((u^k*z^q)^m, m=0..piso((n-1)/q));
p := coef(T_basic(q), u, k);
gf := gf*término^p;
od;
od;
coeftayl(gf, z=0, n-1);
end;
T :=
proc(n)
opción de recordar;
local k, s, a;
si n=0 entonces devolver 0 fi;
si n=1 entonces devolver u fi;
A := n -> add(subs(u=u^l, T(n/l))/l,
l en divisores(n));
s := (1-u)*(n-1);
s := s + 1/(n-1)*
agregar((k+1)*(k+1)*T(n-1-k), k=0..n-2);
expanda(s);
end;
T_all := n -> subs(u=1, T(n));
T_even := n -> 1/2*(subs(u=1, T(n)) + subs(u=-1, T(n)));
T_odd := n -> 1/2*(subs(u=1, T(n)) - submarinos(u=-1, T(n)));
Este material está inspirado por Harary y Palmer,
Gráfico De La Enumeración.
Anexo Sáb Dic 27 2014. Podemos verificar los resultados anteriores con Maple combstruct paquete. Incluso calcular la ecuación funcional (univariante de la versión).
El siguiente Arce código hará el truco para valores de $n$ en la mayoría de los doce.
con(combstruct);
gf :=
proc(n)
opción de recordar;
local de árboles, hojas;
árboles := { T=Unión(Prod(Z, U), Prod(Z, Set(T, 1<= card))),
Z=Átomo, U=Epsilon };
hojas :=
proc(struct)
si el tipo(estructura, función), a continuación,
volver añadir(hojas(op(p, struct)), q=1..nops(struct));
fi;
si struct = Z entonces devuelve 0 fi;
return 1;
end;
agregar(u^hojas(t), t en allstructs([T, los árboles], size=n));
end;
Esto calculará de la siguiente generación de la función de los árboles en $11$ nodos:
$${u}^{10}+9\,{u}^{9}+52\,{u}^{8}+185\,{u}^{7}+416\,{u}^{6}+563\,{u}^{5}+
429\,{u}^{4}+161\,{u}^{3}+25\,{u}^{2}+u.$$
Esto coincide con el valor de la recurrencia.
El comando
seq(count([T, los árboles], size=n), n=1..15);
producirá la
los coeficientes de la univariante de generación de función para este problema de coincidencia de la
los valores que se muestran arriba.
