Esta respuesta explora las ideas por @vonbrand, con una forma de Lagrange
la inversión para extraer los coeficientes. Me gustaría escribir la especie ecuación
de forma ligeramente diferente, a saber, como
T=ZY+ZP≥1(T).
Esto se traduce en la ecuación funcional
T(z)=zy+z(expT(z)−1)=z(−1+y+expT(z)).
Estamos interesados en la extracción de los coeficientes según el siguiente
ecuación:
n![zn]T(z)=n!2πi∫|z|=ϵ1zn+1T(z)dz.
Poner w=T(z), de modo que
z=w−1+y+expw
y
dz=(1−1+y+expw−wexpw(−1+y+expw)2)ps.
Este mapa corrige el origen, por lo que podemos escribir
n!2πi∫|w|=ϵ(−1+y+expw)n+1wn+1×w ×(1−1+y+expw−wexpw(−1+y+expw)2)ps.
Tratamos a los dos parenthesised términos en turno.
El primero de ellos ofrece
(−1+y+expw)nwn=1wnn∑q=0n\elegirq(y−1)n−qexp(wq)
Esto produce el residuo
n∑q=0n\elegirq(y−1)n−qqn−1(n−1)!.
El segundo da
expw(−1+y+expw)n−1wn−1=1wn−1n−1∑q=0n−1\elegirq(y−1)n−1−pexp(w(q+1))
Esto produce el residuo
n−1∑q=0n−1\elegirq(y−1)n−1−p(p+1)n−2(n−2)!.
Veamos el caso de y=1 antes de proceder a extraer los coeficientes.
Esto debería dar el número total de árboles en n nodos.
Sólo el plazo para q=n contribuye desde el primer plazo, dando
n!×nn−1(n−1)!=nn.
A partir del segundo semestre de q=n−1
n!×nn−2(n−2)!=(n−1)×nn−1.
La diferencia de estos dos esnn−1, que es el valor correcto.
Volvemos el proceso de extracción de los coeficientes de este y
multiplicando por n! obtenemos el número de árboles con n nodos y
k deja que
n×n∑q=0n\elegirqn−p\elegirk(−1)n−p−kpn−1−n(n−1)×n−1∑q=0n−1\elegirqn−p−1\elegirk(−1)n−p−1−k(q+1)n−2.
Ahora con las siguientes definiciones de Arce
c1 := proc(n,k)
n*agregar(binomial(n,p)*binomial(n-p,k)*
(-1)^(n-p-k)*p^(n-1), q=0..n);
end;
c2 := proc(n,k)
n*(n-1)*agregar(binomial(n-1,q)*binomial(n-1-p,k)*
(-1)^(n-1-p-k)*(q+1)^(n-2), q=0..n);
end;
c := (n, k) -> c1(n,k)-c2(n,k);
obtenemos la siguiente secuencia para k=1 a partir de a n=2:
2,6,24,120,720,5040,40320,362880,3628800,…
lo cual es correcto y cuenta el número de arraigada de caminos con una hoja en
la parte de abajo.
Para k=2 a partir de a n=3 tenemos
3,36,360,3600,37800,423360,5080320,65318400,898128000,…
que nos señala OEIS A055303
donde nos encontramos con que tenemos el derecho de los valores.
A continuación, intente k=3 a partir de a n=4 para obtener
4,140,3000,54600,940800,16087680,279417600,4989600000,92207808000,…
que nos señala OEIS A055304, una vez más
a confirmar la exactitud de los de arriba de la derivación.
El caso de k=4 a partir de a n=5 rendimientos
5,450,18900,588000,15876000,400075200,9779616000,237105792000,5779453680000,…
que nos señala OEIS A055305. Esto también
está confirmado.
El último que vamos a comprobar es k=5 a partir de a n=6, lo que produce
6,1302,101136,5143824,210198240,7593173280,255415628160,8252203639680,261173083691520,…
que apunta a OEIS A055306, buena noticia
una vez más.
Adicional OEIS consulta muestra que, incluso, k=10 está en la lista
y hay una tabla maestra en OEIS A055302.
Adenda. La fórmula anterior para los árboles en n nodos y con k
hojas admite adicional de la simplificación. Ambos términos son circunvoluciones
de exponenciales funciones de generación A(z)B(z).
El primer término tiene
A(z)=∑m≥0m\elegirk(−1)m−kzmm.=∑m≥km\elegirk(−1)m−kzmm.=1k!∑m≥k(−1)m−k(m−k)!zm=zkk!exp(−z)
y
AB(z) = \sum_{m\ge 0} m^{n-1} \frac{z^m}{m.}
= \exp(z) \sum_{q=1}^{n-1} {n-1\llave q} z^p$$
como es fácilmente demostrado por inducción.
Esto le da la siguiente forma cerrada para el primer término:
n×n![zn]zkk!n−1∑q=1n−1\llaveqzq=n×n![zn−k]1k!n−1∑q=1n−1\llaveqzq=n×n!k!n−1\llaveden−k.
El segundo término está estrechamente relacionado con el primero, siendo evaluada en la
n−1 en lugar de n. La función de A(z) es el mismo y B(z) es
AB(z) = \sum_{m\ge 0} (m+1)^{n-2} \frac{z^m}{m.}
= \exp(z) \sum_{q=1}^{n-1} {n-1\llave q} z^{p-1}$$
como queda una vez más demostrado fácilmente por inducción.
Esto le da la siguiente forma cerrada para el segundo término:
n(n−1)×(n−1)![zn−1]zkk!n−1∑q=1n−1\llaveqzp−1=n(n−1)×(n−1)![zn−1−k]1k!n−1∑q=1n−1\llaveqzp−1=n(n−1)(n−1)!k!n−1\llaveden−k.
La conclusión es que el número de árboles en n nodos y con k
las hojas se está dada por
(n−(n−1))n!k!n−1\llaveden−k=n!k!n−1\llaveden−k.
Post scriptum. El más simple de evaluación de los dos B(z) está en
hecho no por inducción, sino que utiliza una Stirling básico número de identidad.
Supongamos que buscamos
∑m≥0mn−1zmm!.
Ahora recuerdo que
m^{n-1} = \sum_{q=0}^{n-1} {n-1\brace q} m^{\underline q}.
La sustitución de los rendimientos
\sum_{m\ge 0}
\left(\sum_{q=0}^{n-1} {n-1\llave q} m^{\underline q}\right)
\frac{z^m}{m.}
que es
\sum_{q=0}^{n-1} {n-1\llave q}
\sum_{m\ge 0} m^{\underline{q}} \frac{z^m}{m.}
= \sum_{q=0}^{n-1} {n-1\llave q}
\sum_{m\ge q} m^{\underline{q}} \frac{z^m}{m.}
\\= \sum_{q=0}^{n-1} {n-1\llave q}
\sum_{m\ge q} \frac{z^m}{(m-q)!}
= \sum_{q=0}^{n-1} {n-1\llave q} z^q \exp(z)
y tenemos el resultado.
