> Dado un árbol de clases con raíz A, con cantidad de nodos r, cual es la
> forma del nodo para maximizar N(A)? Y para minimizarlo?
Se minimiza con
A1
B1
...
R1
y el resultado es 1. Claramente, hay solo una manera de hacer un
fileout de la jerarquia de clases en la que cada clase tiene
exactamente 1 subclase, salvo la ultima que tiene cero.
Se maximiza con
A1
B1
B2
...
B(r-1)
y el resultado es (r-1)!. Este es el caso no-maximizable de ordenar
r-1 cosas. O sea, no hay mas maneras posibles.
Pero hay otras formas de arbol que llegan a (r-1)! maneras de hacer
file out? Me parece que no. Considerese el caso de que haya r-2
ramas colgando de A1. Entonces alguna de esas ramas tiene que tener
profundidad mayor que cero. Sea B1 esa rama. Eso quiere decir que
N(B1) = 1 (porque hay r-2 ramas, asi que abajo de B1 hay C1 y nada
mas). El resto de las ramas se pueden ordenar de (r-3)! maneras.
Entre esas maneras, hay que intercalar dos. Eso se reduce a conseguir
dos puntos de insercion, o sea el numero combinatorio
\comb{(r-3)!}{2}, o sea (r-3)(r-4)/2. Pero (r-3)!(r-3)(r-4)/2 <
(r-1)! porque (r-3)(r-4)/2 < (r-1)(r-2). No sera la super
demostracion, pero me parece suficiente para creer que no hay otra
manera de maximizar N(A1).
Andres.
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
http://www.clubSmalltalk.org
