Teorema de Cailey

MATEMATICA DISCRETA: ´

TEOREMA DE CAILEY.

Patricia Ortega Jim´enez

20 de Febrero de 2013Antes de hacer los ejercicios propuestos, enuncio el TEOREMA DE

CAILEY, cuya demostraci´on es el objetivo de los ejercicios:

El n´umero de ´arboles distintos que se pueden formar con el conjunto de v´ertices f1; :::; ng es nn−2.

1. EJERCICIO 8.2.5: Denotemos por N(d1; d2; :::; dn) el n´umero de

´arboles distintos que se pueden formar con el conjunto de v´ertices f1; 2; :::; ng, donde gr (j) = dj + 1.

a) Obs´ervese que si Pn j=1 dj = n − 2 entonces N(d1; d2; :::; dn) =

0.

Voy a demostrarlo por el contrarrec´ıproco, esto es:

"Si N(d1; d2; :::; dn) 6= 0 entonces Pn j=1 dj = n − 2 "

Supongamos que N(d1; d2; :::; dn) 6= 0, es decir, al menos hay un ´arbol

donde gr (j) = dj + 1. Sea A el conjunto de las aristas, en un ´arbol,

jAj = n − 1 y Pn j=1 gr (j) = 2jAj, por lo tanto, Pn j=1 gr (j) = 2n − 2.

Luego:

nX j

=1

gr (j) =

nX j

=1

(dj + 1) =

nX j

=1

dj + n = 2n − 2

De donde:

nX j

=1

dj = 2n − 2 − n = n − 2

Como quer´ıamos demostrar.

b) Pru´ebese la siguiente f´ormula de recurrencia:

N(d1; d2; :::; dn−1; 0) = N(d1 − 1; d2; :::; dn−1) +N(d1; d2 − 1; ::::; dn−1)

+ ... +N(d1; d2; ::::; dn−1 − 1)

donde en la suma anterior el t´ermino i-´esimo no aparece si

di = 0.

N(d1; d2; :::; dn−1; 0) es el n´umero de ´arboles con gr (j) = dj + 1. Por

lo tanto, gr(n)=1, es decir, n es una hoja del ´arbol. Esta hoja es vecina

de uno y solo uno de los v´ertices de grado mayor de 1 (como es conexo,

a no ser que el ´arbol fuese L2, dos hojas no pueden ser vecinas). Esto

explica, aplicando la demostraci´on que ahora expondr´e, que en la

suma, el t´ermino i-´esimo no aparezca si di = 0.

1Como hemos dicho, el v´ertice n es vecino de uno y solo un v´ertice.

Luego, sean:

Vi = f´arboles donde n es vecino del v´ertice i, respetando que gr (j) = dj + 1g

Tendremos que

n−1

[ i

=1

Vi = f´arboles donde gr (j) = dj + 1g ;

conjunto cuyo cardinal es N(d1; d2; :::; dn−1; 0)

Adem´as, observamos que habr´a tantos ´arboles donde n sea vecino de

i como ´arboles con los v´ertices f1; 2; :::; n − 1g y donde el grado de i

sea uno menos (esto es, un ´arbol donde le hayamos quitado la hoja ya

etiquetada). Luego jVij = N (d1; d2; :::; di − 1; :::; dn−1). Y, aplicando

el principio de la suma (recordemos que fVi : i = 1:::n − 1g (sin considerar los v´ertices j donde dj = 0 ) era una partici´on del conjunto

de todos los ´arboles con las caracter´ısticas citadas ) tendremos que:

j f´arboles donde gr (j) = dj + 1g j = j

n−1

[ i

=1

Vij =

n−1

X i

=1

jVij;

esto es, y como quer´ıamos demostrar:

N (d1; d2; :::; dn−1; 0) = N (d1 − 1; d2; :::; dn−1)+N (d1; d2 − 1; ::::; dn−1) +

::: + N (d1; d2; ::::; dn−1 − 1)

c) Ded´uzcase que si Pn j=1 dj = n − 2 entonces

N(d1; d2; :::; dn) = d1;dn2−;:::;d 2 n

Supongamos que Pn j=1 dj = n−2. Por contarse el n´umero de ´arboles,

al menos dos de los v´ertices tienen grado 1, tomamos uno cualquiera,

esto es, tomamos un v´ertice j tal que dj = 0 que sabemos que existe.

Para la demostraci´on partir´e de que dn = 0 pero si no fuese as´ı,

habr´ıa, como hemos dicho, otro v´ertice que si lo cumpliese y como

habr´ıa el mismo n´umero de ´arboles donde intercambiamos de nombre

los v´ertices (una biyecci´on entre los ´arboles creados, donde a cada

v´ertice se le asocia ´el mismo a excepci´on del v´ertice j (de grado 1),

que se intercambia con n), el resultado ser´ıa el mismo.

Luego, vamos a probar que:

N(d1; d2; :::; dn−1; 0) = d1;d2n;:::;d −2 n−1

Para probar la igualdad, probaremos que siguen la misma regla de

recurrencia y que tienen los mismos valores iniciales:

2Primero veremos que tienen el mismo valor inicial, esto es, para

n=3 (puesto que se toma n-2 no tiene mucho sentido aplicar la

regla para n=1,2):

N(d1; d2; d3) Para que sea un ´arbol, las ´unicas posibilidades que

hay es que uno tenga grado 2 y los otros dos 1, esto es,

N(d1; d2; d3)=N(1,1,0)=1 o N(d1; d2; d3)=N(1,0,1)=1 o

N(d1; d2; d3)=N(0,1,1)=1.

Y 13;−1;20
= 1, luego, efectivamente:

N (d1; d2; d3) = d13; d−2; d 2 3

Ahora probemos que siguen la misma regla de recurrencia:

(N (d1; d2; :::; dn−1; 0) = N (d1 − 1; d2; :::; dn−1) + N (d1; d2 − 1; ::::; dn−1) +

::: + N (d1; d2; ::::; dn−1 − 1))

Por un lado, tenemos que

d1; d2n; :::; d − 2 n−1 = d1!(dn2!−:::d2)! n−1!

Por el otro lado de la igualdad, tendr´ıamos que:

(d1 (−n1)! − d12−!:::d 2)! n−1!+d1! (d2(n−−1)! 3)! :::dn−1!+::::+d1!d2!(::: n(−dn3)! −1 − 1)!

=

∗

n X j

=1

dj (n − 3)!

d1!d2!:::dn−1! = (n − 2) d1!(dn2!−:::d3)! n−1!

...