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;

...