Clases

Fundamentos de Inform´atica II ILI-153 Horst H. von Brand 2º Semestre 2009 Resumen Este documento presenta el resumen de las clases de Fundamentos de Inform´ atica II, dictada durante el 2º semestre de 2008 y 2009. N´ otese que hay material adicional en estos apuntes, que no se vio en clase.

1.

Funciones Generatrices

En lo que sigue veremos c´ omo usar series de potencias (una herramienta del an´alisis, vale decir matem´ aticas de lo continuo) para resolver una variedad de problemas discretos. La idea de funciones generatrices permite resolver muchos problemas de forma simple y transparente. Incluso cuando no da soluciones puede iluminar, indicando relaciones entre problemas que a primera vista no son obvias. El aplicar herramientas anal´ıticas (especialmente la teor´ıa de funciones de variables complejas) permite deducir resultados que de otra forma ser´ıan muy dif´ıciles de obtener. M´ as que exponer la teor´ıa tras las t´ecnicas, mostraremos aplicaciones. Algunos de nuestros ejemplos llevan a resultados de inter´es independiente. ∞ Sea una secuencia han i0 = ha0 , a1 , a2 , . . . , an , . . .i. La funci´ on generatriz (ordinaria) de la secuencia es la serie de potencias: X A(x) = an xn 0≤n

El punto es que la serie representa en forma compacta y manejable la secuencia infinita. Como veremos, en muchos casos resulta bastante m´ as sencillo manipular la serie que trabajar directamente con la secuencia. Para ejemplo, volveremos al problema de la Competencia de Ensayos de la Universidad de Miskatonic, que llev´ o a la relaci´ on: b2r+1 = b2r−1 + r + 1

b1 = 1

Definamos la serie: X B(x) = b2r+1 xr r≥0

Si multiplicamos nuestra recurrencia por xr y sumamos sobre r ≥ 1 nos queda: X X X b2r+1 xr = b2r−1 xr + (r + 1)xr r≥1

r≥1

r≥1

Expresando lo anterior en t´erminos de B(x), reconocemos: X X b2r+1 xr = b2r+1 xr − b1 r≥1

X

r≥0

= B(x) − 1 X b2r−1 x = b2r+1 xr+1 r

r≥1

r≥0

=x

X

b2r+1 xr

r≥0

= xB(x) Por el otro lado, sabemos que para |x| < 1 vale la serie geom´etrica: X 1 xr = 1−x r≥0

Derivando la serie geom´etrica respecto de x t´ermino a t´ermino, lo que es v´alido dentro de su radio de convergencia, nos queda:   d 1 1 = dx 1 − x (1 − x)2 X = rxr−1 r≥1

X = (r + 1)xr r≥0

Tambi´en: X X (r + 1)xr = (r + 1)xr − 1 r≥1

r≥0

Uniendo las anteriores queda: B(x) − 1 = xB(x) +

1 −1 (1 − x)2

Despejando B(x): B(x) =

1 (1 − x)3

Conociendo la funci´ on B(x), de cierta forma sabemos los valores b2r+1 que nos interesan. Para algunas aplicaciones basta llegar hasta ac´ a, pero nos interesa obtener una f´ormula expl´ıcita (ojal´a simple) para los coeficientes, de forma de poder determinar el tama˜ no requerido de las tarjetas. Derivando la serie geom´etrica por segunda vez:   d2 1 2 = 2 dx 1−x (1 − x)3 X = r(r − 1)xr−2 r≥2

=

X

(r + 2)(r + 1)xr

r≥0

Con esto se sigue: B(x) =

1X (r + 2)(r + 1)xr 2 r≥0

2

y tenemos nuevamente la f´ ormula expl´ıcita: b2r+1 =

1 (r + 1)(r + 2) 2

La ventaja frente al desarrollo anterior es que no tuvimos que “adivinar” esta soluci´on y nos ahorramos la demostraci´ on por inducci´ on.

1.1.

Algunos Trucos: Secuencia desplazada a la izquierda: X hak , ak+1 , . . .i −→ an+k xn n≥0

A(x) − a0 − a1 x − a2 x2 − . . . − ak−1 xk−1 = xk Secuencia desplazada a la derecha (k ceros a la izquierda): h0, 0, . . . , 0, a0 , a1 , . . . , an , . . .i −→

X

an xk+n

n≥0 k

= x A(x) Derivada: h0 · a0 , 1 · a1 , 2 · a2 , . . . , i · an , . . .i −→

X

nan xn

n≥0

=x

d A(x) dx

Para simplificar, muchas veces usaremos la notaci´on D para derivada, con lo que lo anterior se escribir´ıa tambi´en: x

d A(x) = xDA(x) dx

Integral: 

 X an xn+1 an a0 a1 a2 0, , , , . . . , , . . . −→ 1 2 3 n+1 n+1 n≥0 Z x = A(x) dx 0

1.2.

Algunas series u ´ tiles

X n≥0

X n≥0

xn =

1 1−x

an xn =

1 1 − ax

3

X xn = ex n!

n≥0

X α n≥0

n

xn = (1 + x)α

Esto vale no s´ olo para valores reales de α, sino para α ∈ C siempre que |x| < 1, donde   α−k+1 α α α−1 α−2 · · ··· · = · 1 2 3 k k y (consistente con la convenci´ on que productos vac´ıos son 1) siempre es:   α =1 0 Si α es un entero positivo, la serie se reduce a un polinomio y la relaci´on es v´alida para todo x. Adem´as, en tal caso para 0 ≤ k ≤ n podemos escribir:   α α! = k!(α − k)! k N´ otese la simetr´ıa:     α α = k α−k Ejemplo (1 − x)1/2 = Primero:   1/2 =1 0

P

k≥0

1/2 k




· (−1)k xk

El an´ alisis que sigue considera k ≥ 1.   1 · ( 1 − 1) · · · · · ( 12 − k + 1) 1/2 = 2 2 k k! 1 1 · (1 − 2)(1 − 4) . . . (1 − 2k + 2) k≥1 = k · 2 k! (−1)k−1 = · (1 · 3 · · · · · (2k − 3)) k!2k (−1)k−1 1 · 2 · 3 · 4 · · · · · (2k − 3)(2k − 2) = · k!2k 2 · 4 · 6 · · · · · (2k − 2) k−1 (−1) (2k − 2)! = · k−1 2k k! 2 (k − 1)! k−1 (−1) (2k − 2)! = 2k−1 · 2 · k (k − 1)!(k − 1)!   2k − 2 (−1)k−1 · = 2k−1 2 ·k k−1 Uniendo los anteriores, la serie pedida es:   X 1 2k − 2 1/2 (1 − x) =1− · · xk 22k−1 · k k−1 k≥1

4


Ejemplo Calcular −1/2 k Mucha de la derivaci´ on es similar a la del caso anterior. Tenemos, para k > 0:   −1/2 (−1/2) · (−1/2 − 1) · . . . · (−1/2 − k + 1) = k k! 1 1 · 3 · . . . · (2k − 1) = (−1)k k · 2 k! 1 (2k)! = (−1)k k · 2 k!2kk! 1 2k = (−1)k 2k k 2 Esta f´ ormula con k = 0 da:   −1/2 =1 0 as´ı no se necesita hacer un caso especial para ´esto.
Ejemplo Calcular −n k , con n > 0 entero. Tenemos:   −n (−n) · (−n − 1) · . . . · (−n − k + 1) = k k! n · (n + 1) · . . . · (n + k − 1) = (−1)k k! (n + k − 1)! = (−1)k k!(n − 1)!   k n+k−1 = (−1) k   n + k−1 k = (−1) n−1 Tampoco requiere casos especiales. N´ otense los casos particulares:   −2 = (−1)k (k + 1) k   −3 (k + 1)(k + 2) = (−1)k k 2 En general, resulta: X n + k  1 = xk (1 − x)n+1 n k≥0

1.3.

Notaci´ on

Com´ unmente extraeremos el coeficiente de un t´ermino de una serie. Para esto, dada la serie: X f (x) = an xn n≥0

usaremos la notaci´ on: [xn ] f (x) = an

5

Considerando ´esto como “lo que multiplica lo indicado en la serie”, tenemos tambi´en: an α  [xn ] xk f (x) = xn−k f (x) [αxn ] f (x) =

[xn ] (αf (x) + βg(x)) = α [xn ] f (x) + β [xn ] g(x) En t´erminos de esta notaci´ on el teorema de Maclaurin queda expresado como: 1 dn f (x) [xn ]f (x) = n n! dx 0 Ejemplo Esta situaci´ on es lejos la m´ as com´ un: [xn ]

X 1 = [xn ] r k xk 1 − rx k≥0

=r

1.4.

n

N´ umeros de Fibonacci

Consideremos la secuencia h0, 1, 1, 2, 3, 5, . . .i, que se obtiene de la recurrencia v´alida para n ≥ 0: Fn+2 = Fn+1 + Fn

F0 = 0, F1 = 1

Definimos: f (x) =

X

Fn xn

n≥0

Se tiene que: Fn+2 = Fn+1 + Fn X n≥0

Fn+2 · xn = Fn+1 · xn + Fn · xn X X Fn+2 · xn = Fn+1 · xn + Fn · x n n≥0

n≥0

f (x) − F0 − F1 · x f (x) − F0 = + f (x) 2 x x f (x) − x f (x) = + f (x) x2 x f (x) − x = xf (x) + x2 f (x) x f (x) = 1 − x − x2 Se busca factorizar de la siguiente manera: 1 − x − x2 = (1 − r+ x)(1 − r− x) Para obtener esta factorizaci´ on se realiza el cambio de variable y = 1/x y se tiene que: y 2 − y − 1 = (y − r+ )(y − r− ) √ 1± 5 r± = 2 y se denotar´ a a r+ = ϕ. Podemos expresar: y 2 − y − 1 = (y − r+ )(y − r− ) = y 2 − (r+ + r− )y + r+ r− 6

Comparando coeficientes resulta r− = −1/ϕ = 1 − ϕ (ϕ es la secci´ on ´ aurea). Luego mediante el uso de fracciones parciales se tiene:   1 1 1 √ f (x) = · − 1 − r+ x 1 − r− x 5 De esto u ´ltimo se reconocen dos series geom´etricas. Continuando: X 1 X 1 n n n n √ r+ √ r− x − x 5 5 n≥0 n≥0 n X r+ − rn √ − xn = 5 n≥0

f (x) =

Esto da la sorprendente relaci´ on: ϕn − (1 − ϕ)n √ 5 √ √ n (1 + 5) − (1 − 5)n √ = 2n 5

Fn =

Ahora bien: ϕ = 1, 618 . . . 1 − ϕ = −0, 618 . . . ϕ √ = 0, 75 . . . 5 1−ϕ √ = −0, 27 . . . 5 N´ otese entonces que para todo n ≥ 0: (1 − ϕ)n √ < 0, 5 5 √ Por lo tanto, Fn = ϕn / 5, redondeado al entero m´as cercano. Receta Para resolver recurrencias se debe: 1. Plantear la recurrencia. 2. Recopilar valores iniciales. 3. Aclarar para qu´e valores de n vale la recurrencia. 4. Definir la funci´ on generatriz de inter´es 5. Multiplicar la recurrencia de (1) por xn y sumar sobre todos los valores (3) 6. Expresar (5) en t´erminos de la funci´ on generatriz. 7. Despejar. 8. Extraer los coeficientes.

7

1.5.

Recurrencias lineales de coeficientes constantes

Un caso particularmente importante es el de recurrencias de la forma: an un+k + an−1 un−1+k + . . . + a0 uk = f (n) donde los ai son constantes y f (n) es una funci´on cualquiera. Esto se llama una recurrencia lineal de coeficientes constantes (de orden n, si an 6= 0). Si f (n) = 0, se dice homog´enea. Se requieren n condiciones adicionales para fijar la soluci´ on, que generalmente toman la forma de condiciones iniciales dando los valores de u0 hasta un−1 . La recurrencia de Fibonacci que resolvimos antes es una recurrencia de segundo orden, lineal de coeficientes constantes, homog´enea. Tratar el caso general es bastante engorroso, mostraremos el procedimiento mediante un ejemplo. Consideremos la recurrencia: un+2 + 4un = 5n2

u0 = 1, u1 = 3

Aplicando nuestra estrategia general, definimos: X U (x) = un xn n≥0

Siguiendo la receta: X X X un+2 xn + 4 xn = 5 n2 xn n≥0

n≥0

n≥0

  1 U (x) − 3x − 1 2 + 4 U (x) = 5(xD) x2 1−x x(1 + x) =5 (1 − x)3 Despejando y expresando en fracciones parciales: 2x4 + 13x3 − 6x2 + 1 (1 − x)3 (1 + 4x2 ) 2 82x + 37 19 33 + = − + 2 3 2 24(1 + 4x ) (1 − x) 5(1 − x) 25(1 − x)

U (x) =

Luego basta “leer” los coeficientes en esto. Puntos interesantes los ponen los t´erminos: 1 = 1 − 4x2 + 16x4 − . . . 1 + 4x2 X = (−4)n x2n n≥0

x = x − 4x3 + 16x5 − . . . 1 + 4x2 X = (−4)n x2n+1 n≥0

X −3 1 = (−1)n xn (1 − x)3 n n≥0

X (n + 2)(n + 1) xn 2 n≥0 X −2 1 = (−1)n xn (1 − x)2 n n≥0 X = (n + 1)xn =

n≥0

8

Podemos entonces expresar la soluci´ on como: 37 (2n + 2)(2n + 1) 19 33 · (−4)2n + 2 · − · (2n + 1) + 24 2 5 25 37 8 12 = · (−16)n + 4n2 − n − 24 25 25 82 (2n + 3)(2n + 2) 19 33 u2n+1 = · (−4)2n+1 + 2 · − · (2n + 2) + 24 2 5 25 41 12 7 n 2 = · (−16) + 4n + n − 6 5 25 Esta separaci´ on en t´erminos pares e impares es inc´omoda. Usando n´ umeros complejos podemos factorizar m´ as: u2n =

1 + 4x2 = (1 − 2ix)(1 + 2ix)   1 1 1 1 = + 1 + 4x2 2 1 + 2ix 1 − 2ix   i x 1 1 = − 1 + 4x2 4 1 + 2ix 1 − 2ix y podemos entonces expresar: 82 i 37 1 (n + 2)(n + 1) 19 33 · ((−2i)n − (2i)n ) + · ((−2i)n + (2i)n ) + 2 · − · (n + 1) + 24 4 24 2 2 5 25   37 4 12 41i n n n n n 2 ((−i) − i ) + ((−i) + i ) · 2 + n − n − = 48 96 5 25

un =

Es bien poco probable que hubi´eramos adivinado esta soluci´on. . .

1.6.

Dividir y conquistar

Una de las estrategias m´ as fruct´ıferas para dise˜ nar algoritmos es la que se llama “dividir y conquistar”. La idea es resolver un problema “grande” por la v´ıa de dividirlo en varios problemas menores del mismo tipo, resolver ´estos (recursivamente) y luego combinar los resultados. Ejemplos t´ıpicos son el ordenamiento por intercalaci´ on y b´ usqueda binaria Si el tiempo de ejecuci´ on de un algoritmo de este tipo para una entrada de tama˜ no n lo denotamos por t(n), el problema se reduce a a problemas de tama˜ no n/b, y el costo de reducir el problema y luego combinar las soluciones es f (n), tendremos recurrencias de la forma: t(bn) = at(n) + f (bn)

t(1) = t1

El restringir el an´ alisis a potencias de b es v´ alido ya que nos interesa el comportamiento asint´otico de la soluci´ on a la recurrencia. Intuitivamente es claro que los algoritmos considerados se ejecutan en un tiempo intermedio para tama˜ nos intermedios, y en el peor caso podemos “rellenar” los datos hasta completar la potencia respectiva. Hacer ´esto no cambia nuestras conclusiones m´ as abajo. En el caso de ordenamiento por intercalaci´on, dividimos en dos partes iguales que se procesan recursivamente, y el proceso de dividir puede implementarse v´ıa tomar elementos alternativos y ubicarlos en grupos separados, lo que toma un tiempo proporcional al n´ umero de elementos a ordenar. As´ı tenemos que a = b = 2, f (n) = cn para alguna constante c. Para b´ usqueda binaria, se divide en dos partes iguales de las cuales se procesa recursivamente s´ olo una, y el proceso de divisi´ on es simplemente ubicar el elemento medio y comparar con ´el, lo que toma un tiempo constante. En este caso resulta a = 1, b = 2, f (n) = c para alguna constante. Estos ejemplos son bastante representativos, y el an´ alisis resulta simple si f (n) = cnd . Para b´ usqueda binaria tenemos d = 0, para ordenamiento por intercalaci´ on d = 1. Consideramos entonces la recurrencia, v´ alida para n una potencia de b: t(bn) = at(n) + cnd

t(1) = t1

Efectuamos el cambio de variables: n = bk

k = logb n

t(n) = T (k)

t(bn) = T (k + 1) 9

En estos t´erminos: T (k + 1) = aT (k) + c(bd )k

T (0) = t1

Esta recurrencia es v´ alida para k ≥ 0. Esto es f´acil de resolver. Definimos la funci´on generatriz: X g(x) = T (k)xk k≥0

y aplicamos nuestras t´ecnicas: X X X T (k + 1)xk = T (k)xk + c (bd )k xk k≥0

k≥0

k≥0

g(x) − t1 1 = g(x) + c x 1 − (bd )x t1 − ((bd )t1 − c)x g(x) = 1 − (bd + a)x + a(bd )x2 t1 − ((bd )t1 − c)x = (1 − (bd )x)(1 − ax) Veamos primero el caso en que hay ra´ıces repetidas (a = bd ), donde la expansi´on en fracciones parciales toma la forma siguiente, para constantes α y β: g(x) =

α β + 2 (1 − ax) 1 − ax

En consecuencia, con constantes α0 y β 0 tenemos: T (k) = α0 kak + β 0 ak
logb n
logb n t(n) = α0 blogb a logb n + β 0 blogb a
logb a
logb a = α0 blogb n logb n + β 0 blogb n = α0 nlogb a logb n + β 0 nlogb a Como el primer t´ermino domina asint´ oticamente al segundo, podemos decir que en este caso: t(n) = O(nlogb a log n) El otro caso es cuando a 6= bd , y la expansi´ on en fracciones parciales toma la forma siguiente con constantes α y β: g(x) =

β α + 1 − ax 1 − bd x

y resulta mediante una derivaci´ on similar a la anterior: T (k) = αak + β(bd )k t(n) = αnlogb a + βnd Dependiendo de los valores relativos de logb a y d, o lo que es lo mismo, a y bd , es el t´ermino que domina esta expresi´ on. Resumiendo:  log a  si a > bd O(n b ) log a t(n) = O(n b log n) si a = bd   O(nd ) si a < bd En nuestro caso, esto nos dice que el tiempo de ejecuci´on de b´ usqueda binaria es O(log n), y que el de ordenamiento por intercalaci´ on es O(n log n). 10

2.

Aplicaciones combinatorias

Las funciones generatrices tienen muchas aplicaciones en combinatoria, por las razones que quedar´an claras a trav´es de los siguientes ejemplos.

2.1.

Coeficientes binomiales

Hagamos como que nada sabemos. . . ¿Cu´ antos subconjuntos de k elementos podemos obtener de un conjunto de n elementos? Obviamente, exactamente qu´e conjunto de n elementos tomemos da lo mismo, podemos usar el conjunto {1, 2, . . . , n} sin p´erdida de generalidad. Ll´amese f (n, k) a dicha cantidad. Podemos descomponer los f (n, k) subconjuntos en dos grupos: 1. Aquellos conjuntos que no contienen a n: Corresponden simplemente a tomar k elementos de los restantes n − 1, o sea, de ´estos hay f (n − 1, k). 2. Aquellos conjuntos que contienen a n: Estamos tomando n, y k − 1 elementos m´as de entre los restantes n − 1, o sea de ´estos hay f (n − 1, k − 1). Como estas dos posibilidades son excluyentes, y corresponden a todas las formas de armar subconjuntos de k elementos: f (n, k) = f (n − 1, k) + f (n − 1, k − 1) Hay una u ´nica manera de obtener un subconjunto de cero elementos (subconjunto vac´ıo), o sea, f (n, 0) = 1. Siguiendo con nuestra receta, definimos: X Bn (x) = f (n, k)xk k≥0

Partiremos de k + 1 para poder sumar desde k = 0. f (n, k + 1) = f (n − 1, k + 1) + f (n − 1, k) X

f (n, k + 1)xk = f (n − 1, k + 1)xk + f (n − 1, k)xk X X f (n, k + 1)xk = f (n − 1, k + 1)xk + f (n − 1, k)xk

k≥0

k≥0

k≥0

Luego, en t´erminos de la funci´ on generatriz, y teniendo en cuenta que f (n, 0) = 1, se tiene: Bn−1 (x) − 1 Bn (x) − 1 = + Bn−1 (x) x x Bn (x) = Bn−1 (x)(1 + x) P Finalmente es claro que B0 (x) = k≥0 f (0, k)xk = 1, por lo que: Bn (x) = (1 + x)n Aplicando el teorema de Maclaurin a Bn (x): dk Bn (x) = n · (n − 1) · . . . · (n − k + 1)(1 + x)n−k x=0 k dx x=0 = n · (n − 1) · . . . · (n − k + 1) Hemos demostrado nuevamente la relaci´ on entre los coeficientes binomiales y el n´ umero de maneras de elegir k elementos de entre n: n(n − 1) . . . (n − k + 1) f (n, k) = k! n! = k!(n − k)!   n = k Esto da el famoso tri´ angulo de Pascal: 11

n = 0:

1

n = 1:

1

n = 2:

1

n = 3: 1

n = 5: n = 6:

2.2.

2

1

n = 4: 1 1

3 4

5 6

1 1 3 6

10 15

1 4

10 20

1 5

15

1 6

1

N´ umeros de Stirling de 2ª especie

Se desea partir el conjunto {1, 2, 3, 4} en 2 clases: {1} {1,2} {1,3} {1,4} {1,2,3} {1,2,4} {1,3,4}

{2,3,4} {3,4} {2,4} {2,4} {4} {3} {2}

 Hay 7 particiones de 4 elementos en 2 clases. Esto corresponde a n´ umeros de Stirling de segunda especie, nk es el n´ umero de formas de particionar un conjunto de n elementos en k particiones. Nuevamente, el conjunto de n elementos elegidos es irrelevante, usaremos {1, 2, . . . , n} por simplicidad. El ejemplo muestra que:   n =7 k  Para obtener nk , consideremos dos grupos de particiones: 1.  Aquellas a solo: Corresponden a tomar k − 1 particiones de los dem´as n − 1 elementos, o sea, hay en que n est´ n−1 de ´ e stas. k−1 2. Aquellas en que n est´ a con otros elementos:  Se construyen en base a k clases de los restantes n − 1 elementos v´ıa agregar n a cada clase, o sea hay k · n−1 de ´estas. k Nuevamente, estas dos opciones son excluyentes y exhaustivas, y:       n n−1 n−1 = +k k k−1 k Donde:   n = 0, n 6= 0 0   0 =1 0 Si adem´ as decretamos:     0 n < 0 n = 0 k<0  k  0 k>n la recurrencia siempre se cumple.

12

Tenemos varias opciones de funciones generatrices: X n  An (x) = xk k k≥0 X n Bk (y) = yn k n≥0 X n  C(x, y) = xk y n k n≥0 k≥0

 k De estas tres opciones, la primera involucra derivadas (por el t´ermino k n−1 x ), la tercera involucra trabajar con k dos variables (lo cual siempre es complicado, adem´as que involucra derivadas igual que el caso A). Por lo tanto la segunda opci´ on parece ser la m´ as f´ acil. Primeramente, tenemos por lo anterior: B0 (y) = 1   0 Bk (0) = k =0

si k > 0

Aplicando ahora nuestra receta para manejar recurrencias, bajo el entendido que k > 0, y recordando que la recurrencia como est´ a escrita es v´ alida para n ≥ 1:     X n X n−1 X n − 1 yn = yn + k yn k k−1 k n≥1 n≥1 n≥0     X n − 1 X 0 n − 1 n−1 Bk (y) − =y y + ky y n−1 k k−1 k n≥1 n≥1 X n  X n  Bk (y) = y y n + ky yn k−1 k n≥0

n≥0

= yBk−1 (y) + kyBk (y) Despejando: y Bk−1 (y) 1 − ky yk = · B0 (y) (1 − y) · (1 − 2y) · . . . · (1 − ky) yk = (1 − y) · (1 − 2y) · . . . · (1 − ky)

Bk (y) =

Descomponiendo en fracciones parciales: X 1 αi = (1 − y) · (1 − 2y) · . . . · (1 − ky) 1 − iy 1≤i≤k

Multiplicando todo por 1 − ry, y luego haciendo y → 1/r (este es un truco est´andar para obtener los coeficientes en expansiones en fracciones parciales): αr = 

1 1−

1 r




· 1−

2 r




· ... · 1 −

r−1 r


 · 1−

r+1 r




· ... · 1 −

rk−1 {(r − 1) · . . . · (r − r + 1)} · {(r − r − 1) · . . . · (r − k)} rk−1 = {(r − 1)!} · {(−1)k−r (k − r)!} (−1)k−r rk−1 = (r − 1)!(k − r)! =

13

k r




Con esto tenemos: X

Bk (y) =

1≤r≤k

X

[y n ] Bk (y) =

(−1)k−r rk−1 yk · (r − 1)!(k − r)! 1 − ry [y n ]

1≤r≤k

(−1)k−r rk−1 yk · (r − 1)!(k − r)! 1 − ry

  X (−1)k−r rk−1 n yk = [y n ] k (r − 1)!(k − r)! 1 − ry 1≤r≤k

X

=

1≤r≤k

X

=

1≤r≤k

=

(−1)k−r rk−1  n−k  1 · y (r − 1)!(k − r)! 1 − ry (−1)k−r rk−1 · rn−k (r − 1)!(k − r)!

X (−1)k−r rn r!(k − r)!

1≤r≤k

Esta es la f´ ormula expl´ıcita que busc´ abamos. Una tabla de los n´ umeros de Stirling de segunda especie en forma de tri´angulo comienza: n = 0:

1

n = 1:

0

n = 2:

0

n = 3:

0

n = 4:

0

n = 5:

0

n = 6:

2.3.

0

1 1

1 1

1

1 1 3 7

15 31

1 6

25 90

1 10

65

1 15

1

N´ umeros de Bell

El n´ umero de Bell b(n) es el n´ umero total de particiones posibles de un conjunto de n elementos. Claramente:   X n b(n) = k 0≤k≤n

Esta f´ ormula da b(0) = 1, los primeros valores son 1, 1, 2, 5, 15, 52, 203, . . .. Para n > 0 podemos omitir el primer t´ermino (esto simplifica lo que sigue).  Pero resulta que la suma monstruosa que da los n´ umeros de Stirling de segunda especie “sabe” que nk = 0 si k > n (por su derivaci´ on cumple la recurrencia de los n´ umeros de Stirling de segunda especie) as´ı que podemos escribir para todo M ≥ n (as´ı s´ olo trabajamos con sumas finitas por ahora, y no nos meteremos en problemas).   n−1 X X r   b(n) = (−1)k−r (r − 1)!(k − r)! 1≤k≤M

1≤r≤k

El siguiente paso es intercambiar las sumas. Si combinamos las condiciones de ambas sumas resulta 1 ≤ r ≤ k ≤ M , que podemos descomponer en r recorriendo el rango 1 ≤ r ≤ M mientras k recorre r ≤ k ≤ M . Obtenemos: b(n) =

X 1≤r≤M

=

X 1≤r≤M

rn−1 (r − 1)! n−1

r (r − 1)!

X r≤k≤M

(−1)k−r (k − r)!

X 0≤k≤M −r

(−1)k k!

14

La suma interna huele a e−1 . . . Si ahora hacemos M → ∞: b(n) =

1 X rn−1 e (r − 1)! r≥1

1 X rn = e r! r≥0

En esto multiplicamos por r en el numerador y denominador, y luego agregamos el t´ermino para r = 0, que se anula. Esta f´ ormula vale para n ≥ 1. Muy bonito, aunque bien poco u ´til para calcular b(n). Definamos la funci´ on generatriz exponencial: E(x) =

X b(n)xn n!

n≥0

M´ as adelante veremos otras situaciones en las cuales conviene introducir factores extra. Como la f´ ormula para b(n) es v´ alida para n ≥ 1: E(x) − b(0) =

X b(n) xn n!

n≥1

E(x) − 1 =

X xn 1 X r n n! e r!

n≥1

r≥0

1 X X (rx)n = e r!n! n≥1 r≥0

1 X erx − 1 = e r! r≥0   rx X X 1 e 1 =  − e r! r! r≥0 r≥0   1 ex e −e E(x) − 1 = e x E(x) = ee −1 Simplemente notable.

2.4.

Obtener funciones generatrices directamente

Supongamos que A(x) = an xn es la funci´ on generatriz ordinaria para las secuencias de {0, 1}. Esta la podemos expresar como: X A(x) = xlargo de s secuencia s

O sea, consideramos un x como marcando cada elemento de s. Mirando las cosas de esta forma, podemos expresar: A(x) = 1 + 2xA(x) Esto se interpreta como A(x) representando todas las secuencias, mientras 1 representa la secuencia de largo 0 (hay una sola), y 2xA(x) corresponde a que dada una secuencia cualquiera obtenemos dos nuevas de largo uno mayor agregando 0 y 1, respectivamente. Tenemos: 1 1 − 2x an = 2n

A(x) =

15

Esto ya lo sab´ıamos, pero esta derivaci´ on es muy sencilla. Sea ahora B(x) la funci´ on generatriz de secuencias de {0, 1} sin ceros adyacentes. Razonado en forma similar a antes, una secuencia de ´estas es una secuencia que termina en uno (en cuyo caso, lo que viene antes es una de las secuencias que nos interesa) o termina en cero (en este caso el pen´ ultimo s´ımbolo es un uno, y lo que viene antes de ese es una de las secuencias que nos interesa). O sea: B(x) = 1 + x + xB(x) + x2 B(x) 1+x = 1 − x − x2 Esta es casi la funci´ on generatriz de los n´ umeros de Fibonacci: f (x) =

x 1 − x − x2

Sabemos que F0 = 0: f (x) − F0 x f (x) − F0 n n [x ]B(x) = [x ]f (x) + [xn ] x = Fn + Fn+1 B(x) = f (x) +

= Fn+2 y resulta bn = Fn+2 . Podemos verificar directamente que: B(x) =

f (x) − F1 x − F0 x2

Sea ahora C(x, y) la funci´ on generatriz de secuencias de {0, 1} sin ceros adyacentes, donde x marca el largo de la secuencia e y marca los unos. O sea, si cn,k es el n´ umero de secuencias de largo n que tienen k unos, entonces: X C(x, y) = cn,k xn y k n≥0 0≤k≤n

De forma similar a antes, obtenemos: C(x, y) = 1 + x + xyC(x, y) + x2 yC(x, y) La justificaci´ on es que una de las secuencias que nos interesa o es vac´ıa (aporta 0 en largo y 0 en unos, lo que se traduce en x0 y 0 = 1), o es un cero (aporta x1 y 0 = x), o es una de las secuencias que nos interesa seguida por un uno (adem´ as de esa secuencia aporta 1 en largo y 1 en unos, o sea xyC(x, y)), o es una de las secuencias que nos interesa seguida por uno cero (adem´ as de la secuencia base aporta 2 en largo y 1 en unos, vale decir, x2 yC(x, y)). Despejando y expandiendo una serie geom´etrica: 1+x 1 − xy − x2 y 1+x = 1 − xy(1 + x) X = (1 + x) xk y k (1 + x)k

C(x, y) =

k≥0

=

X

k k

x y (1 + x)k+1

k≥0

16

De lo anterior:  X i i cn,k = xn y k x y (1 + x)i+1 i≥0

= [xn ] xi (1 + x)i+1   = xn−i (1 + x)i+1   k+1 = n−k Viendo esta curiosa f´ ormula, podemos interpretarla considerando que al haber k unos hay k + 1 posiciones en las cuales podemos ubicar los n − k ceros (antes del primer uno, entre los primeros dos unos, . . . , despu´es del u ´ltimo uno). Se buscan las formas de obtener un canasto de n frutas si: El n´ umero de manzanas tiene que ser par. El n´ umero de pl´ atanos debe ser un m´ ultiplo de 5. Hay a lo m´ as 4 naranjas. Hay a lo m´ as 1 pera. Por ejemplo tomemos un canasto de 6 frutas: En total hay 7 posibilidades. Tipo Manzanas Pl´ atanos Naranjas Peras

(1) 6 0 0 0

(2) 4 0 2 0

(3) 4 0 1 1

(4) 2 0 4 0

(5) 2 0 3 1

(6) 0 5 1 0

(7) 0 5 0 1

Para aplicar funciones generatrices, veamos primero la situaci´on en que tenemos s´olo manzanas y pl´ atanos. ∞ Consideremos que x marca el n´ umero total de frutas, y que hmk i0 es la secuencia de formas de obtener k manzanas ∞ ∞ mientras hpk i0 corresponde a los pl´ atanos; y hfk i0 la secuencia de las maneras de obtener k frutas. Para un total de 4 frutas es: f4 = m0 · p4 + m1 · p3 + m2 · p2 + m3 · p3 + m4 · p0 Esta es exactamente la forma en que calcular´ıamos el coeficiente de x4 en la serie:     X X  mk xk  ·  p k xk  k≥0

k≥0 ∞

∞

∞

Vale decir, la funci´ on generatriz ordinaria de hfk i0 es el producto de las funciones generatrices de hmk i0 y hpk i0 . Podemos extender ´esto a los dem´ as tipos de frutas, y las funciones generatrices correspondientes a nuestro problema son: Para manzanas se tiene: 1 + x2 + x4 + . . . =

1 1 − x2

Para pl´ atanos se tiene: 1 + x5 + x10 + . . . =

1 1 − x5

Para las naranjas: 1 + x + x2 + x3 + x4 =

1 − x5 1−x 17

Las peras aportan: 1+x Combinando las anteriores: 1 1 − x5 1 · · · (1 + x) 2 5 1−x 1−x 1−x 1 = (1 − x)2

n+1 Por lo tanto hay (−1)n −2 = n + 1 maneras diferentes de llenar el canasto con n frutas. n = 1 Esta forma de ver las cosas da una aproximaci´on adicional al teorema del binomio: Cada uno de los n elementos
queda representado por 1 + x, con lo que la funci´on generatriz de nk debe ser simplemente (1 + x)n . Si tenemos 10 libros de tapa negra y 7 de tapa roja, e interesa saber de cu´antas formas pueden elegirse 3 libros, esto ser´ a una de las siguientes posibilidades: g(x) =

N R Opciones 0 3 1 35 1 2 10 21 2 1 45 7 3 0 120 1 Gran total

Totales 1 · 35 = 35 10 · 21 = 210 45 · 7 = 315 120 · 1 = 120 680

N´ otese que si ni y ri son los n´ umeros de maneras de elegir libros negros y rojos, respectivamente, entonces: X ni r3−i 0≤i≤3

que es precisamente la forma en que se calcular´ıa el coeficiente de x3 en el producto de las funciones generatrices ∞ ∞ ordinarias de las secuencias hni i0 y hri i0 . Si ahora consideramos diferente el orden en que se ubican 6 de los libros, tendremos para el caso de elegir 4 libros negros y 2 rojos: Los libros negros se pueden elegir en 10 · 9 · 8 · 7 = 5 040 ´ordenes diferentes Los libros rojos se pueden elegir en 7 · 6 = 42 ´ordenes diferentes Una vez elegidos los libros (1er libro negro, 2o libro negro, . . . ; 1er libro rojo, 2o libro rojo, .
. . ), queda por decidir en qu´e posiciones de las 6 se ubican los 4 libros negros, cosa que se puede hacer de 64 = 15 formas. Al hacer esto los libros rojos se ubicar´ an en las posiciones restantes. En resumen, hay 15 · 5 040 · 42 = 3 175 200 opciones. En total, en este caso si Ni y Ri son los n´ umeros de maneras de elegir en orden i libros negros y rojos, respectivamente, las maneras de ordenar 6 libros son: X 6 Ni R6−i i 0≤i≤6

Esto corresponde precisamente a la forma de multiplicar las series generatrices exponenciales de las secuencias ∞ ∞ hNi i0 y hRi i0 . Ejemplo Supongamos la t´ıpica “mezcla c´ octel”: Man´ı, pasas y almendras. Nos interesa saber de cu´antas formas puedo tener un total de n de ´estas. Si tengo una almendra y un man´ı, la forma de representar las combinaciones posibles est´a dada por: (1 + x) · (1 + x) = 1 + 2x + x2 18

El primer factor 1 + x indica que hay 1 forma de tener 0 almendras en nuestra mezcla (1 · x0 ) y 1 forma de tener 1 almendra (1 · x1 ). De forma an´ aloga se tiene 1 + x para el man´ı. En el resultado, los coeficientes indican que hay 1 manera de tener nada, 2 maneras de tener 1 (1 almendra o 1 man´ı) y 1 manera de tener 2 (1 almendra y 1 man´ı). Ahora si hay “infinitos” componentes de cada tipo, y s´olo nos interesa la cantidad de cada uno de ellos, la ∞ secuencia es h1i0 (hay 1 manera de tener 0 man´ıs, 1 manera de tener 1 man´ı, 1 manera de tener 2 man´ıs, . . . ), y nos enfrentamos con la serie: 1 + x + x2 + x3 + . . . =

1 1−x

Por lo tanto, las maneras de obtener n items en total (pasas, man´ı y almendras) tiene la funci´on generatriz ordinaria: 1 (1 − x)3 X −2 = (−1)n xn n

g(x) =

n≥0

=

X (n + 1)(n + 2) xn 2

n≥0

lo que nos da la respuesta que hay [xn ]g(x) = (n + 1)(n + 2)/2 maneras de obtener n pasas, man´ı y almendras. Ejemplo Si ahora nos interesara no s´ olo la cantidad de cada tipo de ´ıtem, sino nos interesa el orden en que ∞ ingerimos los ingredientes, nuevamente la secuencia que describe cada uno de ellos es h1i0 (hay s´olo una forma de ordenar n man´ıs id´enticos), y las funciones generatrices exponenciales correspondientes son: X xn = ex n!

n≥0

Para los tres ingredientes tenemos entonces: G(x) = ex · ex · ex = e3x X xn = 3n n! n≥0

y la respuesta es 3n . Ejemplo Otra variante del mismo tema es cuando interesa el orden en que viene cada ingrediente (ya no son ∞ id´enticos, sino cada uno viene numerado). En tal caso, cada ingrediente queda representado por la secuencia hn!i0 (hay n! maneras de ordenar n man´ıs), con funci´on generatriz exponencial: X n!≥0

n!

xn 1 = n! 1−x

y la funci´ on generatriz exponencial para los ordenamientos respectivos es (1 − x)−3 . X n + 2  1 = xn (1 − x)3 2 n≥0 X  n + 2  xn = n! 2 n! n≥0

El n´ umero buscado es:   n+2 (n + 2)! n! = 2 2 19

Ejemplo Cambio de monedas ¿Cu´ antas formas hay de dar US$ 2? Analizando el aporte de los cambios de monedas se tiene: 1¢ 5¢ 10¢ 25¢ 50¢

1 1−x 1 1 + x5 + x10 + . . . = 1 − x5 1 1 + x10 + x20 + . . . = 1 − x10 1 1 + x25 + x50 + . . . = 1 − x25 1 1 + x50 + x100 + . . . = 1 − x50 1 + x + x2 + . . . =

La funci´ on generatriz del n´ umero de maneras de entregar n centavos es entonces 1 1 1 1 1 · · · · 5 10 25 1−x 1−x 1−x 1−x 1 − x50 Luego “bastar´ıa” calcular la serie hasta obtener el coeficiente de x200 para responder a la consulta. . .

2.5.

Cu´ ando usar funciones generatrices ordinarias o exponenciales

Resumiendo las observaciones anteriores, podemos decir lo siguiente: Supongamos que tenemos objetos de tipo A, de los cuales hay an de tama˜ no n, y objetos de tipo B, de los cuales hay bn de tama˜ no n. Si se crean los objetos de tipo C de tama˜ no m + n combinando un objeto A de tama˜ no m y uno B de tama˜ no n de todas las formas posibles, esto corresponde a cn objetos de tipo C, donde X cn = ak bn−k 0≤k≤n

Esto resulta de considerar todas las combinaciones posibles de tama˜ nos de los objetos A y B que conforman el C. Si definimos funciones generatrices ordinarias: X A(x) = an xn n≥0

B(x) =

X

bn x n

n≥0

C(x) =

X

cn x n

n≥0

resulta: C(x) = A(x) · B(x) Si ahora los objetos A de tama˜ no n tienen n partes numeradas {1, 2, . . . , n}, y similarmente los objetos de tipo B y D, adem´ as de combinar los objetos mismos tenemos que distribuir los m + n n´ umeros que corresponden al objeto D que es la combinaci´ on entre la parte A (le tocan m n´ umeros) y la parte B (queda con los n restantes). Esto puede deberse a posiciones que ocupan las partes del objeto A en el objeto D o pueden ser r´otulos asignados a
las partes. As´ı, con un objeto de tipo A de tama˜ no m y uno B de tama˜ no n hay m+n combinaciones que pueden m construirse, y sumando sobre todos los posibles tama˜ nos de los objetos A y B nos queda para el n´ umero de objetos D que pueden construirse: X n dn = ak bn−k k 0≤k≤n

20

Si definimos funciones generatrices exponenciales: b A(x) =

X

an

xn n!

bn

xn n!

dn

xn n!

n≥0

b B(x) =

X n≥0

b D(x) =

X n≥0

y resulta: b b b D(x) = A(x) · B(x) Estas relaciones son las que hacen que la herramienta de funciones generatrices sea de importancia fundamental en combinatoria.

3.

Series de potencias: Teor´ıa formal Sea la serie: X an xn n≥0

donde los elementos an pertenecen a un anillo R. Puede considerarse como una construcci´on puramente formal, sin preocuparse por convergencia. La u ´nica restricci´on que impone ´esto es que toda vez que se calcula un coeficiente deben efectuarse un n´ umero finito de operaciones (en un anillo arbitrario no son aplicables las ideas de l´ımite y convergencia, necesarias para darle sentido a un n´ umero infinito de operaciones). Tiene perfecto sentido en este ambito manipular la serie sobre R: ´ X n!xn n≥0

Esta serie converge u ´nicamente para x = 0, y anal´ıticamente nada se puede hacer con ella. Definimos la igualdad entre series formales: X X an xn = bn xn cuando an = bn para todo n ≥ 0 n≥0

n≥0

Definimos adem´ as las operaciones: X X X an xn + bn x n = (an + bn )xn n≥0

n≥0

n≥0



   X X  ak xk  ·  bi x i  = k≥0

i≥0

X

ak bi xi+k

i≥0 k≥0

X

=

ak bn−k xn

n≥0 0≤k≤n



 =

X

X 

n≥0

ak bn−k  xn

0≤k≤n

Es rutina verificar que las series formales de potencias sobre el anillo R con variable x forman un anillo, con P 0 = n≥0 0 · xn y 1 = 1 + 0 · x + 0 · x2 + . . . A este anillo lo llamaremos RJxK (recu´erdese que llamamos R[x] al anillo de polinomios en x sobre R). Si R es conmutativo, tambi´en lo es RJxK. Para evitar notaci´on engorrosa, 21

consideramos que R[x] es un subconjunto de RJxK de la forma natural. Podemos tambi´en considerar series en m´ as de una variable, si las variables son x e y anotaremos RJx, yK. Esto es, por ejemplo: X S(x, y) = am,n xm y n m≥0 n≥0

Es simple (aunque engorroso) demostrar que RJx, yK es isomorfo a RJxKJyK y a RJyKJxK, pero no nos detendremos en tales detalles. Salvo situaciones excepcionales, en lo que sigue consideraremos series con elementos tomados de alg´ un campo, normalmente C (o R).

3.1.

Unidades y rec´ıprocos

Sea F un campo. En el anillo de series formales F JxK hay unidades que no son simplemente constantes (como ocurre en el correspondiente anillo de polinomios formales). Por ejemplo, en CJxK: 1 = 1 + x + x2 + . . . 1−x (1 − x) · (1 + x + x2 + x3 + . . .) = 1 Si a0 = 0 la serie no puede tener rec´ıproco, ya que no hay forma de crear un t´ermino constante del producto en tal caso. Por otro lado, supongamos que a0 6= 0:     X X  an xn  ·  bn x n  = 1 n≥0

n≥0

 X

 X

ak bn−k  xn = 1

 n≥0

0≤k≤n

Para n = 0 tendr´ıamos que a0 b0 = 1, o sea, b0 = 1/a0 ; luego para n > 0: X X ak bn−k = an−k bk 0≤k≤n

0≤k≤n

=0 bn = −

1 a0

X

an−k bk

0≤k≤n−1

Con esto u ´ltimo se obtiene la secuencia de todos los bn , que es la secuencia de coeficientes del rec´ıproco de la seria A(x). N´ otese que las sumas indicadas son siempre finitas. Ejemplo Sabemos que en C: ex =

X xn n!

n≥0

Entonces, ¿cu´ al es el rec´ıproco, o sea, (ex )−1 ? Sea: X (ex )−1 = bn xn n≥0

22

Entonces: 1

b0 =

=

1 0!

1 0!

 b1 = − 

 X

a1−n bn  = −a1 b0 = −1 = −

0≤n≤0

1 1!



 1 1 1 −1 1 · + · = 2! 0! 1! 1! 2!   1 1 1 −1 1 1 1 b3 = − · + · + · =− 3! 0! 2! 1! 1! 2! 3! .. . 1 b99 = − 99! O sea, sospechamos: b2 = −

(−1)n n! lo cual faltar´ıa demostrar por inducci´ on. . . Claro que demostrar ´esto por inducci´ on es una soberana lata. Intentemos calcular el producto:       n X xn X X X x 1 1  ·   xn (−1)n  = (−1)k n! n! k! (n − k)! n≥0 n≥0 n≥0 0≤k≤n   n X X n! x  = (−1)k k!(n − k)! n! bn =

n≥0

0≤k≤n

Ahora bien, el t´ermino constante es: 1 1 · (−1)0 = 1 0! 0! y los dem´ as t´erminos son:   1 X n! 1 X k k n (−1) = (−1) n! k!(n − k)! n! k 0≤k≤n

0≤k≤n

1 = (1 − 1)n n! =0 y nuestra “sospecha” se confirma: e−x =

X

(−1)k

k≥0

3.2.

xk k!

Derivadas formales  d  dx

 X

an xn  =

n≥0

X

nan xn−1

n≥0

=

X

(n + 1)an+1 xn

n≥0

23

Esta es una definici´ on puramente formal, no intervienen l´ımites ni el significado de la serie como una funci´ on. Debe interpretarse (n+1)an como lo definimos para anillos, vale decir, sumar n+1 veces el valor an . Debe tenerse cuidado con situaciones en las cuales n = 0 en el anillo de base. Ahora supongamos que la serie f (x) cumple con:   X d  fn xn  = 0 dx n≥0

Entonces para todo n ≥ 0 tenemos (n + 1)fn+1 = 0, y como (n + 1) 6= 0 debe ser fn+1 = 0. O sea, f0 es arbitrario y f1 = f2 = . . . = 0. La serie es una constante. Supongamos ahora que:   X X d  gn xn  = gn xn dx n≥0 n≥0 X X gn xn (n + 1)gn+1 xn = n≥0

n≥0

gn = (n + 1)gn+1 gn gn+1 = (n + 1) Esto significa que gn = g0 /n!, o sea: X gn xn = g0 ex n≥0

3.3.

Manipulaci´ on de Series Formales ∞

Sea una secuencia han i0 = ha0 , a1 , a2 , . . . , an , . . .i. La funci´ on generatriz (ordinaria) de la secuencia es la serie de potencias: X A(x) = an xn 0≤n ∞ ops

Anotaremos han i0 ←→ A(x) en este caso (ops es por ordinary power series). La funci´ on generatriz exponencial de la secuencia es la serie: X xn E(x) = an n! 0≤n

∞ egf

Anotaremos han i0 ←→ E(x) en este caso (egf es por exponential generating function). 3.3.1.

Reglas OPS ops

∞

1. Si f ←→ han i0 , entonces: f (x) − a0 − a1 x − . . . − ak−1 xk−1 ops ∞ ←→ han+k i0 xk Consideremos: ops

∞

f ←→ han i0

d ops ∞ f (x) ←→ hnan i0 dx Esta u ´ltima operaci´ on la expresamos en t´erminos del operador xD (D por derivada). Adem´as:

∞ ops (xD)2 f ←→ n2 an 0
d d d2 2 N´ otese que x2 D2 corresponde a x2 dx 2 ; lo que es bien distinto de (xD) , o sea, x dx x dx . x

24

2. En general, si p es un polinomio, entonces: ops

∞

p(xD)f ←→ hp(n)an i0

Ejemplo Obtener la suma de los primeros N cuadrados: 1 − xN +1 1−x   1 − xN +1 (xD)2 1 + x + x2 + . . . + xN = (xD)2 1−x  2  1 − xN +1 0 + 12 x + 22 x2 + . . . + N 2 xN x=1 = l´ım (xD)2 x→1 1−x 1 + x + x2 + · · · + xN =

El resto es derivar, calcular l´ımites y ´ algebra: X

k2 =

1≤k≤N

N (N + 1)(2N + 1) 6

La maquinaria de funciones generatrices permite obtener en forma rutinaria resultados que de otra forma ser´ıan complicados de sospechar, y luego deber´ıan ser demostrados por inducci´on. ops

ops

∞

∞

3. Si f ←→ han i0 y g ←→ hbn i0 entonces: * +∞ X ops f · g ←→ ak bn−k 0≤k≤n

0 ops

∞

4. Sea k un entero positivo y f ←→ han i0 , entonces: * +∞ X k ops f ←→ (an1 · an2 · . . . · ank ) n1 +n2 +...+nk =n

0

5. Supongamos: ops

∞

f ←→ han i0 Entonces: f (x) ops ←→ 1−x

+∞

* X

ak

0≤k≤n

0 ∞

Ejemplo La funci´ on generatriz de hni0 se obtiene de:   X X X X  (n + 1 − 1)xn = 1 · 1 xn − xn n≥0

n≥0

 =

n≥0

0≤k≤n

  X

n≥0

xn  · 

 X

xn  −

n≥0

X n≥0

1 1 1 = · − 1−x 1−x 1−x x = (1 − x)2

25

xn

∞

O podemos considerarla
el corrimiento en una posici´on a la derecha de la secuencia hn + 1i0 (esta se explica mediante n + 1 = n+1 1 ), que da: 1 (1 − x)2

x·

∞

Otra alternativa es considerar hn · 1i0 , que tambi´en da: xD

1 x = 1−x (1 − x)2

Otro caso interesante es la funci´ on generatriz de los n´ umeros harm´onicos, definidos como: Hn =

X 1 k

1≤k≤n

Adem´ as definimos H0 = 0 (consistente con que sumas vac´ıas son cero). Entonces buscamos una expresi´on para: X H(x) = Hn xn n≥0

Esto se reduce a: 

 X 1   xn H(x) = k n≥1 1≤k≤n   X X 1   xn−1 =x k+1 n≥1 0≤k≤n−1   X X 1  xn  =x k+1 X

n≥0

0≤k≤n

Como tenemos una suma entre manos, intentamos: H(x) = x ·

1 X xk 1−x k+1 k≥0

1 1 = ln 1−x 1−x En ´esto usamos el hecho (v´ alido para |x| < 1): d 1 ln(1 − x) = − dx 1−x X =− xn n≥0

con lo que: ln(1 − x) = −

X xn n

n≥1

= −x

X xn n+1

n≥0

26

3.3.2.

Reglas EGF egf

∞

egf

∞

egf

∞

egf

∞

1. Si f ←→ han i0 entonces Dk f ←→ han+k i0

egf

∞

2. Si f ←→ han i0 , y p es un polinomio, entonces p(xD)f ←→ hp(n)an i0 egf

∞

3. Si f ←→ han i0 y g ←→ hbn i0 entonces: f (x) =

X an xn n!

n≥0

X bn xn n! n≥0   X ak bn−k X   xn f (x) · g(x) = k! (n − k)! n≥0 0≤k≤n   X n X xn  ak bn−k  = k n! g(x) =

n≥0

0≤k≤n

Vale decir, si h(x) = f (x) · g(x), entonces: * +∞ X n egf h(x) ←→ ak bn−k k 0≤k≤n

3.4.

0

El truco xD log

Los logaritmos ayudan a simplificar expresiones con exponenciales y potencias. Pero terminamos con el logaritmo de una suma si el argumento es una serie, que es algo bastante feo de contemplar. Eliminar el logaritmo se logra derivando: d ln(f ) f0 = dx f Esto es mucho m´ as decente. Multiplicamos por x para reponer la potencia “perdida” al derivar. Receta: 1. Aplicar xD ln 2. Multiplicar para eliminar fracciones 3. Igualar coeficientes Ejemplo N´ umeros de Bell: Sabemos que: B(x) =

X b(n)xn n!

n≥1

= ee

x

−1

27

Aplicando nuestra receta: xB 0 (x) = xex B(x) xB 0 (x) = xex B(x)     X b(n)xn X xn X nb(n) ·  xn = x  n! n! n! n≥0 n≥0 n≥0    X X n X xn xn  b(n) b(k) =x k (n − 1)! n! n≥1 n≥0 0≤k≤n   X X n − 1  xn  = b(k) (n − 1)! k xD ln(B(x)) =

n≥1

0≤k≤n−1

Igualando coeficientes se obtiene la recurrencia: X n − 1 b(n) = b(k) b(0) = 1 k 0≤k≤n−1

Esto es definitivamente m´ as u ´til para calcular los valores de b(n) que la ecuaci´on anterior. Ejemplo Serie para A(x)α , con α ∈ C: Sea: X A(x) = an xn n≥0

¿Cu´ al es la serie para A(x)α ? Definimos: X B(x) = Aα (x) = bn x n n≥0

Aplicando la receta se tiene: A0 (x) xB 0 (x) = αx B(x) A(x) 0 xB (x) · A(x) = αxA0 (x) · B(x)         X X X X  nbn xn  ·  an xn  = α  nan xn  ·  bn x n  n≥0

n≥0

 X

X 

n≥0

n≥0

 ibi an−i  xn =

0≤i≤n

 X

 X

 n≥0

n≥0

αiai bn−1  xn

0≤i≤n

De ac´ a se sigue, igualando coeficientes: X X ai (n − i)bn−i = αiai bn−i 0≤i≤n

0≤i≤n

28

Nuevamente, esto involucra s´ olo operaciones finitas. Finalmente: X [ai (n − i)bn−i − αiai bn−i ] = 0 0≤i≤n

X

(n − i − αi)ai bn−i = 0

0≤i≤n

 na0 bn = − 

 X

(n − i − αi)ai bn−i 

1≤i≤n

bn = −

1 X (n − i − αi)ai bn−i na0 1≤i≤n

Para comenzar la recurrencia, usamos: b0 = aα 0

3.5.

Fibonacci RECARGADO

Recordando que: Fn+2 = Fn+1 + Fn

F0 = 0, F1 = 1

Entonces con: X Fn xn F (x) = n! n≥0

Se tendr´ıa que: X Fn+2 xn X Fn+1 xn X Fn xn = + n! n! n!

n≥0

n≥0

n≥0

2

D F = DF + F donde F (0) = 0 y F 0 (0) = 1. N´ otese que esto u ´ltimo no es m´ as que una notaci´on c´omoda para F0 y F1 en t´erminos de la serie. Si adem´ as comparamos la ecuaci´ on diferencial con la recurrencia original, est´a claro que obtener una de la otra es inmediato. Tratemos de solucionar esta ecuaci´ on diferencial ordinaria de segundo orden, homog´enea y de coeficientes constantes por el m´etodo de la ecuaci´ on caracter´ıstica: r2 = r + 1 r2 − r − 1 = 0 r± =

√ 1± 5 2

con lo que tenemos: F (x) = αer+ x + βer− x de donde: F (0) = α + β = 0 F 0 (0) = αr+ + βr− = 1 La soluci´ on de estas ecuaciones es: 1 α= √ 5

1 β = −√ 5 29

y finalmente:  n x Fn = (αer+ x + βer− x ) n!  n  n x x xr+ +β =α e exr− n! n! n n = αr+ + βr− rn − rn = +√ − 5

Esta es la misma f´ ormula derivada antes, ya que r+ = ϕ y r− = 1 − ϕ. Si comparamos las derivaciones, antes ten´ıamos una ecuaci´ on m´ as simple (algebraica) para la funci´on generatriz, pero el obtener la expresi´on final fue m´ as engorroso (tuvimos que usar fracciones parciales). Ac´a la ecuaci´on para la funci´on generatriz es m´as compleja (ecuaci´ on diferencial), pero una vez resuelta ´esta, obtener la f´ormula final es muy simple.

3.6.

Derangements

Un punto fijo de una permutaci´ on ocurre cuando el elemento n´ umero k es k. Un derangement (¿“desordenamiento”?) es una permutaci´ on sin puntos fijos. Llamamos Dn al n´ umero de derangements de n elementos. Por ejemplo, D0 = 1 (hay una u ´nica manera de ordenar cero elementos, y en esa ning´ un elemento est´a en su posici´ on), D1 = 0 (un elemento puede ordenarse de una manera solamente, y ese siempre est´a en su posici´on), D2 = 1 (s´ olo 21), D3 = 2 (312 y 231). Ejemplo Consideremos una permutaci´ on de 7 elementos: Nº elemento Valor

1 2

2 6

3 3

4 4

5 1

6 5

7 7

Esta permutaci´ on tiene tres puntos fijos: El 3 est´a en la posici´on 3, el 4 en la posici´on 4 y el 7 en la posici´on 7. Luego hay D7−3 formas de ordenar los dem´ as sin introducir puntos fijos adicionales, y esos “3 puntos fijos” se pueden
elegir de 73 formas diferentes.
En general,
si hay k puntos fijos en una permutaci´on, ´estos pueden elegirse de nk maneras; por lo tanto hay exactamente nk · Dn−k permutaciones con k puntos fijos. Toda permutaci´on tiene puntos fijos (0, 1, . . . , n de ellos) y hay un total de n! permutaciones: X n n! = · Dn−k k 0≤k≤n

Esta recurrencia es v´ alida para n ≥ 0 si definimos D0 = 1 (hay una u ´nica permutaci´on de 0 elementos, que no tiene puntos fijos y por tanto es un derangement). En la recurrencia se observa que el lado derecho se parece al producto de funciones generatrices exponenciales (por el coeficiente binomial). Definimos: D(x) =

X n≥0

Dn

xn n!

30

Multiplicando la recurrencia por xn /n! y sumando sobre n ≥ 0:   X xn X n X xn  n! · Dn−k  = k n! n! n≥0 n≥0 0≤k≤n     X Dn xn X xk 1 ·  = 1−x n! n! n≥0

n≥0

x

= e D(x) e−x 1−x   X X 1  = (−1)k  xn k!

D(x) =

n≥0

0≤k≤n

En esto usamos la f´ ormula para el producto de funciones generatrices exponenciales, y luego el que multiplicar por (1 − x)−1 nos da la funci´ on generatriz de las sumas parciales. De lo u ´ltimo:  n x Dn = d(x) n! X (−1)k = n! k! 0≤k≤n

La suma es la de la serie para e−1 truncada, y esta u ´ltima converge muy r´apidamente, por lo que se podr´ıa decir que: Dn ≈

n! e

Algo as´ı como un 37 % de las permutaciones no tienen puntos fijos. Otra manera de resolver ´esto es partir derivando una recurrencia para los Dn . Considere un derangement σ de {1, 2, . . . , n + 1} tal que σ(j) = n + 1 para alg´ un 1 ≤ j ≤ n. Vemos dos casos: σ(n + 1) 6= j: Definimos un derangement σ 0 de {1, 2, . . . , n} mediante: ( σ(i), cuando i 6= j 0 σ (i) = σ(n + 1), cuando i = j Esto da una biyecci´ on entre estos derangements y los de {1, 2, . . . , n}. Por ejemplo, dada σ = 51432, tenemos σ(1) = 5 (o sea, j = 1 y σ(5) = 2 6= 1. Esto nos da σ 0 = 2143. Si tomamos esta u ´ltima permutaci´ on y j = 1, primero tenemos 21435, y debemos intercambiar el elemento en la posici´ on j = 1 con el u ´ltimo, y resulta σ = 51432. σ(n + 1) = j: En este caso definimos un derangement σ 0 de {1, 2, . . . , n − 1} mediante:  −1  σ(i), para 1 ≤ i ≤ n − 1, i 6= j, i 6= σ (n) 0 σ (i) = σ(n), para i = j   j, para i = σ −1 (n) Esto da una biyecci´ on entre estos derangements y los de {1, 2, . . . , n − 1}. Por ejemplo, para σ = 41523 con j = 3 es σ(3) = 5 y σ(5) = 3. Interesa tambi´en σ −1 (4) = 1. Obtenemos σ 0 = 312. Al rev´es, comenzando con σ 0 = 312 y j = 3, Ser´a σ(3) = 5, y σ(5) = 3. La ubicaci´on de j = 3 en σ −1 (4) hace que σ(1) = 4. Los dem´ as valores son iguales a los de σ 0 , y resulta σ = 41523.

31

Finalmente, podemos elegir j de n formas en ambos casos, y obtenemos: Dn+1 = n(Dn + Dn−1 ) Para completar los valores, definimos D0 = 1 de forma que D2 = 1 · (D1 + D0 ). Para resolver esta recurrencia, definimos la funci´on generatriz exponencial: b D(x) =

X D n xn n!

n≥0

De la recursi´ on tenemos para n ≥ 1: Dn+1 nDn Dn−1 = + n! n! (n − 1)! Entonces: X X xn X xn xn = nDn + Dn−1 Dn+1 n! n! (n − 1)! n≥1

n≥1

n≥1

N´ otese que: X Dn+1 d X xn−1 b 0 (x) xn = Dn+1 =D n! dx (n + 1)!

n≥1

n≥0

X nDn d X xn b 0 (x) xn−1 = Dn =D n! dx n! n≥1

n≥1

X n≥1

xn−1 b Dn−1 = D(x) (n − 1)!

y tenemos: b 0 (x) = xD b 0 (x) + xD(x) b D b 0 (x) D x = b 1−x D(x) Z x x b ln D(x) = dx 1 − x 0 1 = ln −x 1−x 1 −x b D(x) = e 1−x X (−1)k Dn = n! k! 0≤k≤n

Igual que antes.

3.7.

¿Cuantos strings de 2n par´ entesis balanceados hay?

Llamaremos Cn al n´ umero de strings de 2n par´entesis balanceados. Todo string de par´entesis balanceados se puede dividir en dos partes: El 2k-´esimo par´entesis cierra el primer par´entesis (1 ≤ k ≤ n), y el resto. Por ejemplo, marcando este comienzo con negrillas: (()())(()(()))()(()()()). Llamamos perfecto a un string con n = k. ¿Cuantos strings perfectos de largo 2n hay? Hay Cn−1 , como muestra la siguiente biyecci´ on: Tomar un string balanceado cualquiera de largo 2n − 2, y encerrarlo entre par´entesis da un string perfecto de largo 2n. 32

Tomar un string perfecto, y eliminar los “( )” de m´as afuera da un string balanceado Por lo anterior, un string balanceado de largo 2n se obtiene combinando: Un string perfecto de largo 2k, para 1 ≤ k ≤ n: Hay Ck−1 de ´estos. Un string balanceado de largo 2n − 2k: Hay Cn−k de ellos. Luego, como todo string se puede dividir de esta forma, y las “mitades” se pueden elegir en forma independiente: X Cn = Ck−1 · Cn−k 1≤k≤n

Sabemos que C1 = 1, y para hacer que la recurrencia valga tambi´en para n = 1, donde queda C1 = C0 · C0 , elegimos C0 = 1. La recurrencia entonces es v´ alida para n ≥ 1. La suma corresponde casi casi a una convoluci´on (el coeficiente en el producto de series de potencias). Definimos X C(x) = Cn xn n≥0

para luego aplicar nuestra receta:   X X X  Cn xn = Ck−1 Cn−k  xn n≥1

n≥1

1≤k≤n

 C(x) − 1 =



X

X

Ck Cn−1−k  xn

 n≥1

0≤k≤n−1

 =



X

X 

n≥0

Ck Cn−k  xn+1

0≤k≤n

 =x·

 X

X  n≥0

Ck Cn−k  xn

0≤k≤n

2

= xC(x) 2

xC − C + 1 = 0 Otra manera de obtener esta ecuaci´ on para C(x) es razonar directamente como sigue: Sea C(x) nuestra funci´ on generatriz. Para obtener una de las secuencias que nos interesa, hay dos posibilidades: La secuencia vac´ıa (aporta 1) o dos secuencias arbitrarias de las que consideramos cuyo tama˜ no suma n − 1 y un par de par´entesis extra. O sea: C(x) = 1 + xC 2 (x) Tenemos la condici´ on adicional que C0 = 1, que completa las condiciones. Tenemos dos posibles valores para resolver la ecuaci´on: √ 1 ± 1 − 4x C(x) = 2x Como ambas opciones son indeterminadas en x = 0, calculamos l´ımites, y debe ser C(0) = C0 = 1. Resulta c´ omodo expandir la ra´ız mediante el teorema del binomio: √ 1 + 1 − 4x l´ım =∞ x→0 2x √ 1 − (1 − 12 (4x) − . . .) 1 − 1 − 4x = l´ım =1 l´ım x→0 x→0 2x 2x 33

La opci´ on correcta es el signo menos: √ 1 − 1 − 4x C(x) = 2x y s´ olo queda obtener los coeficientes. A esta funci´on generatriz se le ha llamado la m´as famosa de la combinatoria. Analizando esta expresi´ on se observa que:  X 1/2 1/2 (1 − 4x) = · (−4x)n n n≥0 X (−1)n−1 2n − 2 =1+ · · (−4x)n 22n−1 · n n−1 n≥1  X 2n − 2  22n xn n−1 n · =1+ · · (−1) (−1) n−1 22n−1 n n≥1 X 2 2n − 2 =1− · xn n n−1 n≥1

Reemplazando este resultado en la funci´ on generatriz de los n´ umeros de Catalan se tiene: √   1 − 1 − 4x X 1 2n − 2 = · xn−1 2x n n−1 n≥1 X 1 2n · xn = n+1 n n≥0

con lo que: Cn =

  1 2n n+1 n

Esta secuencia (los n´ umeros de Catalan) aparecen con bastante frecuencia en problemas combinatorios. Ejemplo Strings de largo n de s´ımbolos tomados de {a, b, c, d} que tienen un n´ umero par de a. ¿Cu´antos hay? Sean: un : N´ umero de strings de largo n con un n´ umero impar de a. vn : N´ umero de strings de largo n con un n´ umero par de a. Entonces: un+1 = 3un + vn Esta u ´ltima recurrencia se explica de la siguiente manera: Sea por ejemplo el string de largo 8 de la forma “abaabcd?”, el u ´ltimo s´ımbolo a agregar determinar´ a la naturaleza del string. Existe una u ´nica forma de que este string quede con una cantidad par de a (agregando otra letra a) representada por vn , y tres formas de crear un string que tenga un n´ umero impar de a (agregando una de las tres letras {b, c, d}), representadas por 3un . Siguiendo la misma l´ ogica se obtiene otra recurrencia: vn+1 = un + 3vn Tenemos valores iniciales u0 = 0 y v0 = 1. Para solucionar estas recurrencias definimos: X U (x) = un xn n≥0

V (x) =

X

vn x n

n≥0

34

Aplicando la receta anti-recurrencias: U (x) = 3U (x) + V (x) x V (x) − 1 = U (x) + 3V (x) x Despejando, y recordando que realmente s´ olo nos interesa vn : 1 − 3x 1 − 6x + 8x2   1 1 1 = + 2 1 − 4x 1 − 2x 1 vn = (4n + 2n ) 2

V (x) =

3.8.

Particiones de enteros

Una de las ´ areas de investigaci´ on importantes en teor´ıa de n´ umeros en el siglo XX fue la teor´ıa de las particiones de enteros. Ac´ a veremos s´ olo un par de resultados curiosos, que se conocen hace mucho. 3.8.1.

Particiones en general

Sea p(n) el n´ umero de formas de escribir n como suma. Tenemos: p(1) = 1 1 p(2) = 2 1 + 1 = 2 p(3) = 3 1 + 1 + 1 = 2 + 1 = 3 p(4) = 4 1 + 1 + 1 + 1 = 2 + 1 + 1 = 2 + 2 = 3 + 1 = 4 .. . Si definimos la funci´ on generatriz: X P (x) = p(n)xn n≥0

A la suma 1 puede aportar 0, 1, 2, . . . , lo que queda expresado en la serie geom´etrica 1/(1 − x); de la misma forma 2 aporta 1/(1 − x2 ); . . . ; y en general n aporta 1/(1 − xn ). La serie entonces se puede expresar como: Y 1 P (x) = 1 − xn n≥0

3.8.2.

Sumandos diferentes e impares

Analizando ahora la serie anterior pero poniendo como condici´on que los sumandos no se pueden repetir el umero de ´estas particiones pd (n), por aporte de n es 0 ´ o n, lo que se refleja en un factor 1 + xn . Llamamos al n´ different, y distinguimos as´ı la funci´ on generatriz tambi´en: X Pd (x) = pd (n)xn n≥0

=

Y

(1 + xn )

n≥0

Este producto podemos expresarlo de otra forma: Y 1 − x2n Pd (x) = 1 − xn n≥0

=

Y n≥0

1 1 − x2n+1

35

Este producto corresponde a sumandos impares, y si escribimos po (n) por el n´ umero de particiones en sumandos impares (por odd ), tenemos: pd (n) = po (n) Curioso resultado, obtenido u ´nicamente considerando las funciones generatrices del caso. Y ni siquiera evaluamos ninguna de ellas.

4.

Principio de Inclusi´ on y Exclusi´ on

Hab´ıamos considerado antes la situaci´ on de contar los elementos contenidos en la uni´on entre dos conjuntos, concluyendo que |A ∪ B| = |A| + |B| − |A ∩ B| La situaci´ on se complica r´ apidamente cuando se consideran m´as conjuntos y sus intersecciones. En lo que sigue atacaremos el caso general mediante herramientas m´as sofisticadas. Tomamos un conjunto universo, y los conjuntos que consideramos se representan mediante propiedades (un elemento pertenece a uno de los conjuntos si tiene la propiedad que representa a ese conjunto). Las diversas intersecciones quedan expresadas a trav´es de los elementos que tienen todas las propiedades correspondientes a los conjuntos intersectados. Sean: Ω: El universo. Un conjunto de objetos. P : Un conjunto de propiedades que los objetos pueden tener S: Un subconjunto de las propiedades, S ⊆ P . N (⊇ S): N´ umero de objetos con las propiedades en S (esto no quiere decir que no puedan tener otras). Buscamos la forma de calcular cu´ antos objetos tienen exactamente t de las propiedades. Para r ≥ 0 fijo definimos: X Nr = N (⊇ S) |S|=r

Esto corresponde a la suma del tama˜ no de los conjuntos de objetos con al menos r de las propiedades, lo que perfectamente puede ser mayor que |Ω|. N´ otese que N0 = |Ω|, ya que considera todos los conjuntos con al menos cero propiedades, y eso es simplemente el universo mismo. Denote ω ∈ Ω un objeto cualquiera, y llamemos P (ω) al conjunto de propiedades de ω. Entonces: X Nr = N (⊇ S) |S|=r

=

X X |S|=r

=

=

ω∈Ω S ⊆ P (ω)

X ω∈Ω

 1

X

 1

S ⊆ P (ω) |S| = r

X |P (ω)| ω∈Ω

r

En espa˜ nol dice: Si el objeto tiene un total de |P (ω)| propiedades, puedo elegir r de sus propiedades de formas. Ahora sea et el n´ umero de objetos con exactamente t propiedades, es decir X et = 1 |P (ω)|=t

36

|P (ω)| r




Expresando Nr como una suma sobre el n´ umero de propiedades de los objetos, como cada uno de los et objetos con exactamente t propiedades aporta lo mismo: X |P (ω)| Nr = r ω∈Ω   X t = · et r t≥0

De lo anterior se busca, entonces, despejar los et . Para esta tarea definimos las funciones generatrices: X E(x) = et xt t≥0

N (x) =

X

Nr x r

r≥0

Siguiendo la receta vista antes:  X XX  t  Nr x r = · et xr r r≥0 r≥0 t≥0   XX t = · et xr r t≥0 r≥0 X  X t  = et xr r t≥0 r≥0 X = et (1 + x)t t≥0

O sea: N (x) = E(1 + x) E(x) = N (x − 1) De la expresi´ on anterior podemos extraer el et que se quiera:  t et = x E(x)   = xt N (x − 1)  X = xt Nr (x − 1)r r≥0

=

X

  Nr xt (x − 1)r

r≥0

  X r t−r = (−1) · Nr t r≥0

Esta f´ ormula expresa el celebrado principio de inclusi´on y exclusi´on. Adem´as de ser mucho m´as simple que la demostraci´ on tradicional, la ventaja de nuestro desarrollo es que no hace necesario recordar esta f´ormula, nos da las herramientas para deducirla sin mayor esfuerzo cada vez que debamos recurrir a ella. T´ıpicamente interesa saber cu´ antos objetos no tienen ninguna de las propiedades, o sea: e0 = E(0) = N (−1) N´ otese que si hay t propiedades en total, entonces et = Nt , ya que contempla todos los que tienen al menos t propiedades, y no hay propiedades adicionales.
Si s´ olo nos interesa calcular el n´ umero promedio de propiedades por objeto, como t = 1t resulta: X X t¯ = tet / et t≥0

=

t≥0

N1 N0 37

Receta 1. Definir Ω y P , expresar lo que se busca en t´erminos de et 2. Calcular los N (⊇ S) 3. Calcular los Nr , y en consecuencia obtener N (x). 4. et = [xt ] N (x − 1). Hay que tener cuidado con ´esto, ac´ a las series deben converger para que nuestras operaciones tengan sentido. Normalmente el n´ umero de propiedades y objetos de inter´es es finito, as´ı que en realidad estamos manipulando polinomios y no hay problemas. Ejemplo Puntos fijos de permutaciones. Este es un tema que ya hemos visto (derangements), pero ac´a obtendremos una visi´on adicional. Siguiendo nuestra receta: 1. Ω: Las n! permutaciones de n elementos. Una permutaci´on τ tiene la propiedad i si i es un punto fijo de la permutaci´ on. Nos interesa obtener e0 . 2. Sea S ⊆ {1, . . . , n}. Entonces N (⊇ S) corresponde a las permutaciones para las cuales los elementos de S son fijos, s´ olo se pueden “mover” los n − |S| restantes: N (⊇ S) = (n − |S|)! 3. Como r puntos fijos entre n pueden elegirse de Nr =

X

n r




maneras, se tiene que:

N (⊇ S)

|S|=r

=

X

(n − r)!

|S|=r

=

  n · (n − r)! r

Con esto: N (x) =

X n (n − r)!xr r

0≤r≤n

=

X 0≤r≤n

= n!

n! · (n − r)! · xr r!(n − r)!

X xr r!

0≤r≤n

Definamos la funci´ on exponencial truncada en n como: exp|n (x) =

X xr r!

0≤r≤n

Entonces: N (x) = n! · exp|n (x) 4. Finalmente buscamos et :   et = xt n! exp|n (x − 1)

38

En particular, e0 es el n´ umero de derangements de n, o sea Dn = e0 = E(0) = N (−1): Dn = n! exp|n (−1) ≈ n!e−1 Este resultado ya lo hab´ıamos obtenido. M´ as en general, tenemos tambi´en:   X (x − 1)r et = n! xt r! 0≤r≤n    t X X 1 r k = n! x x (−1)r−k r! k 0≤r≤n 0≤k≤r X 1 r  (−1)r−t = n! r! t 0≤r≤n

= n!

X (−1)r−t t!(r − t)!

t≤r≤n

=

n! t!

X 0≤r≤n−t

(−1)r r!

n! exp|n−t (−1) t! Esto coincide con lo que hab´ıamos usado como punto de partida al buscar una recurrencia para los Dn : =

n! exp|n−t (−1) t! n! = · (n − t)! exp|n−t (−1) t!(n − t!   n = · Dn−t t

et =

El n´ umero promedio de puntos fijos es: N1 t¯ = N0
n 1 (n − 1)! = n! =1 Curiosamente no depende de n. Ejemplo ¿Cu´ antos n´ umeros entre 1 y 100 no son divisibles por 2, 3 ´o 5? Aplicando la receta: 1. El universo Ω = {1, 2, . . . , 100}. Llamaremos P2 , P3 y P5 a la propiedad de ser divisible por el sub´ındice respectivo. Nos interesan los objetos que no tienen ninguna de las propiedades, o sea, e0 . 2. Los conjuntos del caso son un tanto enredados de manejar. . . Por ejemplo, si S = {2, 3}, estamos hablando de los n´ umeros divisibles por 2 ´ o 3. Es f´acil ver que la cantidad de n´ umeros entre 1 y 100 divisibles por a es simplemente b100/ac, y que los n´ umeros divisibles tanto por a como por b son divisibles por ab si a y b son relativamente primos (gcd(a, b) = 1), con lo que: N (⊇ {P2 }) = 50 N (⊇ {P3 }) = 33 N (⊇ {P5 }) = 20 N (⊇ {P2 , P3 }) = 16 N (⊇ {P2 , P5 }) = 10 N (⊇ {P3 , P5 }) = 6 N (⊇ {P2 , P3 , P5 }) = 3 39

3. Estamos en condiciones de calcular los Nr : N0 = |Ω| = 100 N1 = N (⊇ {P2 }) + N (⊇ {P3 }) + N (⊇ {P5 }) = 50 + 33 + 20 = 103 N2 = N (⊇ {P2 , P3 }) + N (⊇ {P2 , P5 }) + N (⊇ {P3 , P5 }) = 16 + 10 + 6 = 32 N3 = N (⊇ {P2 , P3 , P5 }) =3 Continuando con el desarrollo, la funci´ on generatriz de los Nr es simplemente: N (x) = 100 + 103x + 32x2 + 3x3 4. La funci´ on generatriz de los et es: E(x) = N (x − 1) Nos interesa el n´ umero de elementos con exactamente 0 de las propiedades: e0 = E(0) = N (−1) = 26 Incluso tenemos: E(x) = 26 + 48x + 23x2 + 3x3 O sea, hay 26 n´ umeros sin ninguna propiedad, 48 con una, 23 con dos y 3 con tres. Ejemplo Un grupo de estudiantes rinde pruebas con los profesores Ellery, Upham y Atwood. Sabemos que 12 pasaron la prueba de qu´ımica, 15 la de matem´aticas y 10 la de f´ısica; 8 pasaron qu´ımica y matem´aticas, 5 pasaron qu´ımica y f´ısica, 6 pasaron matem´ aticas y f´ısica. Sabemos que el total de estudiantes que pasaron al menos una prueba es 20. ¿Cu´ antos pasaron las tres pruebas? Aplicamos nuestra receta: 1. El universo es el grupo de 20 estudiantes que aprobaron alguna de las pruebas, las propiedades son las pruebas aprobadas (Q, F, M ). Nos interesan los que aprobaron todas las pruebas, o sea e3 . 2. Algunos de los N (⊇ S) est´ an dados en el enunciado del problema. Por ejemplo, dice que N (⊇ {Q, F }) = 5. 3. Para calcular los Nr tenemos: N0 = |Ω| = 20 N1 = N (⊇ {Q}) + N (⊇ {M }) + N (⊇ {F }) = 12 + 15 + 10 = 37 N2 = N (⊇ {Q, M }) + N (⊇ {Q, F }) + N (⊇ {M, F }) =8+5+6 = 19 N3 = N (⊇ {Q, M, F }) Entonces N3 = e3 . Sabemos tambi´en que e0 = 0 (entre los considerados no hay nadie que no haya aprobado al menos una prueba). La funci´ on generatriz de los Nr es simplemente: N (x) = 20 + 37x + 19x2 + e3 x3 40

4. Sabemos que: e0 = 0 = E(0) = N (−1) = 2 − e3 O sea, e3 = 2. Pero tambi´en tenemos: E(x) = N (x − 1) = 5x + 13x2 + 2x3 lo que nos dice que 5 aprobaron una u ´nica prueba y que 13 aprobaron dos. Ejemplo Determinar cu´ antos n´ umeros de largo n escritos en decimal tienen un n´ umero par de ceros. Ac´ a nuestro universo es el conjunto de todos los n´ umeros con n d´ıgitos. La propiedad i es que el d´ıgito i-´esimo es cero. Lo que nos interesa entonces es: X e2r e0 + e2 + . . . = r≥0

Podemos extraer u ´nicamente los t´erminos con potencia par mediante: E(x) + E(−x) 2 y nuestra suma es simplemente: E(1) + E(−1) 2 Un n´ umero decimal de n d´ıgitos comienza con un d´ıgito no cero, los dem´as n − 1 d´ıgitos pueden ser cualquiera. En este caso podemos calcular los er directamente, observando que hay r posiciones para los ceros, elegidas de entre n − 1 posiciones, los otros n − r d´ıgitos (incluyendo el primero) pueden tomar uno de los 9 valores restantes. O sea:   n−1 er = · 9n−r r X n − 1 · 9n−1−r · xr E(x) = 9 · r r≥0

= 9 · (9 + x)n−1 y el n´ umero buscado resulta ser:
1 1 (E(1) + E(−1)) = 9 · (9 + 1)n−1 + 9 · (9 − 1)n−1 2 2
9 = 10n−1 + 8n−1 2 El principio de inclusi´ on y exclusi´ on completa las herramientas elementales de la combinatoria vistas anteriormente.

5.

La f´ ormula de inversi´ on de Lagrange La f´ ormula de inversi´ on de Lagrange es una herramienta notable para resolver ecuaciones de la forma: u = tφ(u)

donde φ es una funci´ on dada de u. Esta relaci´on define u en funci´on de t, y “estamos despejando u en t´erminos de t”. La utilidad en combinatoria resulta porque al derivar la ecuaci´on para la funci´on generatriz G(x) t´ıpicamente tendremos un caso “vac´ıo” (aporta 1) y x veces alguna expresi´on que involucra a G, que representa “casos anteriores y ´este”. Con la substituci´ on u = G(x) − 1 la ecuaci´on queda de la forma indicada. Veremos un par de ejemplos m´ as adelante. 41

Teorema 5.1 (F´ ormula de Inversi´ on de Lagrange). Sean f (u) y φ(u) series formales de potencias en u, con φ(0) = 1. Entonces hay una u ´nica serie formal u = u(t) que cumple: u = tφ(u) Adem´ as, el valor f (u(t)) de f en la ra´ız u = u(t), expandida en serie alrededor de t = 0, cumple: 1  n−1  0 u {f (u)φ(u)n } n N´ otese que dadas las funciones f y φ, esta f´ormula nos da los coeficientes de f (u(t)) en bandeja. No demostraremos este resultado, ya que nos llevar´ıa demasiado fuera del rango de este ramo. [tn ] {f (u(t))} =

´ Ejemplo Arboles binarios. Un ´ arbol binario es vac´ıo, o es una ra´ız y un sub´arbol binario izquierdo y un sub´arbol binario derecho. Definimos bn como el n´ umero de ´ arboles binarios con n nodos, con funci´on generatriz ordinaria B(x). Directamente, ya que obtenemos los ´ arboles de tama˜ no n de combinar un nodo con dos sub´arboles cuyos tama˜ nos suman n − 1: B(x) = 1 + xB 2 (x) Sabemos que ´esto nos lleva a los n´ umeros de Catalan, o sea bn = Cn . Si definimos u(x) = B(x) − 1, queda: u(x) = x(u + 1)2 Es aplicable la f´ ormula con φ(u) = (u + 1)2 , y claramente φ(0) = 1. Tenemos entonces, como en nuestro caso f (u) = u: 1  n−1  0 u {f (u)φ(u)n } n 1  n−1  = u (u + 1)2n n  1 2n = n n−1   1 2n = n+1 n

[xn ] u(x) =

N´ otese que ´esto nos da u ´nicamente los coeficientes para n ≥ 1 (solo ´estos coeficientes de B y de u = B −1 coinciden). Por casualidad la f´ ormula final si cubre correctamente el caso b0 = 1. Casi indoloro. ´ Ejemplo Arboles ternarios. Son similares a los ´ arboles binarios, pero cada nodo tiene tres descendientes. O sea, un ´arbol ternario es vac´ıo, o un nodo ra´ız adem´ as de tres sub´ arboles ternarios (el izquierdo, el central y el derecho) Nos interesa determinar cu´ antos ´ arboles ternarios de n nodos hay. Llamemos tn a esta cantidad. Claramente t0 = 1. Aplicando nuestra receta anti-recurrencias, definimos: X T (x) = t n xn n≥0

De la definici´ on, un ´ arbol ternario de n ≥ 1 nodos consta de un nodo ra´ız y tres sub´arboles, cuyos tama˜ nos suman n − 1. Como los tres sub´ arboles pueden elegirse independientemente: T (x) = 1 + xT 3 (x) Usando la misma idea anterior, definimos u = T − 1, φ(u) = (u + 1)3 , f (u) = u, y la f´ormula nos da: 1  n−1  0 u {f (u)φ(u)n } n 1  n−1  = u (u + 1)3n n  1 3n = n n−1   1 3n = 2n + 1 n

[xn ] u(x) =

42

Seguir en este caso el camino que emprendimos originalmente cuando derivamos los n´ umeros de Catalan lleva a la c´ ubica x T 3 (x) − T (x) + 1 = 0, resolviendo ´esta da las tres soluciones: √

3i 1 − − 2 2

T1 =

√

3i 1 − 2 2

T2 =

q T3 = 

27 x−4 x

 31

!  q 27 x−4

√

1   √ − + 2x 6 3x

3i 2

x

!  q 27 x−4

 13

√ 3x

6

−

27 x−4 √x

3x

1 2

−

1 2x

 13

√

1   √ + − 2x 6 3x x

− 23 i − 12 √  31 27 x−4 1 x √ 3x − 2x 6 3x

 31

1  √ + − 2x 6 3x

1 √ 3x

6

27 x−4 √x

3x

−

1 2x

 13

Nos interesan soluciones reales, por lo que la rama correcta es T3 (x). Extraer los coeficientes deber´a quedar de ejercicio. ´ Ejemplo Arboles ordenados Un ´ arbol ordenado es vac´ıo, o consta de un nodo ra´ız u ´nicamente, o es un nodo ra´ız y uno o m´as sub´arboles no vac´ıos ubicados en un orden espec´ıfico. Sea an el n´ umero de ´ arboles ordenados de n nodos. Definimos la funci´on generatriz: X A(x) = an xn n≥0

Directamente de la definici´ on anterior, como A(x) − 1 representa ´arboles ordenados no vac´ıos:
A(x) = 1 + x + x (A(x) − 1) + (A(x) − 1)2 + . . .
= 1 + x 1 + (A(x) − 1) + (A(x) − 1)2 + . . . 1 =1+x 1 − (A(x) − 1) Si definimos u = A(x) − 1, resulta: u=x·

1 1−u

y la f´ ormula de inversi´ on nos da para n ≥ 1 (sabemos que a0 = 1): an = [xn ]u(x) 1 = [un−1 ](1 − u)−n n   1 −n n−1 = (−1) n n−1   1 2n − 2 = · n n−1 De nuevo bastante indoloro. El lector astuto reconoce inmediatamente que para n > 0 es an = Cn−1 , aparecen nuevamente los n´ umeros de Catalan.

43

6.

Grafos

En matem´ aticas, un grafo corresponde a una abstracci´on de la situaci´on en la cual hay objetos (v´ertices), algunos de los cuales est´ an conectados entre s´ı (mediante arcos). El inter´es es razonar s´olo con el hecho que existen o no conexiones entre los v´ertices. Ejemplos de aplicaciones de grafos son circuitos el´ectricos y representaciones de redes de transporte. Muchas estructuras de datos pueden representarse mediante grafos. Tambi´en sirven como notaci´ on gr´ afica de algunos modelos de computaci´ on. Formalmente: Definici´ on Un grafo G = (V, E) consta de: V: Conjunto finito de v´ertices E: Conjunto de arcos, pares de v´ertices pertenecientes a V . O sea, un arco {a, b} ∈ E consta de a, b ∈ V . Consideramos en esta definici´ on que un arco conecta un par de v´ertices diferentes (sin importar el orden), y no pueden haber varios arcos uniendo el mismo par de v´ertices. Dos v´ertices contenidos en un arco se llaman adyacentes. Si de un grafo G = (V, E) se eliminan arcos o v´ertices (con los arcos que los contienen) el resultado G0 = (V 0 , E 0 ) es un subgrafo. Para nuestros efectos no interesa el caso de conjuntos infinitos de v´ertices. Variantes de grafos son multigrafos, en los cuales se permiten varios arcos entre el mismo par de v´ertices, e incluso arcos que comienzan y terminan en el mismo v´ertice. Muchas de nuestras conclusiones se aplican a ellos tambi´en, pero no los trataremos expl´ıcitamente. Ejemplo Definici´ on de un grafo. G dado por: V = {a, b, c, d, z} E = {{a, b}, {a, d}, {b, z}, {c, d}, {d, z}} Gr´ aficamente est´ a dado por la figura 1. Notar que a conectado con b o b conectado con a, para el caso significa lo mismo, sin importar la ruta o la distancia del arco. S´olo el hecho que est´an conectados importa. Ejemplo Red del Metro Al usar el metro (u otro medio de transporte) interesan cu´ales son los destinos que se pueden alcanzar por qu´e l´ınea, no las distancias exactas. La figura 2 muestra el “mapa” del metro de Santiago.

6.1.

Representaci´ on de Grafos

El dibujo es u ´til para seres humanos, pero bastante in´ util para razonar con ´el o para el uso en computadoras. Veremos algunas opciones adicionales. 6.1.1.

Lista de Adyacencia

La lista de adyacencia es una tabla donde para cada v´ertice se listan los v´ertices adyacentes. Para el caso del primer grafo de ejemplo (figura 1) se tendr´ıa: Nodo a b c d z

Adyacentes b, z a, z d a, c, z b, d

44

a

z

b

c

d Figura 1: Un grafo 6.1.2.

Matriz de adyacencia

Representar un grafo mediante una matriz de adyacencia corresponde a definir una matriz con ´ındices los v´ertices, y los elementos son 1 ´ o 0 dependiendo de si los v´ertices del caso est´an conectados. El grafo de la figura 1 quedar´ıa representado por la siguiente tabla: a b c d z

a 0 1 0 1 0

b 1 0 0 0 1

c 0 0 0 1 0

d 1 0 1 0 1

z 0 0 0 1 0

Es claro que esta matriz es sim´etrica (vale decir, a[i, j] = a[j, i]), y los elementos en la diagonal son todos cero (porque no hay arcos {v, v}). 6.1.3.

Representaci´ on enlazada

Una opci´ on natural es representar los v´ertices por nodos con punteros que lo conectan a sus vecinos. Como el n´ umero de vecinos no necesariamente es el mismo (o siquiera razonablemente acotado) una opci´on es que cada nodo tenga una lista de punteros a los vecinos (termina siendo algo similar a las listas de adyacencia). 6.1.4.

Representaci´ on impl´ıcita

En muchas aplicaciones el grafo nunca existe como estructura de datos, se van generando los nodos vecinos conforme se requieren.

45

Figura 2: Mapa del metro de Santiago

6.2.

Isomorfismo entre grafos

Si G1 = (V1 , E1 ) y G2 = (V2 , E2 ) son grafos se dice que son isomorfos si existe una biyecci´on: α : V1 → V2 tal que: {u, v} ∈ E1 ⇐⇒ {α(u), α(v)} ∈ E2 Ejemplo Isomorfismo entre grafos La figura 3 muestra un par de grafos isomorfos, indicando las correspondencias entre v´ertices.

6.3.

Algunos grafos especiales Kn : Grafo completo de n v´ertices cada uno conectado con todos los dem´as. La figura 4 muestra un ejemplo de ´esto.

46

Figura 3: Ejemplo de isomorfismo entre grafos Cn : Ciclo de n v´ertices, donde el v´ertice i est´a conectado con los v´ertices i − 1 e i + 1 m´odulo n. Ver figura 5. Wn : Rueda (“wheel”) de n v´ertices, que consiste en un grafo Cn m´as un “centro” conectado a cada v´ertice. La rueda de 6 v´ertices m´ as un centro est´a representada en la figura 6 Qn : Cubo de orden n. Donde: V´ ertice: Strings de n s´ımbolos {0, 1}. Arcos: Conectan a todos los pares de v´ertices que difieren en 1 s´ımbolo. Ejemplo Lista de adyacencia de un cubo de n = 3. Nodo 000 001 010 011 100 101 110 111

6.4.

Adyacentes 001, 010, 100 000, 011, 101 011, 110, 000 111, 010, 001 110, 101, 000 100, 111, 001 111, 101, 010 110, 011, 101

Grado de un v´ ertice

Definici´ on Sea G = (V, E) un grafo. El grado de un v´ertice es el n´ umero de otros v´ertices conectados a ´el, o sea, para v ∈ V es δ(v) = |{e ∈ E : v ∈ e}|. Teorema 6.1. Sea G = (V, E) un grafo, entonces: X δ(v) = 2 · |E| v∈V

Demostraci´ on. Consideremos S ⊆ V × E tal que (v, e) ∈ S siempre que v ∈ e. Contando los elementos de S “por filas” y “por columnas” tenemos: Por filas: Cada v´ertice aparece una vez por cada arco en el cual participa, o sea: X δ(v) v∈V

47

K2

K3

K4

K5

Figura 4: Grafos Kn . Por columnas: Cada v´ertice aparece dos veces (una por cada extremo del arco): X 2 = 2 · |E| e∈E

Estas dos expresiones deben ser iguales, lo que corresponde precisamente a lo que se quer´ıa demostrar. Lema 6.2 (Handshaking). El n´ umero de v´ertices de grado impar en un grafo es par. Demostraci´ on. Sean Vo los v´ertices de grado impar y Ve los v´ertices de grado par del grafo. Entonces: X X δ(v) + δ(v) = 2 · |E| v∈Vo

v∈Ve

El lado derecho de esta ecuaci´ on es par. El segundo t´ermino del lado izquierdo es una suma de n´ umeros pares, por lo que es par. Entonces el primer t´ermino debe ser par, pero es la suma de n´ umeros impares. La u ´nica posibilidad es que haya un n´ umero par de ´estos, que es exactamente lo que se quer´ıa demostrar. Definici´ on Se le llama regular a un grafo en el cual δ(v) es el mismo para todos los v´ertices. Definici´ on G = (V, E) es un grafo. Entonces se define: Camino: Se llama camino a una secuencia de v´ertices hv1 , v2 , . . . , vn i tal que vi , vi+1 son adyacentes (walk en ingl´es). Camino simple: Es un camino en los que los vi son todos distintos (en ingl´es, path). 48

Figura 5: Ciclo de 8 v´ertices. Ciclo: Es un camino hv1 , v2 , . . . , vn , v1 i, en el cual no se repite m´as que el primer y u ´ltimo v´ertice. Se llama r-ciclo (ciclo de largo r) si tiene r arcos y r v´ertices. Algunos distinguen ciclos (pueden repetirse v´ertices fuera del inicial) y ciclos simples (lo que nosotros llamamos ciclos). Circuito: Un camino cerrado hv1 , v2 , . . . , vn , v1 i (pueden repetirse v´ertices). Definici´ on Sea G = (V, E) un grafo. Definimos la relaci´on ∼ entre v´ertices: x ∼ y si x e y est´an en un camino de G, o sea x = v1 , v2 , . . . , vk = y es un camino. Es f´ acil notar que ∼ es una relaci´ on de equivalencia: (Reflexiva) x ∼ x. Un camino de 0 arcos cumple con la definici´on. (Sim´ etrica) x ∼ y ⇒ y ∼ x: Esto es x = v1 , . . . , vk = y ⇒ y = vk , . . . , v1 = x, que claramente es cierto. (Transitiva) (x ∼ y) ∧ (y ∼ z) ⇒ x ∼ y. Esto es decir: x = v1 , . . . , vk = y = u1 , . . . , uk = z O sea, x y z est´ an en un camino simple, y x ∼ z. Definici´ on Sea G = (V, E) un grafo. Si V1 ∪ V2 · · · ∪ Vk son las clases de equivalencia de ∼, y E1 , E2 , . . . , Ek son los conjuntos de arcos tales que Ei contiene solo v´ertices de Vi , a los grafos Gi = (Vi , Ei ) se les llama componentes de G. Si G tiene un solo componente es llamado conexo. Ejemplo Grafo no conexo En el grafo de la figura 7 se distinguen nodos a los cuales no se puede acceder desde el resto de los v´ertices. Este grafo tiene 2 componentes. Un resultado simple es la relaci´ on entre el n´ umero de v´ertices y arcos en grafos conexos. Teorema 6.3. Todo grafo G = (V, E) tiene a lo menos |V | − |E| componentes conexos. Demostraci´ on. Usamos inducci´ on sobre el n´ umero de arcos. Base: En un grafo con 0 arcos, cada v´ertice es un componente conexo por s´ı mismo, y hay exactamente |V |−0 = |V | componentes conexos. 49

Figura 6: Wheel de 6 v´ertices m´as un centro. Inducci´ on: Suponemos que la hip´ otesis vale para todo grafo de n arcos, y demostramos que vale para todo grafo de n + 1 arcos, con n ≥ 0. Consid´erese un grafo G = (V, E) con n + 1 arcos. Eliminamos un arco arbitrario {a, b} del grafo, dejando el grafo G0 con n arcos. Por la hip´otesis, G0 tiene a lo menos |V | − n componentes conexos. Reponemos el arco eliminado, con lo que tenemos de vuelta el grafo original G. Si a y b pertenec´ıan al mismo componente conexo de G, G tiene el mismo n´ umero de componentes conexos de G0 , que es a lo menos |V | − n por hip´ otesis. Si a y b pertenecen a componentes distintos de G0 , G tiene un componente conexo menos que G0 , ya que el arco {a, b} une esos dos componentes de G0 en uno solo en G. Como G0 ten´ıa a lo menos |V | − n componentes conexos, G tiene entonces a lo menos uno menos que ´esto, vale decir |V | − n − 1 = |V | − (n + 1). Esto demuestra el paso de inducci´ on.

Algunos puntos se deben hacer notar de esta demostraci´on. Primeramente, usamos inducci´on sobre el n´ umero de arcos. Esto es com´ un en demostraciones en grafos, al igual que inducci´on sobre el n´ umero de v´ertices. S´ olo si ninguna de estas dos estrategias sirve vale la pena considerar otras opciones. Por otro lado, usamos la estrategia de eliminar un arco y reponerlo en nuestra demostraci´on. Esta es la forma m´ as sencilla de evitar errores l´ ogicos comunes, ya que nos asegura que el arco que queremos agregar es posible. Si se usa inducci´ on en grafos (ya sea sobre arcos o v´ertices), siempre conviene usar esta idea de encoger-expandir. Corolario 6.4. Todo grafo conexo de n v´ertices tiene a lo menos n − 1 arcos. Definici´ on Sea G = (V, E) un grafo. Entonces: Un camino simple que visita todos los v´ertices es un camino Hamiltoniano. Un ciclo que contiene todos los v´ertices del grafo es llamado ciclo Hamiltoniano. Un camino que pasa por todos los arcos es denominado camino de Euler. Un circuito que pasa por todos los arcos se llama circuito de Euler. Determinar si hay un ciclo Hamiltoniano es dif´ıcil. En cambio, un camino de Euler es sencillo de determinar: Si consideramos v´ertices cualquiera hay dos opciones: 1. Comienzo en un v´ertice, termino en otro. 2. Comienzo en un v´ertice, termino en el mismo.

50

Figura 7: Un grafo con dos componentes. Si inicio y fin son diferentes: Inicio: Salgo 1 vez, paso por ´el (entro y salgo) varias veces, lo que significa que δ(inicio) es impar. Fin: Llego 1 vez, paso por ´el (entro y salgo) varias veces, con lo que tambi´en δ(fin) es impar. Otros v´ertices: Paso por ´el (entro y salgo) varias veces, por lo que δ(otras) es par. Si inicio y fin son el mismo: Inicio (y fin): Salgo una vez, paso por ´el (entro y salgo) varias veces, llego una vez, y δ(inicio) es par. Otros v´ertices: Paso por ´el (entro y salgo) varias veces, con lo que δ(otras) es par. Estas dos son las u ´nicas posibilidades, y por tanto es condici´on necesaria para la existencia de un camino de Euler en un grafo conexo el que o todos los v´ertices sean de grado par (en tal caso podemos comenzar en cualquiera de ellos, terminamos en el mismo, es un ciclo de Euler ), o que hayan exactamente dos v´ertices de grado impar (comenzamos en uno de ellos, terminamos en el otro, es un camino de Euler ). M´as adelante demostraremos que estas condiciones son suficientes, y daremos un algoritmo para encontrar un camino (o ciclo) de Euler. Ejemplo Puentes de K¨ onigsberg Sup´ ongase que se desea dar un paseo por la ciudad de K¨onigsberg, pasando una u ´nica vez por cada uno de los siete puentes, situados seg´ un la figura 8. ¿Es posible realizar esta tarea? La respuesta es no. Representando los sectores unidos por los puentes en un grafo como en la misma figura 8, se aprecia claramente que hay un n´ umero impar de v´ertices de grado impar. Debido a esto no es posible que exista un camino de Euler que permita cumplir con la tarea requerida. (Si bien la representaci´on no es un grafo propiamente tal pues hay v´ertices que est´ an conectados por m´as de un arco, a´ un as´ı los principios son aplicables.) Teorema 6.5 (Euler). Sea G un grafo conexo. Entonces hay un camino de Euler si y s´ olo si hay exactamente dos v´ertices de grado impar (y todo camino de Euler comienza en uno de ellos y termina en el otro), y hay un ciclo de Euler si y s´ olo si todos los v´ertices son de grado par. Demostraci´ on. Demostramos implicancia en ambas direcciones. Que las condiciones son necesarias ya lo vimos antes, demostramos ahora que son suficientes por inducci´on fuerte sobre el n´ umero de arcos de G. Si G tiene un u ´nico arco, la conclusi´ on es trivial. Supongamos entonces que para todo grafo con a lo m´as n arcos se cumple el teorema, y demostraremos que vale tambi´en para n + 1.

51

(a) K¨ onigsberg en tiempos de Euler

(b) K¨ onigsberg y sus puentes

3

5 3

3 (c) Puentes de K¨ onigsberg como multigrafo

Figura 8: Puentes de K¨onigsberg. Consideremos primero el caso en que todos los v´ertices de G son de grado par. Elijamos un v´ertice x y un arco e = {x, y}. Si eliminamos el arco e, obtenemos un nuevo grafo G0 . Aseveramos que G0 es conexo. Supongamos que G0 no fuera conexo, entonces x e y pertenecen a componentes diferentes. Resulta que en G0 el v´ertice x es de grado impar, y es el u ´nico v´ertice de grado impar en su componente. Esto es absurdo, contradice al lema 6.2. Por tanto, G0 es conexo y tiene exactamente dos v´ertices de grado impar, x e y. Por inducci´on, como G tiene n arcos, hay un camino de Euler que comienza en x y termina en y; al reponer el arco {x, y} hay entonces un circuito de Euler (el camino anterior junto con este arco). Supongamos ahora que G tiene exactamente dos v´ertices de grado impar, llam´emosles x e y. Consideremos primero el caso en que x e y son adyacentes. Eliminando el arco {x, y} tenemos un grafo G0 con n arcos, y todos sus v´ertices son de grado par. Si G0 es conexo, tiene un circuito de Euler, y agregando el arco {x, y} a ´este tenemos un camino de Euler que comienza en x y termina en y. Si G0 no es conexo, tiene dos componentes, llam´emosles G1 y G2 . Pero tanto G1 como G2 tienen s´ olo v´ertices de grado par, y tienen menos de n arcos, con lo que cada uno de ellos tiene un circuito de Euler. Conectando estos dos circuitos entre s´ı mediante el arco {x, y} obtenemos un camino de Euler para G. Si no hay un arco que conecte a x e y, debe haber un arco {x, z} para alg´ un v´ertice z. Eliminando este arco, tenemos un grafo G0 con n arcos en el cual hay exactamente dos v´ertices de grado impar, z e y. Por inducci´ on, si G0 es conexo hay un camino de Euler que comienza en z y termina en y, reponiendo el arco {x, z} tenemos un camino de Euler que comienza en x y termina en y. Si G0 no fuera conexo, tendr´a componentes G1 (que contiene a x) y G2 . Entonces z estar´ a en G2 (en caso contrario, G0 ser´ıa conexo), e y estar´a en G2 tambi´en (de otra forma, ser´ıa el u ´nico v´ertice de grado impar en G1 ). O sea, G1 tiene s´olo v´ertices de grado par, y G2 tiene exactamente dos v´ertices de orden impar (y y z). Por inducci´on, hay un circuito de Euler en G1 y un camino de Euler en G2 que comienza en z y termina en y. Reponiendo el arco {x, z} tenemos un camino de Euler que comienza en x, recorre G1 para volver a x, luego pasa a G2 por {x, z} y sigue el camino de Euler en G2 para terminar en y.

52

Esta demostraci´ on no da muchas luces sobre c´omo hallar el camino (circuito) de Euler. Esto lo da el algoritmo de Fleury: Si hay v´ertices de grado impar, comience en uno de ellos, en caso contrario elija uno cualquiera. En cada paso, elija un arco desde el v´ertice actual y atravi´eselo, luego lo elimina del grafo. AL hacer ´esto, debe tener cuidado que el grafo resultante sea conexo (salvo que no tenga alternativa). Ejemplo El juego del dibujo en el papel. Se pide dibujar la figura 9 en un papel, de manera que el l´apiz no se

Figura 9: Dibuja una casita. levante en ning´ un momento del papel y no dibuje dos veces el mismo trazo. ¿Es posible realizar esto? La respuesta es si. Esto debido a que hay exactamente 2 v´ertices de grado impar. Debemos elegir uno de ellos como punto de partida, y terminaremos en el otro. Ejemplo Tres servicios y tres casas.

1

A

B

C

2 Figura 10: Dos casas conectadas a tres servicios. Suponga que se tienen 3 casas {1, 2, 3} y 3 servicios {A, B, C}. ¿Pueden conectarse los servicios a las casas sin que estos se lleguen a cruzar? Como se ve en la figura 10, es imposible ya que despu´es de ubicar 2 casas no existen zonas libres en las cuales colocar la tercera sin que las lineas de servicios se crucen. Ejemplo Un cubo de queso cortado en 3 × 3. Un rat´ on comienza en una de las esquinas, come ese cubito y sigue con uno de los vecinos (no en diagonal). ¿Puede comerse todo el queso terminando con el cubo del centro? La respuesta a esto es No. Esto se debe a que no se cumple ninguno de estos casos: Path que visite todos los v´ertices comenzando con una esquina y finalizando en el centro. Ciclo Hamiltoniano en el grafo si se conecta la esquina con el centro.

53

6.5.

´ Arboles

Definici´ on El grafo T = (V, E) en un ´ arbol si: Definici´ on T1: T es conexo. T2: No hay ciclos en T . Definici´ on En un ´ arbol T = (V, E) un v´ertice v ∈ V se llama hoja si tiene exactamente un vecino en T . En caso contrario es un v´ertice interno. Teorema 6.6. Si T = (V, E) es un ´ arbol entonces: T3: Para cualquier par de v´ertices hay un u ´nico camino simple entre ellos. T4: Al agregar un arco a T se forma un ciclo T5: Al eliminar un arco, quedan dos componentes que son ´ arboles. T6: Un ´ arbol con al menos dos v´ertices tiene al menos dos hojas. T7: |E| = |V | − 1. Demostraci´ on. Demostramos cada una de las aseveraciones por turno. T3: Supongamos que T = (V, E) es un ´ arbol y que hay dos v´ertices x, y con m´as de un camino que los conecta, digamos: x = v1 , v2 , . . . , vr = y x = u1 , u2 , . . . , us = y Ahora sea i el menor ´ındice tal que vi+1 6= ui+1 , y sea j el mayor ´ındice tal que vj = uk para alg´ un k. V´ease la figura 11. De aqu´ı se nota que v1 , vi+1 , . . . , vj−1 , vj , uk−1 , uk−2 , ui+1 , ui es un ciclo, pero siendo T un a ´rbol

vi+1

x=

vj−1

v1

vi

vj

vr

u1

ui

uk

us

=y

uk−1

u i+1

Figura 11: Esquema de v´ertices en el teorema 6.6 no tiene ciclos. Esta contradicci´ on completa la demostraci´on de esta parte. T4: Al agregar un arco {x, y} al ´ arbol, ´este junto con el camino entre x e y (que existe porque T es conexo) forman un ciclo. T5: Consideremos un arco {x, y} del ´ arbol. Si lo eliminamos del grafo, ya no hay caminos entre x e y (por T3 hay un u ´nico camino entre x e y, precisamente este arco). Luego el grafo resultante tiene dos componentes, cada uno conexo y sin ciclos. O sea, ambos son ´arboles. T6: Consideremos un camino de largo m´ aximo en T , que contiene v´ertices v1 , v2 , . . . , vm . Entonces m ≥ 2, dado que un ´ arbol con al menos dos v´ertices tiene que tener al menos un arco. No pueden haber arcos {v1 , vi } para i ≥ 2, ya que de otra forma tendr´ıamos un ciclo v1 , . . . , vi , v1 . Tampoco puede haber un arco {u, v1 }, ya que de haberlo tendr´ıamos un camino m´ as largo u, v1 , . . . , vm . O sea, v1 es una hoja. De forma similar, vm es una hoja, y hay al menos dos hojas.

54

T7: Usamos inducci´ on fuerte sobre el n´ umero de v´ertices. Con un ´arbol con un u ´nico v´ertice, la aseveraci´ on se cumple. Supongamos ahora que la aseveraci´on se cumple para todos los ´arboles con a lo m´as n v´ertices, y consideremos un ´ arbol con n + 1 v´ertices. Elijamos una hoja x, hay un u ´nico arco {x, y}. Al eliminar el v´ertice x de T y el arco {x, y} queda un ´ arbol de |V | − 1 v´ertices, que por inducci´on tiene |V | arcos. Al reponer el v´ertice y el arco, el n´ umero de arcos y de v´ertices aumenta en uno, y resulta |V | = |E| + 1.

6.6.

Colorear v´ ertices

Ejemplo Consideremos la situaci´ on en que deseamos programar seis charlas, cada una de una hora. Hay interesados en asistir a varias de ellas, en particular, hay interesados en las charlas 1 y 2, en las 1 y 4, en 1 y 6, en 2 y 6, en 3 y 5, en 4 y 5, en 5 y 6. Nos interesa programar las charlas en el m´ınimo n´ umero de horas. Podemos modelar esto mediante un grafo, conectando las charlas que tienen asistentes en com´ un. V´ease la figura 12. Por ejemplo, podemos asignar:

v1

v2

v3

v6

v4

v5

Figura 12: Grafo representando charlas Hora 1 Hora 2 Hora 3 Hora 4 v1 y v3 v2 y v4 v5 v6 En t´erminos matem´ aticos, hemos particionado los v´ertices del grafo en cuatro partes, de forma que no hayan v´ertices adyacentes en ninguna de ellas. Una forma gr´afica de representar esta situaci´on usa la funci´on: c : {v1 , v2 , v3 , v4 , v5 , v6 } → {1, 2, 3, 4} que a cada v´ertice (charla) le asigna una hora. Generalmente hablamos de colores de los v´ertices, no de horas asignadas, aunque claramente la naturaleza exacta de los objetos {1, 2, 3, 4} es irrelevante. Podemos hablar de colores azul, rojo, amarillo, verde, o de hora 1, hora 2, hora 3, hora 4. Lo u ´nico que importa es que v´ertices vecinos tienen colores diferentes. Definici´ on Un coloreo de v´ertices de un grafo G = (V, E) es una funci´on c : V → N tal que c(x) 6= c(y) siempre que {x, y} ∈ E. Definici´ on El n´ umero crom´ atico de un grafo G = (V, E), escrito χ(G), es el m´ınimo entero k tal que el grafo tiene un coloreo de k colores 55

Volviendo a nuestro ejemplo de la figura 12, corresponde a un coloreo con 4 colores. Pero probando un poco con 3 colores: Hora 1 Hora 2 Hora 3 v1 v2 y v6 v3, v4 y v5 Por lo dem´ as, se requieren al menos 3 colores ya que v1, v2 y v6 est´an conectados entre s´ı. En general, para demostrar que el n´ umero crom´atico de un grafo es k se requiere: 1. Encontrar un coloreo con k colores 2. Demostrar que es imposible hacerlo con menos de k colores

6.7.

El algoritmo voraz para colorear grafos

Encontrar el n´ umero crom´ atico de un grafo es un problema dif´ıcil. No se conoce ning´ un algoritmo que tome tiempo polinomial, y se cree generalmente que tal algoritmo no existe. Sin embargo, hay una forma simple de construir un coloreo de v´ertices usando un n´ umero “razonable” de colores. La idea es ir asignando colores a los v´ertices de forma de usar siempre el primer color que no produce conflictos. El algoritmo 1 es corto de vista, por Algoritmo 1 Coloreo voraz Asigne el color 1 a v1 for i = 2 to n do Sea S el conjunto vac´ıo de colores for j = 1 to i − 1 do if vj es adyacente a vi then Agregue el color de vj a S end if end for k=1 while el color k est´ a en S do k =k+1 end while Asigne el color k a vj end for lo que generalmente no identifica necesariamente un buen coloreo. Sin embargo, puede producir el coloreo con el m´ınimo n´ umero de colores, dependiendo del orden en que se consideren los v´ertices. Lo malo es que si hay n v´ertices, son n! ´ ordenes diferentes a considerar. A pesar de ´esto, el algoritmo es u ´til en teor´ıa y en la pr´actica. Demostraremos un par de teoremas usando esta estrategia. Teorema 6.7. Si G es un grafo de grado m´ aximo k, entonces: 1. χ(G) ≤ k + 1 2. Si G es conexo y no es regular, entonces χ(G) ≤ k Demostraci´ on. Demostramos cada aseveraci´ on por turno. 1. Sea v1 , v2 , . . . , vn un orden de los v´ertices de G. Si aplicamos el algoritmo de coloreo voraz, al considerar un v´ertice cualquiera tendr´ a a lo m´ as k vecinos con colores ya asignados. Si contamos con k + 1 colores, siempre habr´ a uno que podamos asignarle. 2. Para este caso consideraremos los v´ertices en un orden especial. Como el grafo no es regular, habr´a al menos un v´ertice cuyo grado es menor a k. Llam´emosle vn a uno de ellos. Numeremos los vecinos de vn como vn−1 , vn−2 , . . . (hay a lo m´ as k − 1 de ´estos). Una vez agotados los vecinos de vn , numeramos los vecinos de vn−1 distintos de vn ; nuevamente habr´ a a lo m´as k − 1 de ´estos. Continuando de esta forma, siempre dejando fuera de consideraci´ on los que ya tienen n´ umero asignado. Si ahora aplicamos el algoritmo voraz, siempre que considere un v´ertice tendr´ a a lo m´ as k − 1 vecinos ya coloreados, y se requerir´an a lo m´as k colores.

56

Otra consecuencia u ´til de lo anterior se obtiene en grafos para los cuales χ(G) = 2. En este caso, los v´ertices se dividen en dos grupos V1 y V2 que corresponden a los coloreados con los colores 1 y 2, respectivamente, y los arcos unen uno de cada grupo. En consecuencia, estos grafos se llaman bipartitos. Para ellos tenemos: Teorema 6.8. Un grafo es bipartito si y s´ olo si no tiene ciclos de largo impar. Demostraci´ on. Demostramos implicancias en ambas direcciones. Si hay un ciclo de largo impar, se requieren tres colores s´olo para colorear ese ciclo, y χ(G) ≥ 3. Por el otro lado, si no hay ciclos de largo impar, construiremos un ordenamiento de los v´ertices que produce un coloreo con dos colores. Elijamos un v´ertice cualquiera, llam´emosle v1 , y le asignamos el nivel 0. A los vecinos de v1 les llamamos v2 , . . . , vr , les asignamos el nivel 1. A los vecinos de los v´ertices de nivel 1 que no est´an ya numerados les asignamos el nivel 2, . . . , a los vecinos no numerados de los v´ertices de nivel l − 1 les asignamos el nivel l. De esta forma completamos un componente de G, y procesamos a los dem´as componentes de la misma forma. Lo crucial de este orden es que un nodo del nivel l s´ olo tiene vecinos en los niveles l − 1 y l + 1. Para ver esto, supongamos que hay dos v´ertices conectados en el mismo nivel. Siguiendo sus conexiones hacia atr´as a trav´es de los distintos niveles, encontraremos paths hacia un v´ertice com´ un, que tendr´an el mismo largo. Pero ´estos forman un ciclo de largo impar junto con el arco entre los v´ertices del mismo nivel que supusimos conectados. Ejemplo An´ alisis de grados. ¿Es posible tener grafos con v´ertices de grados como los de esta lista? 1. 2 2 2 3 2. 1 2 2 2 3 4 3. 2 2 4 4 4 4. 1 2 3 4 Respuesta: P P 1. Sabemos que v∈V δ(v) = 2 · |E|, ac´ a v∈V δ(v) = 9. Por lo tanto es imposible. Recordar que el n´ umero de v´ertices de grado impar siempre es par. 2. Es f´ acil ver que es factible dibujar este grafo.

1

2

2 4

3

3. Hay 5 v´ertices, de los cuales 3 est´ an conectados con “todos los dem´as” δ(v) = 4. Ninguno de los otros v´ertices pueden tener grado menor a 3. Por lo tanto es imposible este grafo. 4. Tenemos 4 v´ertices y uno conectado a 4 v´ertices, es decir, est´a conectado al resto y a 1 m´as. Nos falta 1 v´ertice. Este grafo es imposible. Ejercicio Se pide dibujar los ´ arboles no isomorfos de 6 v´ertices. La mejor forma de solucionar esto es empezar a dibujar los grafos, partiendo por el caso en que se encuentre un v´ertice de grado m´ aximo, es decir, de grado 5. 57

δ(v) = 5 (caso u ´nico).

δ(v) = 4

δ(v) = 3

δ(v) = 2

Que son la soluci´ on a nuestro problema. Hay un total de 6 ´arboles no isomorfos de 6 v´ertices. Ejercicio N´ umeros crom´ aticos Analicemos cu´ antos colores se necesitan para colorear el siguiente grafo:

Dado que el grafo presenta ciclos de largo impar, inmediatamente se desprende la necesidad de 3 colores o m´ as para colorear el grafo.

58

3

2

4 1

2

3

Figura 13: Ejemplo de grafo para n´ umeros crom´aticos Ejercicio N´ umeros crom´ aticos: Otro caso. Supongamos el grafo de la figura 13. En verde se marcan algunos ciclos impares, lo que nos indica que necesitan a lo menos 3 colores. Tambi´en dado que son 6 v´ertices, el n´ umero de colores es a lo m´as 6. Junto con los ciclos impares representados se nota claramente un grafo K4 , lo que indica que el n´ umero de colores tiene que ser a lo menos 4. En resumen, se necesitan como m´ınimo 4 colores para colorear este grafo.

6.8.

´ Arboles con ra´ız.

Veremos algunas aplicaciones de ´ arbol con un v´ertice especial designado como ra´ız. As´ı no son iguales (isomorfos) los siguientes ´ arboles con ra´ız (el cuadro indica la ra´ız):

Inmediatamente aparte de la ra´ız distinguimos v´ertices internos con δ(v) ≥ 2, y hojas con δ(v) = 1 En muchas aplicaciones nos encontraremos que los v´ertices internos tienen el mismo grado. Si los v´ertices internos tienen grado m se habla de ´ arboles m-arios. Aclaramos que los v´ertices binarios vistos en el ramo Estructuras de Datos, no son ´ arboles. Ac´a no hay hijos ni descendientes, y a´ un menos “hijos izquierdos” y “derechos”, s´olo vecinos. Podemos enumerar los v´ertices de un ´ arbol con ra´ız, analizando su distancia con la ra´ız: Nivel 0: La ra´ız. Nivel 1: Los vecinos de la ra´ız. Nivel 1: Los vecinos de nodos en el nivel 1, salvo los que est´an en el nivel 0. · · ·: · · ·. Nivel n: Los vecinos de los nodos en el nivel n − 1, salvo los que est´an en nivel n − 2. Definici´ on La altura del ´ arbol con ra´ız es el m´aximo k para el que el nivel k no es vac´ıo. Teorema 6.9. Si el grado m´ aximo de los v´ertices de un ´ arbol con ra´ız es d y su altura es h entonces el ´ arbol tiene a lo m´ as dh hojas. Demostraci´ on. La demostraci´ on es por inducci´on sobre h. Cuando h = 0 hay un u ´nico v´ertice (ra´ız = hoja) y hay 1 ≤ d0 = 1 hojas. Supongamos que todos los ´ arboles de altura menor o igual a h tienen a lo m´as dh hojas. Consideremos un ´ arbol de altura h + 1. Este es la ra´ız y a lo m´ as d ´ arboles de altura a lo m´as h, cada uno de los cuales aporta a lo m´ as dh h h+1 hojas, para un total de a lo m´ as d · d = d hojas. Corolario 6.10. Un ´ arbol con δ(v) ≤ d que tiene l hojas tiene altura a lo m´ as de logd l. 59

´ Arbol de decisi´ on

6.8.1.

Un ´ arbol de decisi´ on representa una secuencia de decisiones y los resultados de ´estas. Se comienza en la ra´ız, cada v´ertice interno representa una decisi´ on, y las hojas son resultados finales. Ejemplo B´ usqueda de monedas falsas. Tenemos una moneda O (la sabemos buena) y r otras monedas, una de las cuales puede ser falsa (o sea, puede que sea m´ as pesada o m´ as liviana que la moneda O). ¿Cual es el n´ umero m´ınimo de pesadas (comparar el peso de dos colecciones de monedas) para determinar si hay una falsa y saber exactamente cu´ al es? El ´ arbol de decisiones podr´ıa representarse as´ı: <=>

<=>

<=>

<=>

Si analizamos las hojas tenemos: Todos OK. #1 Pesada. #1 Liviana. ··· #r Pesada. #r Liviana. Tenemos 2r + 1 resultados. Por lo tanto se requieren a lo menos log3 (2r + 1) pesadas.

6.9.

An´ alisis de Algoritmos de Ordenamiento

Supongamos un m´etodo de ordenamiento basado en comparaciones. ¿Cu´antas comparaciones requiere ordenar n elementos? El suponer que todos los elementos son diferentes hace m´as duro resolver el problema, con lo que nos concentramos en ese caso. El ordenar n elementos involucra determinar en qu´e orden est´an (o, lo que es lo mismo, han de ubicarse). Un ´ arbol en el que los nodos internos son comparaciones se llama ´ arbol de decisi´ on. En nuestro caso, cada nodo representa comparar dos elementos con las opciones <, >. Las hojas son ´ordenes de los n elementos de entrada (aunque tambi´en es posible que aparezcan entre las hojas situaciones imposibles). No descartamos comparaciones redundantes en ´esto. Ejemplo De n elementos hay n! permutaciones. Comparemos tres elementos {a, b, c}, todos distintos. Como se ve en la figura 14, el ´arbol tiene 6 hojas, que corresponden a las 3! formas de ordenar 3 objetos. Esto nos muestra que la altura del ´ arbol de decisi´on (el n´ umero de comparaciones requeridas en el peor caso) es log2 n!. Interesa acotar ´esto. Es simple obtener: X log2 n! = log2 k 1≤k≤n

≤

X

log2 n

1≤k≤n

= n log2 n

60

a:b <

>

b:c

b:c

<

h=3

>

a,b,c

< a:c

< a,c,b

>

a:c >

< c,a,b b,a,c

b,c,a > c,b,a

´ Figura 14: Arbol de decisi´on Ahora demostraremos que n log2 n no es tan mala aproximaci´on. Consideremos: i(n − i + 1) ≥ n si 1 ≤ i ≤ n Para demostrar esto, buscamos el valor m´ınimo de esta expresi´on en este rango. f (x) = x(n − x + 1) f 0 (x) = n − 2x + 1 f 00 (x) = −2 Como f 00 (x) = −2 el punto cr´ıtico es un m´ aximo. Por simetr´ıa se concluye que los m´ınimos est´an en los extremos: f (1) = f (n) = n En vista de lo anteriormente demostrado: Y i(n − i + 1) ≥ nn 1≤i≤n

(n!)2 ≥ nn n! ≥ nn/2 En resumen: nn/2 ≤ n! ≤ nn La aproximaci´ on ln n! = n ln n no es tan mala. Otra forma de ver la aproximaci´ on la da la figura 15. Las ´areas bajo las curvas nos permiten concluir la siguiente relaci´ on: Z n+1 Z n+1 ln(x − 1) dx ≤ ln n! ≤ ln x dx 2

1

Integrando por partes resulta: Z ln x dx = x ln x − x As´ı tenemos: Z n+1 Z ln(x − 1) dx = 2

n

ln x dx

1

= n ln n − n + 1 Z

n+1

ln x dx = (n + 1) ln(n + 1) − (n + 1) + 1 1

61

2.5 log(floor(x)) log(x) log(x - 1)

2

1.5

1

0.5

0 1

2

3

4

5

6

7

8

9

10

Figura 15: Logaritmo natural de n! lo que nos da las cotas:  n+1  n n n+1 e ≤ n! ≤ e e e Un an´ alisis m´ as preciso usando la f´ ormula de Euler-Maclaurin para aproximar la diferencia entre la sumatoria y la integral lleva a la f´ ormula de Stirling:  n n √ n! ≈ 2πn e De todas formas, esto demuestra que para ordenar n elementos se requieren a lo menos log2 n! comparaciones, y por nuestro an´ alisis esto es O(n log n).

6.10.

Algoritmos de b´ usqueda

6.10.1.

DFS, Depth First Search

Sea G = (V, E) un grafo conexo. Apliquemos el siguiente algoritmo: Elegir un v´ertice v ∈ V como punto de partida. Marcar v como “visitado”, y considerar (recursivamente) los vecinos de v. La recursi´on termina al llegar a un v´ertice ya visitado. Esta t´ecnica es llamada en “profundidad” porque avanza todo lo que puede antes de considerar las dem´as alternativas. Ejemplo DFS El grafo de la figura 16 fue recorrido siguiendo el algoritmo DFS. Se parti´o desde el v´ertice 1, y desde all´ı se recorri´ o y enumer´ o el resto de los v´ertices. En verde quedan registrados los arcos por lo cuales se pas´o. 62

8 5

4

6

7 3 1 2 9 Figura 16: Un grafo recorrido en DFS Definici´ on Sea G = (V, E) un grafo conexo. Al ´arbol T = (V, E 0 ), donde E 0 ⊆ E se le llama un spanning tree de G. DFS recorre un spanning tree del grafo. En general entrega un componente del grafo, para encontrar todos los componentes basta con repetir la b´ usqueda partiendo cada vez de un v´ertice a´ un no visitado hasta agotar los v´ertices. Ver el algoritmo 2. Algoritmo 2 Depth First Search Sea stack = (v) while stack no vac´ıo do x ← top(stack); if y adyacente a x, no visitado then push(stack,y; else pop(stack) end if end while

6.10.2.

BFS, Breadth First Search

Sea G = (V, E) un grafo conexo. Apliquemos el siguiente algoritmo: Elegir v ∈ V como punto de partida. Marcar v como visitado, luego visitar cada uno de los vecinos no visitados de v, y reci´en entonces los vecinos de ´estos Ejemplo BFS Tomando el mismo grafo que en ejemplo de DFS, ahora se enumeran los v´ertices y se marcan los arcos recorridos, pero ahora con el m´etodo de b´ usqueda BFS. V´ease la figura 17 M´ as formalmente el algoritmo para buscar a los “ancho” es el 3.

63

9 4

8

5

6 3 1 2 7 Figura 17: Ejemplo de grafo recorrido en BFS

Algoritmo 3 Breadth First Search Sea queue = (v) while queue no vac´ıa do x ← front(queue); if y adyacente a x, no visitado then queue ← y; else Saque x de queue end if end while

64

p l(p)

w(py)

u y l(y)

Figura 18: Esquema de c´alculo de m´ınimo costo

6.11.

BFS v/s DFS

Ambos llegan a todos los v´ertices del componente. Los programas son similares. Complejidad (equivalente a tiempo de ejecuci´on) similares. ¿Como elegir? Si interesa una soluci´ on cualquiera: DFS Si interesa “la mejor” (por lo general referida a cercan´ıa de nodos): BFS 6.11.1.

Grafos Rotulados

En muchas aplicaciones los arcos tienen asociados “pesos” (costos), definimos entonces un grafo rotulado como un grafo G = (V, E) y una funci´ on P : E → C, con C alg´ un conjunto (t´ıpicamente C es R) que asocia el peso P (e) al arco e. Ejemplo Caso t´ıpico Nos interesa saber el costo (suma de los pesos de los arcos) para llegar a c/u de los v´ertices de G partiendo desde el v´ertice v. La soluci´ on es aplicaci´ on de BFS. Supongamos que tenemos establecido que el camino m´as corto de v a p tiene largo l(p). Supongamos que tenemos un vecino y, para el que tenemos la estimaci´on l(y). La ruta m´as corta que tengo de v a y pasando por p tiene costo l(p) + w(py), y si l(y) > l(p) + w(py), debi´eramos considerar: l(y) ←− l(p) + w(py) donde w(py) es el costo del arco {p, y}, ver la figura 18. Informalmente, el algoritmo es el siguiente: Inicialmente s´e que l(v) = 0. Puedo partir con l(p) = n´ umero grande para todos los p ∈ V , e ir actualizando los l(p) en BFS partiendo de v. Una versi´on formal es el algoritmo 4. Algoritmo 4 Costos m´ınimos desde un v´ertice Marque todos los v´ertices v ∈ V con l(v) = ∞, no permanente l(v) ← 0; marque v como permanente while Hay v´ertices no permanentes do l(y) ← m´ın(l(y), l(p) + w(py)), con y vecino de p; Marcar permanentemente el v´ertice con valor m´ınimo l(q); end while

65

6.12.

Relaciones y grafos bipartitos

Hab´ıamos definido una relaci´ on R entre conjuntos X e Y como R ⊂ X × Y , y escribimos: x R y ⇔ (x, y) ∈ R Si bien no es mismo decir x R y que y R x para casos pr´acticos presentes nos meteremos al bolsillo esta realidad. Si consideramos X ∩ Y = ∅, podemos modelar R como un grafo bipartito como lo muestra la figura 19. Esto lo

X

Y

Figura 19: Un grafo bipartito anotamos como grafo mediante R = (X ∪ Y, E). Teorema 6.11. Sea G = (X ∪ Y, E) un grafo bipartito con arcos entre X e Y . Entonces: X X δ(x) = δ(y) = |E| x∈X

y∈Y

Demostraci´ on. Cada arco tiene un v´ertice en X, y la primera suma es el n´ umero total de arcos vistos desde X. Lo mismo respecto a la segunda suma. Ejemplo Se tiene un grupo de personas y un grupo de trabajos (jobs), tal que cada persona esta calificada para ejecutar k trabajos, y para cada trabajo hay k personas calificadas. Demostrar: 1. El n´ umero de personas es igual al numero de trabajos. 2. Cualquier grupo de n personas incluye personas capaces de efectuar al menos n trabajos. Para contestar a esto, sea X el conjunto de personas, Y el conjunto de trabajos, y consideramos x R y si x est´ a calificado para y. 1. |E| = k|X| = k|Y |, o sea |X| = |Y | 2. Sea A un grupo cualquiera de personas, y sea J(A) el conjunto de trabajos para los que hay al menos una persona calificada en A. J(A) = {y : (x, y) ∈ R ∧ x ∈ A} Si EA es el conjunto de arcos que poseen un v´ertice en A, entonces |EA | = k|A|, y como cada tarea j ∈ J(A) tiene a lo m´ as k personas en A capacitadas para efectuarlo: X |EA | = δ(j) j∈J(A)

≤

X

k

j∈J(A)

= k · |J(A)| 66

Combinando ´esto con lo anterior: k|A| = k|J(A)| |A| = |J(A)| Definici´ on Dado un grafo G = (V, E) se define un coloreo de arcos como una funci´on c : E −→ N tal que c(e1 ) 6= c(e2 ) si e1 ∩ e2 6= ∅. Ac´ a tenemos una partici´ on de los arcos E1 ∪ E2 ∪ · · · ∪ En tal que los arcos en Ei no tienen v´ertices en com´ un. Teorema 6.12. Sea G = (V, E) un grafo bipartito. Entonces el m´ınimo n´ umero de colores requerido para colorear sus arcos es el grado m´ aximo de G. Demostraci´ on. Usamos inducci´ on sobre el n´ umero de arcos m. Cuando m = 1, hay un u ´nico arco, y el grado m´aximo es 1. Claramente basta 1 color en este caso. Supongamos ahora que es cierto para todos los grafos bipartitos de m arcos y grado m´aximo k. Consideremos un grafo bipartito G = (X ∪ Y, E) con m + 1 arcos y grado m´aximo k. Elegimos un arco {x, y} ∈ E, y consideramos el grafo G0 = (X ∪ Y, E 0 ) donde E 0 = E r {{x, y}}, que tiene m arcos, y por tanto admite un coloreo de arcos con k colores. En G, tanto x como y tienen grado a lo m´as k; y al eliminar el arco {x, y}, en G0 δ(x) ≤ k − 1, De la misma forma δ(y) ≤ k − 1. Luego tanto x como y participan en a lo m´as k − 1 arcos y por tanto a lo m´ as est´ an rodeados por k − 1 colores. Ahora sea α un color no adyacente a x y β un color no adyacente y. Se pueden presentar dos casos: Caso simple: Si puedo elegir α = β, tomo ese color y asunto resuelto. Caso complejo: No puedo elegir α = β. Llamemos α a un color libre en x y β a un color libre en Y . Habr´ a un arco {x, y1 } de color β (de caso contrario β estar´ıa libre y podr´ıa elegir α = β como en el caso anterior). Puede haber un arco {x1 , y1 } de color α, un arco {x1 , y2 } de color β y as´ı sucesivamente. Este proceso de crear un camino a trav´es de elegir arcos entre X e Y de color β y entre Y y X de color α debe terminar, ya que el grafo tiene un n´ umero finito de v´ertices, y no puede formar un ciclo ya que no hay un arco de color α en x.

67

b

b y

y a

x

x

a

b y1

y1

b x1

b x1

a

a y2

y2

b x2

x2

b

a yn

xn

yn

a

xn

b

Como se ilustra en la figura, se pueden intercambiar los colores α y β, cayendo en el caso simple.

Esta t´ecnica de zig-zag e intercambio vale la pena tenerla presente, bastantes demostraciones se basan en ella.

6.13.

Minimal Spanning Tree (MST)

6.13.1.

Algoritmo de Prim

Sea T el ´ arbol actual, elegir el v´ertice v ∈ V − T el costo de llegar a ´el desde un v´ertice x ∈ T es m´ınimo. Luego agregar el arco {v, x} a T . Aplicamos el algoritmo al ejemplo usado para el algoritmo de Kruskal, ver figura 20. En l´ıneas verdes esta el minimal spanning tree, que en caso de empate se elige cualquiera. Teorema 6.13. El algoritmo de Prim genera un minimal spanning tree. Demostraci´ on. Por contradicci´ on: Sea w(G) el costo total de los arcos en G y sea T el spanning tree construido por el algoritmo, y e1 , e2 , . . . , en los arcos en el orden en que los elige el algoritmo. Entonces: w(T ) = w(e1 ) + w(e2 ) + · · · + w(en ) Ahora supongamos U un MST de G, y T no es m´ınimo, o sea w(U ) < w(T ). Sea ek el primer arco en T que no est´ a en U . Eliminando ek de T obtenemos 2 componentes que son ´ arboles. Habr´ a alg´ un arco e∗ ∈ U que conecta estos 2 componentes. Si w(e∗ ) < w(ek ) habr´ıamos elegido e∗ en vez de ek , as´ı que w(e∗ ) ≥ w(ek ). Siguiendo este razonamiento, siempre habr´ıa elegido un arco de costo menor que el en U , y w(T ) ≤ w(U ). Por lo tanto T es un MST. 68

a 3

v

8 e

6

9

1

b

7

4

d

2 c 5 Figura 20: Ejemplo del algoritmo de Prim a 3

v

8 e

6

9

1

b

7

4

d

2 c 5

Figura 21: Ejemplo de grafo para MST En este caso, la estrategia voraz de elegir “el mejor” sin considerar consecuencias futuras tiene ´exito.

6.14.

Algoritmo de Kruskal

Otra idea es ordenar los arcos en orden de costo creciente, y agregar sucesivamente el siguiente arco que no forma un ciclo. Este es el algoritmo de Kruskal. Ejemplo Algoritmo de Kruskal Supongamos el grafo de la figura 22. Aplicando el algoritmo, creamos un bosque (“forest”, colecci´on de ´ arboles). Inicialmente el bosque es cada v´ertice por s´ı solo, luego en cada paso conectamos dos ´arboles. Se van agregando arcos con el menor coste posible que no generen un ciclo. Como este grafo es conexo, se genera un spanning tree del grafo, ver la figura 22. En adici´ on, se genera un MST, por razonamiento similar al dado para el algoritmo de Prim.

69

a 3

v

e

6 1

b 4

d

2 c

Figura 22: Ejemplo del algoritmo de Kruskal

6.15.

Matchings

Discutimos un caso especial de la situaci´ on en que hay un conjunto X de personas y un conjunto Y de trabajos, donde cada persona est´ a calificada para alguno de los trabajos. Una pregunta con implicancias obvias es la siguiente: ¿C´ omo asignamos personas a las tareas, de forma que el n´ umero m´aximo de personas queda asignada a una tarea para la que est´ a calificada? Esta pregunta la traduciremos al lenguaje de grafos bipartitos. La relaci´on “estar calificado” nos da un grafo bipartito G = (X ∪ Y, E): El arco {x, y} indica que la persona x est´a calificada para la tarea y. Una asignaci´ on de tareas a personas corresponde a un “matching” en el sentido t´ecnico que definiremos ahora. Definici´ on Sea G = (X ∪ Y, E) un grafo bipartito. Un matching es un subconjunto M ⊆ E de arcos tal que no hay v´ertices en com´ un entre dos arcos. El tama˜ no del matching es el n´ umero de arcos en ´el. Por ejemplo, la figura 23 muestra dos matchings de un grafo, donde los arcos en M est´an marcados. Est´ a claro

x1

y1 x1

y1

x2

y2 x2

y2

x3

y3 x3

y3

x4

y4 x4

y4

(a) M1

(b) M2

Figura 23: Matchings en un grafo bipartito que M2 es mayor, en el sentido que contiene m´as arcos. No puede haber uno mayor, ya que si consideramos el conjunto {x1 , x2 , x3 }, en total s´ olo est´ an capacitados para {y2 , y3 }, por lo que necesariamente quedar´a uno de los tres sin trabajo asignado. Definici´ on Sea G = (X ∪ Y, E) un grafo bipartito. Un matching de G se dice maximal si no hay matchings con m´ as arcos. Un matching es completo si |M | = |X|. 70

Analizaremos primero las condiciones bajo las cuales hay matchings completos. Si para un conjunto de personas A definimos: J(A) = {y : {x, y} ∈ E para alg´ un x ∈ A} est´ a claro que debe cumplirse |J(A)| ≥ |A| para que haya un trabajo para cada integrante de A. Incluso esta condici´ on es necesaria y suficiente, como demostraremos. Teorema 6.14 (Hall). Sea G = (X ∪ Y, E) un grafo bipartito. Hay un matching completo de G si y s´ olo si para todo A ⊆ X tenemos |J(A)| ≥ |A|. Demostraci´ on. Demostramos implicancias en ambos sentidos. Si hay un matching completo, para cada subconjunto A ⊆ X tenemos en J(A) al menos los trabajos asignados por el matching a los integrantes de A, o sea |J(A)| ≥ |A|. Al rev´es, supongamos que para todo A ⊆ X se cumple |J(A)| ≥ |A|, y consideremos un matching M cualquiera de G. Si M no es completo, demostraremos c´ omo construir un nuevo matching M 0 tal que |M 0 | = |M |+1. Repitiendo el proceso, finalmente obtenemos un matching completo. Si M no es completo, hay alg´ un x0 ∈ X que no participa en M . Dado que por hip´otesis J({x0 }) ≥ 1, hay al menos un v´ertice y1 ∈ Y tal que {x0 , y1 } ∈ E. Si y1 no participa en M , podemos agregar el arco {x0 , y1 } a M , dando el matching prometido M 0 . Por otro lado, si hay un arco {x1 , y1 } ∈ M , y x1 no tiene trabajo asignado, habr´ a un trabajo y2 para el que x1 est´ a calificado. Podemos eliminar el arco {x1 , y1 } y agregar los arcos {x0 , y1 } y {x1 , y2 }, obteniendo un matching M 0 con |M 0 | = |M | + 1. Continuando de la misma forma, tarde o temprano se agotan los v´ertices y encontraremos un camino con arcos alternadamente en M y no en M . Intercambiando estos arcos, obtenemos el matching prometido. Nuestro ejemplo previo indicar´ıa que de A a lo m´as |J(A)| podr´an encontrar trabajo. Esto lleva a: Definici´ on Sea G = (X ∪ Y, E) un grafo bipartito. La deficiencia de G es: d = m´ ax {|A| − |J(A)|} A⊆X

Con esto podemos demostrar: Teorema 6.15. Sea G = (X ∪ Y, E) un grafo bipartito de deficiencia d. Entonces el matching maximal M de G cumple |M | = |A| − d. Demostraci´ on. Primeramente, por los comentarios luego del primer ejemplo un matching no puede tener m´ as que el tama˜ no indicado. Basta entonces demostrar que hay un matching de ese tama˜ no. Tomamos un conjunto D de nuevos v´ertices con |D| = d. Definimos el grafo bipartito G∗ = (X ∗ ∪ Y ∗ , E ∗ ) mediante: X∗ = X Y∗ =Y ∪D E ∗ = E ∪ {{x, y} : x ∈ X ∧ y ∈ D} O sea, agregamos un nuevo conjunto de trabajos D para los que todos est´an calificados. Entonces G∗ cumple con las condiciones del teorema de Hall y tiene un matching completo M ∗ que incluye todos los v´ertices de D. Esto porque si A es un conjunto para el cual |A| − |J(A)| es m´aximo (o sea, d), la u ´nica forma de parear todos los elementos de A es incluir los elementos de D en el pareo. Eliminando los arcos que incluyen v´ertices de D de M ∗ obtenemos un matching de tama˜ no |X| − d. Definici´ on Sea G = (X ∪ Y, E) un grafo bipartito, y M un matching de G. Un camino se llama alternante para M si alterna arcos en M con arcos que no est´ an en M . En la demostraci´ on del teorema de Hall (teorema 6.14) usamos precisamente un camino alternante. El teorema 6.15 no es particularmente u ´til para encontrar un matching m´aximo, ni siquiera ayuda mucho a la hora de hallar su tama˜ no ya que considera analizar los 2|X| subconjuntos de X para determinar la deficiencia. Una forma pr´ actica de encontrar matchings m´ aximos las da el siguiente teorema. 71

Teorema 6.16. Sea G = (X ∪ Y, E) un grafo bipartito, y M un matching de G. Si M no es m´ aximo, G contiene un camino alternante para M . Demostraci´ on. Sea M ∗ un matching m´ aximo de G, y sea F el conjunto de arcos que est´an en M ∗ o M , pero no en ambos (esta es la diferencia sim´etrica entre estos conjuntos, que se anota F = M ∗ M M ). Los arcos en F y los v´ertices que contienen forman un grafo cuyos v´ertices tienen grado 1 ´o 2, por lo que sus componentes son caminos y ciclos. Pero en todo camino o ciclo los arcos en M alternan con arcos no en M , por lo que en todo ciclo el n´ umero de arcos en M debe ser igual al n´ umero de arcos no en M . Como |M ∗ | > |M |, hay m´as arcos no en M que arcos en M en F , y hay al menos un componente que es un camino con un n´ umero impar de arcos, y ´este es un camino alternante para M . Esto sugiere la siguiente estrategia para hallar un matching m´aximo: 1. Comience con un matching M cualquiera (un arco por s´ı solo sirve) 2. Busque un camino alternante para M 3. Si encontr´ o un camino alternante, construya un matching M 0 mejor de la forma usual, y vuelva al paso (2) 0 con M en vez de M 4. Si no hay camino alternante, M es m´ aximo Para hallar un camino alternante, podemos usar la siguiente variante de BFS. Comenzando con un v´ertice sin match x0 construimos un ´ arbol de caminos alternantes “parciales” desde x0 como sigue: 1. En el nivel 1 inserte todos los v´ertices y1 , y2 , . . . , yk adyacentes a x0 . Si alguno de estos v´ertices no tiene match, digamos yi , det´engase. x0 yi es un camino alternante. 2. Si todos los v´ertices en el nivel 1 tienen match, inserte v´ertices x1 , x2 , . . . , xk que son matches de y1 , y2 , . . . , yk en el nivel 2. 3. En el nivel 3, inserte los v´ertices adyacentes a los de nivel 2 que no tienen match con ellos. Si alguno de ellos no tiene match, det´engase: El camino desde x0 hasta ´el es un camino alternante. 4. Si todos los v´ertices de nivel 3 tienen match, inserte sus matches en el nivel 4, . . . Claramente este proceso puede terminar porque no hay v´ertices a insertar en un nivel impar. En tal caso, no hemos hallado un camino alternante, y habr´ a que intentar otro punto de partida. Si ninguno de los v´ertices sin match resulta en un camino alternante, el match que tenemos es m´aximo. Ejemplo Considere el grafo dado por la tabla 1, y el matching inicial {x1 y3 , x2 y1 , x3 y5 , x4 y4 }. x1 x2 x3 x4 x5

y1 y1 y1 y2 y3

y3 y3 y3 y5 y4 y5 y4

Cuadro 1: Un grafo bipartito El ´ arbol con ra´ız en x5 se ilustra en la figura 24. De la figura se ve que en el nivel 3 y2 no tiene match, as´ı que x5 y4 x4 y2 es un camino alternante. Intercambiando el estado de los arcos en este camino da el match completo {x1 y3 , x2 y1 , x3 y5 , x4 y2 , x5 y4 }.

6.16.

Transversals de familias de conjuntos finitos

Ejemplo En la Universidad de San Mateo, en el Departamento de Computaci´on todo lo resuelven mediante comit´es de sus integrantes. Hay seis profesores en el Departamento, profesores Acevedo, von Brand, Ca˜ nas, Dombroskaia, Ernst y Fredes. Est´ an organizados en los siguientes comit´es:

72

x5

y3

y4

x1

x4

y1

y2

y5

x3

x2

´ Figura 24: Arbol de caminos alternantes parciales con ra´ız en x5 Acad´emico: {Acevedo, Fredes} Investigaci´ on: {Acevedo, von Brand, Fredes} Administraci´ on: {von Brand, Fredes} Estacionamientos: {Ca˜ nas, Dombroskaia, Ernst} Se decide que cada comit´e debe enviar un representante al nuevo Comit´e de Comit´es del Departamento, y cada uno puede representar s´ olo a un comit´e. ¿Es posible crear este comit´e? Dados los miembros de los distintos comit´es, esto se puede lograr de diferentes formas. Por ejemplo, podemos elegir a Acevedo, von Brand, Ca˜ nas y Dombroskaia. Si embargo, si el comit´e de estacionamientos estuviera formado s´ olo por von Brand y Ca˜ nas, no se puede formar el Comit´e de Comit´es. La forma general de este problema se expresa m´as claramente usando la noci´on de familia de conjuntos. Tenemos la familia F = {Si : i ∈ I} de conjuntos (ac´ a I es un conjunto ´ındice), no necesariamente diferentes, y buscamos representantes si para i ∈ I tales que si ∈ Si y i 6= j ⇒ si 6= sj Tal conjunto de representantes distintos se suele llamar transversal de F. Nuestro problema es entonces hallar condiciones que aseguren que la familia F tenga un transversal. En realidad, esto no es m´ as que una forma disfrazada del problema de hallar un matching. Para ver esto, construimos un grafo bipartito cuyas partes corresponden a los conjuntos y a los elementos, y hay arcos que unen a los elementos con los conjuntos a los que pertenecen. La figura 25 muestra la situaci´on de los comit´es de la Universidad de San Mateo. En general, definimos G = (X ∪ Y, E) como X=I (los nombres de los conjuntos) [ Y = Si (todos los elementos de los conjuntos) i∈I

y el arco iy est´ a en E si y ∈ Si . Entonces un transversal de F no es m´as que un matching completo de G. En estos t´erminos la condici´ on de Hall es f´ acil de expresar. Un subconjunto H de I es una subfamilia de F, y J(H) es 73

Académico

Acevedo

Administración

von Brand

Investigación

Cañas

Dombroskaia

Estacionamientos

Ernst

Fredes

Figura 25: Comit´es del Departamento de Computaci´on, Universidad de San Mateo simplemente los miembros de todos esos conjuntos, o sea: [ J(H) = Si i∈H

En estos t´erminos, el teorema de Hall es: Teorema 6.17. La familia finita de conjuntos F = {Si : i ∈ I} tiene un transversal si y s´ olo si [ Si ≥ H para todo H ⊆ I i∈H

Una forma simple de expresar ´esto es decir que cualquier uni´on de k de los conjuntos debe tener al menos k miembros en total. En realidad este es el teorema de Hall original, que tambi´en se conoce como “Hall’s Marriage Theorem”, por la interpretaci´ on siguiente: I es un conjunto de mujeres, mientras Si corresponde al conjunto de hombres con los cuales i ∈ I estar´ıa dispuesta a casarse. Entonces hay forma de conseguirle pareja a todas las mujeres si y s´ olo si para cada conjunto de mujeres el conjunto de hombres con los que estar´ıan dispuestas a casarse en total no es menor al conjunto de mujeres.

7.

Digrafos, redes, flujos

Definici´ on Un digrafo (o grafo dirigido) consta de un conjunto finito V de v´ertices, y un subconjunto A de V × V , cuyos miembros se llaman arcos. Anotaremos D = (V, A) para el digrafo definido de esta forma. Los digrafos se pueden representar gr´ aficamente de forma similar a los grafos, s´olo que ac´a un arco es un par ordenado (x, y), mientras en el grafo es un par no ordenado {x, y}. Si (x, y) es un arco, lo indicamos mediante una flecha de x a y, si hay un arco (x, x) lo indicamos mediante un ciclo, si hay arcos (x, y) e (y, x) los indicamos por dos flechas. La figura 26 muestra ejemplos. Nuestras representaciones de grafos para uso computacional se aplican con cambios obvios a este caso. Formalmente, un digrafo es simplemente otra manera de representar una relaci´on R entre elementos del mismo conjunto (un grafo bipartito, por otro lado, representa una relaci´on entre elementos de conjuntos disjuntos). Las propiedades de las relaciones pueden f´ acilmente traducirse en propiedades del digrafo. Por ejemplo, si la relaci´ on es sim´etrica los arcos aparecen en pares (salvo los loops), (x, y) es un arco exactamente cuando lo es (y, x). Las definiciones de camino, camino simple y ciclo son an´alogas a las de grafos. As´ı, un camino dirigido en D = (V, A) es una secuencia de v´ertices v1 , v2 , . . . , vk tal que (vi , vi+1 ) est´a en A para 1 ≤ i ≤ k − 1, un camino dirigido simple es un camino dirigido en que todos los v´ertices son diferentes, y un ciclo dirigido es un camino dirigido en que todos los v´ertices son distintos, s´olo que v1 = vk . 74

Figura 26: Ejemplos de digrafos

7.1.

Redes y rutas cr´ıticas

Hay muchas situaciones que se pueden modelar mediante digrafos, no mediante grafos. Un ejemplo t´ıpico es la red de calles, donde hay rutas de una sola v´ıa. Es com´ un que se asocien costos o distancias a los arcos. Con esta idea en mente, usaremos red para un digrafo D = (V, A) junto con una funci´on w : A → N. Restringimos el rango de la funci´ on a enteros positivos para evitar problemas con la existencia de soluciones ´optimas, en la pr´actica esta restricci´ on suele ser f´ acil de levantar. Un caso t´ıpico de aplicaciones de redes es las redes de actividades. Suponiendo un gran proyecto de construcci´ on, ´este se subdivide en actividades menores. Las actividades a su vez est´an relacionadas, en el sentido que algunas no pueden iniciarse antes que terminen otras. Al planificar un proyecto de este tipo se suele usar una red de actividades, con arcos representando actividades y los v´ertices representando “eventos”, donde un evento es el fin de una actividad. El peso de un arco es la duraci´on de la actividad, y se busca organizar las actividades de forma de minimizar el tiempo total del proyecto. Ejemplo La tabla 2 da las duraciones de las actividades (en meses), y las dependencias entre ellas (que actividades deben estar completas antes de comenzar la actividad indicada). Act A B C D E F G H I J

Descripci´ on Dise˜ no del producto An´ alisis de mercado An´ alisis de producci´on Prototipo del producto Dise˜ no de folleto An´ alisis de costos Pruebas del producto Entrenamiento ventas Definici´ on de precios Reporte del proyecto

Requisitos

A A A C D B, E H F , G, I

Dur 5 1 2 3 2 3 4 2 1 1

Cuadro 2: Actividades y dependencias El primer paso es construir la red de actividades, ver figura 27. Para cada evento calcularemos E(v), el instante m´ as temprano en que ese evento puede tener lugar. Esto corresponde al momento m´as temprano en que todas las actividades previas a v han terminado. Iniciamos con E(1) = 0. Luego est´a claro que E(2) = 5, ya que la u ´nica actividad involucrada es A = (1, 2). Ahora, como 3 involucra a A = (1, 2) y a E = (2, 3), E(3) = m´ ax{E(1) + 1, E(2) + 2} = m´ ax{0 + 1, 5 + 2} = 7. Continuando, obtenemos: v: 1 2 3 4 5 6 7 8 E(v): 0 5 7 7 8 9 12 13 con lo que el plazo m´ınimo es de 12 meses. Este ejemplo es un caso especial del problema de calcular el camino m´as largo en una red. Usamos BFS (ajustado 75

5

D

2

G

C

A

4

J

F

1 E

8

7 I

B H 6

3 Actividad: A Arco: (1, 2) Duraci´ on: 5

B (1, 3) 1

C (2, 4) 2

D (2, 5) 3

E (2, 3) 2

F (4, 7) 3

G (5, 7) 4

H (3, 6) 2

I (6, 7) 1

J (7, 8) 1

Figura 27: Una red de actividades para digrafos) y en cada v´ertice visitado calculamos E(v) mediante la regla: E(s) = 0

E(v) = m´ ax{E(u) + w(u, v)} u

donde el m´ aximo es sobre los v´ertices u predecesores de v. Este m´etodo de estudiar redes de actividades es parte de la t´ecnica que se conoce como an´ alisis de camino cr´ıtico. El resto de la t´ecnica contin´ ua como sigue: Calculamos L(v), el u ´ltimo instante en que puede ocurrir el evento v sin retrasar el proyecto completo de forma similar a como se calcularon los E(v), pero comenzando del evento final y trabajando en reversa. O sea: L(t) = E(t)

L(v) = m´ın{L(x) − w(v, x)} x

donde el m´ınimo es sobre los v´ertices x sucesores de v. Podemos adem´as calcular la holgura de cada actividad (u, v), que representa el m´ aximo retraso que puede sufrir el comienzo de la actividad sin retrasar el fin del proyecto: F (u, v) = L(v) − E(u) − w(u, v) Las actividades sin holgura se dice que son cr´ıticas, cualquier retraso en ´estas se traduce en un retraso del proyecto completo. Toda red de actividades tiene al menos un camino dirigido entre principio y fin formado u ´nicamente por actividades cr´ıticas, tal camino se llama ruta cr´ıtica. Aplicando esto al ejemplo da: v: 1 2 3 4 5 6 7 8 E(v): 0 5 7 7 8 9 12 13 L(v): 0 4 8 11 7 10 11 13 y tenemos las holguras: Actividad: A B C D E F G H I J Arco: (1, 2) (1, 3) (2, 4) (2, 5) (2, 3) (4, 7) (5, 7) (3, 6) (6, 7) (7, 8) Holgura: 0 8 2 0 2 2 0 2 2 0

7.2.

Redes y Flujos

En lo que sigue interpretaremos los arcos como “tuber´ıas” por las que puede fluir alguna mercader´ıa. Los pesos num´ericos representan la capacidad del arco. Adem´as, habr´a un v´ertice s con la propiedad que todos los arcos que contienen a s se alejan de ´el, y otro v´ertice t con la propiedad de que todos los arcos que lo contienen se dirigen a ´el. Al primero se le llama fuente (source), al segundo sumidero (sink). En resumen, trataremos con redes que incluyen: 76

(i) Un digrafo D = (V, A) (ii) Una funci´ on de capacidad c : A → N (iii) Una fuente s y un sumidero t Un ejemplo se ve en la figura 28.

a

3

5

4

b

2

d

4 t

s 3

7

5

c Figura 28: Una red con capacidades de cada arco Supongamos que alg´ un material fluye por la red, y sea f (x, y) el flujo a lo largo del arco (x, y). Insistiremos que, salvo para la fuente y el sumidero, que el flujo que arriba a un v´ertice v debe ser el flujo que sale. Adem´ as requeriremos que ning´ un arco tenga un flujo mayor que su capacidad. Esto queda incluido en nuestra definici´ on. Definici´ on Un flujo en una red es una funci´on que asigna un n´ umero f (x, y) a cada arco (x, y), sujeto a las condiciones: Viabilidad: f (x, y) ≤ c(x, y) para todo arco (x, y) ∈ A Skew symmetry: (“Simetr´ıa torcida”) (f (y, x) = −f (x, y) para todo arco (x, y) ∈ A Conservaci´ on: Para todo u ∈ V − s, t requerimos: X f (u, v) = 0 v∈V

El valor del flujo es: X val(f ) = f (s, v) v∈V

Como no se permite acumulaci´ on en los v´ertices intermedios, est´a claro que el flujo que sale de s debe ser el flujo que entra en t: X val(f ) = f (v, t) v∈V

El valor com´ un de estas dos cantidades es el valor del flujo, que se anota val(f ). Un problema obvio es obtener el valor m´ aximo del flujo en una red. La funci´ on siguiente es un flujo en la red de la figura 28: (x, y): (s, a) (s, b) (s, c) (a, d) (b, d) (c, d) (a, t) (c, t) (d, t) f (x, y): 3 2 3 1 2 1 2 2 4 Exploremos un poco las propiedades de la definici´on. La viabilidad indica u ´nicamente que el flujo no puede exceder la capacidad del enlace. Skew symmetry es simplemente una conveniencia notacional (b´asicamente, si 77

vamos “contra corriente” contabilizamos el flujo como negativo). La conservaci´on indica que el flujo neto que sale de un v´ertice es nulo, y por simetr´ıa el que entra tambi´en: X f (v, u) = 0 v∈V

Si no hay arco (u, v), no puede haber flujo entre ellos, y f (u, v) = f (v, u) = 0. Para conveniencia, definimos los flujos de entrada y salida de un v´ertice: X inflow(v) = f (u, v) u∈V f (u, v) > 0

X

outflow(v) =

f (v, u)

u∈V f (v, u) > 0

7.2.1.

Trabajando con flujos

Para conveniencia, usaremos una convenci´ on de suma impl´ıcita, en que si mencionamos un conjunto de v´ertices en f , estamos considerando la suma de los flujos sobre ese conjunto. Por ejemplo, al anotar f (X, Y ), donde X e Y son conjuntos de v´ertices, entenderemos: X f (X, Y ) = f (x, y) x∈X y∈Y

En estos t´erminos, la condici´ on de conservaci´ on se reduce a f (u, V ) = 0 para todo u ∈ / {s, t}. Adem´as, omitiremos las llaves al restar conjuntos de un solo elemento. Por ejemplo, en f (s, V − s) = f (s, V ) la notaci´on V − s significa el conjunto V r {s}. Esto simplifica mucho las ecuaciones que involucran flujos. Por ejemplo, el lema siguiente recoge varias de las identidades m´ as comunes. La demostraci´ on queda como ejercicio. Lema 7.1. Sea D = (V, A) una red, y sea f un flujo en D. Entonces: 1. Para todo X ⊆ V , tenemos f (X, X) = 0 2. Para todo X, Y ⊆ V tenemos f (X, Y ) = −f (Y, X) 3. Para todo X, Y, Z ⊆ V con X ∩ Y = ∅ tenemos f (X ∪ Y, Z) = f (X, Z) + f (Y, Z) y f (Z, X ∪ Y ) = f (Z, X) + f (Z, Y ) Como ejemplo de uso de la notaci´ on, demostraremos que: val(f ) = f (V, t) Intuitivamente, lo que entra a la red por la fuente debe salir por el sumidero, ya que no se permiten acumulaciones entremedio. Formalmente: val(f ) = f (s, V ) = f (V, V ) − f (V − s, V ) = −f (V − s, V ) = f (V, V − s) = f (V, t) + f (V, V − s − t) = f (V, t)

78

7.3.

M´ etodo de Ford-Fulkerson

Presentaremos ahora una manera de obtener el flujo de m´aximo valor en una red. No lo llamaremos “algoritmo”, ya que la estrategia general puede implementarse de varias formas, con caracter´ısticas diferentes. En el proceso introduciremos varias ideas importantes en muchos problemas relacionados con flujos. El m´etodo de Ford-Fulkerson es iterativo. Comenzamos con f (u, v) = 0 para todo arco (u, v), con un valor inicial cero. En cada iteraci´ on aumentamos el valor del flujo a trav´es de identificar un “augmenting path” (un camino entre s y t que no est´ a en su m´ axima capacidad) y aumentamos el flujo a lo largo de este camino. Continuamos hasta que no se pueda encontrar otro augmenting path. Por el teorema max-flow min-cut se demuestra que al finalizar el valor del flujo es m´ aximo. Algoritmo 5 El m´etodo de Ford-Fulkerson Inicialice f en 0 while hay un augmenting path p do aumente el flujo f a lo largo de p end while

7.3.1.

Redes residuales

Intuitivamente, dada una red y un flujo f , la red residual consta de arcos que admiten flujo adicional. M´ as formalmente, supongamos una red D = (V, A) con capacidades c, fuente s y sumidero t. Sea f un flujo en D, y consideremos un par de v´ertices u y v. El flujo adicional que podemos enviar de u a v antes de sobrepasar la capacidad del enlace es la capacidad residual del enlace (u, v): cf (u, v) = c(u, v) − f (u, v) Por ejemplo, si c(u, v) = 10 y f (u, v) = 7, podemos enviar un flujo adicional de 3 de u a v sin sobrepasar la capacidad del enlace. Cuando f (u, v) es negativo, cf (u, v) es mayor que la capacidad c(u, v). Por ejemplo, si c(u, v) = 4 y f (u, v) = −10, cf (u, v) = 14. Esto podemos interpretarlo como un flujo “contracorriente” de 10; para compensar eso hay que aumentar el flujo “con la corriente” en 10, y sobre eso agregar 4 para usar toda la capacidad. Dados una red D = (V, A) y un flujo f , la red residual inducida por f es Df = (V, Af ), donde Af = {(u, v) ∈ V × V : cf (u, v) > 0}. Los arcos de Df son ya sea arcos de D o sus reversos. En Df todos los arcos pueden admitir flujos mayores a cero. Un arco puede aparecer en Df s´ olo si (u, v) ∈ A o (v, u) ∈ A, as´ı que |Af | ≤ 2|A|. N´otese que Df es a su vez una red de flujos con capacidades cf . El siguiente lema relaciona flujos en D con flujos en Df . Conviene definir la suma de flujos f1 y f2 : (f1 + f2 )(u, v) = f1 (u, v) + f2 (u, v) N´ otese que esto no siempre es un flujo. Lema 7.2. Sea D = (V, A) una red con fuente s y sumidero t, y sea f un flujo en D. Sea Df = (V, Af ) la red residual inducida por f , y sea f 0 un flujo en Df . Entonces la suma f + f 0 es un flujo en D, con valor val(f + f 0 ) = val(f ) + val(f 0 ). Demostraci´ on. Primero, para verificar que es un flujo, debe cumplir las condiciones de la definici´on. Para skew symmetry tenemos: (f + f 0 )(u, v) = f (u, v) + f 0 (u, v) = −f (v, u) − f 0 (v, u) = −(f (v, u) + f 0 (v, u)) = −(f + f 0 )(v, u) Para las restricciones de capacidad, note que f 0 (u, v) ≤ cf (u, v) para todo u, v ∈ V . Por tanto: (f + f 0 )(u, v) = f (u, v) + f 0 (u, v) ≤ f (u, v) + (c(u, v) − f (u, v)) = c(u, v) 79

Finalmente: val(f + f 0 )) = (f + f 0 )(s, V ) = f (s, V ) + f 0 (s, V ) = val(f ) + val(f 0 )

7.3.2.

Augmenting paths

Dada una red D = (V, A) y un flujo f , un augmenting path p es un camino dirigido entre s y t en la red residual Df . Por la definici´ on de red residual, cada arco (u, v) a lo largo de p admite flujo positivo de u a v sin violar la restricci´ on de capacidad. Est´ a claro que podemos aumentar el flujo a lo largo de p en cf (p) = m´ın {cf (u, v)} (u,v)∈p

sin violar las restricciones de capacidad. A esto se le llama la capacidad residual de p. Lema 7.3. Sea D = (V, A) una red, sea f un flujo en D, y sea p un augmenting path en Df . Defina la funci´ on fp : V × V → N mediante:   si (u, v) est´ a en p cf (p) fp (u, v) = −cf (p) si (v, u) est´ a en p   0 caso contrario Entonces fp es un flujo en Df con valor val(fp ) = cf (p) > 0. De lo anterior tenemos: Corolario 7.4. Sea D = (V, A) una red, f un flujo en D y p un augmenting path en Df . Sea fp como definido en el lema 7.3, y defina f 0 : V × V → N mediante f 0 = f + fp . Entonces f 0 es un flujo en D, y su valor es val(f 0 ) = val(f ) + val(fp ) ≥ val(f ). Demostraci´ on. Inmediato por los lemas 7.2 y 7.3. Para clarificar estas ideas, v´eanse las figuras 29 y 30. La figura 29 muestra una red. La figura 30a muestra un

a

12

c

20

16

s

10

4

9

7

t

13

4

b

14

d

Figura 29: Una red flujo en la red de la figura 29, 30b muestra la red residual con ese flujo con un augmenting path marcado. Este augmenting path tiene capacidad residual 4, y 30c muestra el resultado de aumentar el flujo. 80

a

12/12

a

c

12

c

a

5

c

15

15/20

11/16

12/12

11

19/20

11/16

5 4

s

0/10

1/4

4/9

t s

7/7

11

3

7

t s

0/10

1/4

0/9

7/7

t

5 8/13

4

4/4

12/13

4/4

3

b

11/14

b

d

(a) Un flujo

11

d

b

(b) La red residual

11/14

d

(c) El flujo aumentado

Figura 30: Flujos, redes residuales, augmenting paths 7.3.3.

Cortes

La idea del m´etodo de Ford-Fulkerson es hallar un augmenting path y aumentar el flujo a lo largo de ´el. Cuando este proceso termina, tenemos un flujo de valor m´aximo. Esto lo garantiza el teorema max-flow min-cut, que es nuestro pr´ oximo objetivo. Primeramente consideraremos el concepto de un corte (cut) en una red. Un corte (S, T ) corresponde simplemente a una partici´ on de los v´ertices de la red en conjuntos S y T = V r S tal que s ∈ S y t ∈ T . V´ease la figura 31. Si f es un flujo, el flujo neto a trav´es del corte (S, T ) se define como f (S, T ). En nuestro

a

12/12

c

15/20

11/16

s

0/10

4/9

1/4

7/7

t

8/13

4/4

b

11/14

d

S

T

Figura 31: Un corte en el flujo de la red de la figura 30a caso (figura 31) el flujo neto es 12 − 4 + 11 = 19. La capacidad del corte (S, T ) es c(S, T ), que en la misma figura corresponder´ıa a 12 + 14 = 16. Tambi´en se define un corte m´ınimo (minimum cut) como un corte de capacidad m´ınima. N´ otese que el flujo neto que cruza el corte incluye flujos de S a T (aportes positivos) y flujos de T a S (aportes negativos). Por otro lado, en las capacidades se incluyen s´olo las de arcos de S a T . El lema siguiente (7.5) relaciona los flujos a trav´es de cortes de la red. Lema 7.5. Sea f un flujo en la red D = (V, A) con fuente s y sumidero t, y sea (S, T ) un corte de la red. Entonces el flujo neto a trav´es del corte es el valor del flujo.

81

Demostraci´ on. Notando que por conservaci´ on de flujo f (S − s, V ) = 0, tenemos: f (S, T ) = f (S, V ) − f (S, S) = f (S, V ) = f (s, V ) + f (S − s, V ) = f (s, V ) = val(f )

Un corolario inmediato del lema 7.5 es el resultado que demostramos antes, que el flujo al sumidero es el valor del flujo en la red. Pero tambi´en podemos deducir: Corolario 7.6. El valor de cualquier flujo f en una red D est´ a acotado por arriba por la capacidad de cualquier corte en D. Demostraci´ on. Sea (S, T ) un corte cualquiera de D y sea f un flujo. Por el lema 7.5 y las restricciones de capacidad: val(f ) = f (S, T ) XX = f (u, v) u∈S v∈T

≤

XX

c(u, v)

u∈S v∈T

= c(S, T )

Una consecuencia inmediata del corolario 7.6 es que el valor de un flujo est´a acotado por la capacidad de un cut m´ınimo. El teorema siguiente nos dice que el flujo m´aximo en realidad es esta cota. Teorema 7.7 (Max-flow min-cut). Si f es un flujo en la red D = (V, A) con fuente s y sumidero t, entonces las siguientes son equivalentes: (1) f es un flujo m´ aximo en D (2) La red residual Df no contiene augmenting paths (3) val(f ) = c(S, T ) para alg´ un corte (S, T ) de D Demostraci´ on. Demostramos la equivalencia a trav´es de un ciclo de implicancias. (1) ⇒ (2): Por contradicci´ on. Supongamos en contrario que f es m´aximo en D, pero que Df tiene un augmenting path p. Por el corolario 7.4 la suma f + fp es un flujo, cuyo valor es mayor que val(f ), lo que contradice la suposici´ on de que f es m´ aximo. (2) ⇒ (3): Supongamos que D no tiene augmenting path, o sea, no hay camino dirigido de s a t en Df . Definamos: S = {v ∈ V : hay un camino de s a v en Df } T =V −T Entonces (S, T ) es un corte de D, ya que obviamente s ∈ S y t ∈ / S ya que no hay camino de s a t en Df por suposici´ on. Para cada par de v´ertices u ∈ S y v ∈ T tenemos f (u, v) = c(u, v), dado que de lo contrario (u, v) ∈ Af y habr´ıa un camino s u → v y as´ı v ∈ S. Por el lema 7.5 tenemos val(f ) = f (S, T ) = c(S, T ). (3) ⇒ (1): Por el corolario 7.6 sabemos que val(f ) ≤ c(S, T ) para todos los cortes (S, T ). La condici´on val(f ) = c(S, T ) entonces asegura que el flujo es m´aximo.

Este teorema sirve para demostrar la validez del m´etodo de Ford-Fulkerson: Si en una iteraci´on no hay un augmenting path, quiere decir que el flujo actual es m´aximo. Una manera razonable de buscar un augmenting path es usar b´ usqueda a lo ancho en la red residual. A ´esto se le conoce como el algoritmo de Edmonds-Karp. 82

8.

Permutaciones

Definici´ on Una permutaci´ on de un conjunto finito no-vac´ıo X es una biyecci´on de X a X. Com´ unmente usaremos X = {1, 2, . . . , n}. Por ejemplo, una permutaci´on t´ıpica de {1, 2, . . . , 5} es la funci´ on α definida por la tabla: α

1 ↓ 2

2 ↓ 4

3 ↓ 5

4 ↓ 1

5 ↓ 3

Est´ a claro que hay n! permutaciones de un conjunto de n elementos (el valor de π(1) puede elegirse de n maneras, una vez elegido ´este quedan s´ olo n − 1 opciones para π(2), y as´ı sucesivamente, y finalmente queda s´olo una opci´ on para π(n)). Supongamos la permutaci´ on β definida por la tabla β

1 ↓ 3

2 ↓ 5

3 ↓ 1

4 ↓ 4

5 ↓ 2

1 ↓ 2 ↓ 5

2 ↓ 4 ↓ 4

3 ↓ 5 ↓ 2

4 ↓ 1 ↓ 3

5 ↓ 3 ↓ 1

1 ↓ 3 ↓ 5

2 ↓ 5 ↓ 3

3 ↓ 1 ↓ 2

4 ↓ 4 ↓ 1

5 ↓ 2 ↓ 4

Entonces la composici´ on βα se obtiene de α β N´ otese que en general βα 6= αβ: β α

Llamaremos Sn al conjunto de permutaciones de n elementos. Teorema 8.1. Las permutaciones Sn cumplen las siguientes: (i) Si π y σ est´ an en Sn , lo est´ a tambi´en πσ (ii) Para todas permutaciones π, σ, τ en Sn , se cumple: (πσ)τ = π(στ ) (iii) La funci´ on identidad, que llamaremos id, definida por id(r) = r es una permutaci´ on, y tenemos para todo σ en Sn id σ = σid = σ (iv) Para toda permutaci´ on π en Sn hay una permutaci´ on inversa π −1 en Sn tal que ππ −1 = π −1 π = id Demostraci´ on. La propiedad (i) sigue directamente de que la composici´on de biyecciones es una biyecci´ on, (ii) es una propiedad b´ asica de la composici´ on de funciones, (iii) es obvio, y (iv) es simplemente que toda biyecci´ on tiene una inversa.

83

N´ otese que esto equivale a decir que las permutaciones forman un grupo con la operaci´on de composici´ on. A este grupo se le llama el grupo sim´etrico de orden n, que se anota Sn . Es conveniente tener una notaci´ on compacta para permutaciones individuales. Consideremos nuevamente la permutaci´ on α, y notemos que α(1) = 2, α(2) = 4, α(4) = 1 Esto forma un ciclo (1 → 2 → 4 → 1) de largo 3. Similarmente, 3 y 5 forman un ciclo de largo 2, y podemos escribir α en notaci´ on de ciclos α = (124)(35) Toda permutaci´ on π se puede escribir en notaci´on de ciclos mediante Comience con alg´ un s´ımbolo (digamos 1), y trace el efecto de π sobre ´el y sus sucesores hasta que nuevamente encontremos 1, as´ı tenemos un ciclo Tome un s´ımbolo cualquiera que no haya sido considerado a´ un, y construya el ciclo que lo contiene de la misma forma Contin´ ue de la misma forma hasta haber dado cuenta de todos los s´ımbolos Por ejemplo, para la permutaci´ on β dada anteriormente, la notaci´on de ciclos es β = (13)(25)(4) N´ otese que 4 forma un ciclo “degenerado” por s´ı mismo, ya que β(4) = 4. En algunos casos simplemente omitiremos estos ciclos de largo 1, ya que corresponden a s´ımbolos que no son afectados por la permutaci´on. En todo caso, es mejor no omitirlos hasta que uno se haya familiarizado con la notaci´on. Aunque la descripci´ on de la permutaci´ on mediante ciclos es esencialmente u ´nica, hay dos maneras obvias en que podemos modificar la notaci´ on sin alterar la permutaci´on descrita. Primeramente, podemos elegir cualquiera de los elementos de cada ciclo como primero — por ejemplo, (78213) es lo mismo que (13782). Por otro lado, podemos reordenar los ciclos — por ejemplo, (124)(35) y (35)(124) corresponden a la misma permutaci´on. Lo importante son el n´ umero de ciclos, sus largos, y la disposici´ on de sus elementos. Ejemplo Se tienen cartas numeradas 1 a 12, que se reparten en filas como muestra la figura 32a. Luego se toman 1 4 7 10

2 5 8 11

3 6 9 12

1 2 3 4

(a) Original

5 6 7 8

9 10 11 12

(b) Columnas

Figura 32: Ordenamiento de cartas las cartas por filas y se distribuyen en columnas, quedando como lo muestra la figura 32b. ¿Cu´antas veces hay que repetir esta operaci´ on hasta obtener nuevamente el orden original? Esto corresponde a determinar el orden de la permutaci´on. Sea π la permutaci´on que corresponde a esta operaci´ on, vale decir, π(i) = j si la carta j aparece en la posici´on ocupada originalmente por la carta i. En notaci´ on de ciclos tenemos π = (1)(2 5 6 10 4)(3 9 11 8 7)(12) Las cartas 1 y 12 no cambian de posici´ on, y las dem´as forman ciclos de largo 5. Entonces al repetir esta operaci´ on 5 veces todas las cartas quedan en sus posiciones originales.

84

8.1.

Clasificaci´ on de permutaciones

A cada permutaci´ on π en Sn corresponde una partici´on de los n elementos en los elementos de sus ciclos. Al n´ umero de ciclos de cada largo de la permutaci´on le llamaremos su tipo. O sea, si π tiene αi ciclos de largo i (1 ≤ i ≤ n), el tipo de π es [1α1 2α2 . . . nαn ]. Es simple contabilizar las permutaciones de un tipo particular. Supongamos, por ejemplo, que nos interesa saber cu´ antos elementos de S14 tienen tipo [22 32 4]. Esto corresponde a poner los s´ımbolos 1, 2, . . . , 14 en el patr´ on (. .)(. .)(. . .)(. . .)(. . . .) y hay 14! formas de distribuir los 14 s´ımbolos en las 14 posiciones. Sin embargo, muchas de ´estas dan la misma permutaci´ on. Considerando cada ciclo, podemos elegir el primer elemento de ´el y el resto quedar´a determinado por la permutaci´ on. O sea, hay 2 maneras de obtener cada 2-ciclo, 3 maneras de obtener cada 3-ciclo, y 4 maneras de obtener cada 4-ciclo. El ordenamiento interno se puede llevar a cabo de 22 × 32 × 4 formas en este caso. En general, si el tipo es [1α1 2α2 . . . nαn ], habr´ an 1α1 × 2α2 × . . . × nαn ordenamientos internos equivalentes. Por otro lado, el orden de los ciclos del mismo largo es arbitrario, por lo que el n´ umero de reordenamientos en el caso general ser´ a α1 ! α2 ! . . . αn !, y el n´ umero de permutaciones de tipo [1α1 2α2 . . . nαn ] es 1α1 2α2

n! α1 ! α2 ! . . . αn !

. . . nαn

Definici´ on Si hay una permutaci´ on σ tal que σασ −1 = β se dice que β es conjugada de α. El teorema siguiente es b´ asico en la teor´ıa algebraica de permutaciones. Teorema 8.2. Dos permutaciones α y β son conjugadas si y s´ olo si tienen el mismo tipo. Demostraci´ on. Demostramos implicancias en ambas direcciones. Supongamos que α y β son conjugadas, de forma que podemos escribir σασ −1 = β. Si α(x1 ) = x2 , definamos y1 = σ(x1 ) e y2 = σ(x2 ); con x3 = α(x2 ) definimos y3 = σ(x3 ), y as´ı sucesivamente. Tenemos: β(y1 ) = σασ −1 (σ(x1 )) = σα(x1 ) = σ(x2 ) = y2 De forma similar, β(y2 ) = y3 , y as´ı sucesivamente. Est´a claro que esto es una biyecci´on entre el ciclo de α que contiene a x1 y el ciclo de β que contiene a y1 , y habr´an biyecciones similares entre los dem´as ciclos de α y β, que as´ı tienen el mismo tipo. Por otro lado, supongamos que α y β tienen el mismo tipo. Como tienen el mismo n´ umero de ciclos de cada uno de los largos, podemos construir una biyecci´ on entre ciclos del mismo largo de α y β, digamos (x1 , x2 , . . . , xr ) en α corresponde al ciclo (y1 , y2 , . . . , yr ) en β. Definiendo σ(x1 ) = y1 para este ciclo, y de forma similar para los dem´ as ciclos, tenemos σασ −1 = β ya que σασ −1 (y1 ) = σα(x1 ) = σ(x2 ) = y2 = β(y1 )

Una manera fundamental de clasificar permutaciones viene de considerarlas como composici´on de transposiciones, que son permutaciones que s´ olo intercambian dos elementos. O sea, una permutaci´on es una transposici´ on si es del tipo [1n−2 2] (tiene n − 2 ciclos de largo 1 y un ciclo de largo 2). Ahora bien, el ciclo (x1 x2 . . . xr ), transforma (x1 x2 . . . xr ) en (x2 x3 . . . xr x1 ), y este mismo efecto se logra intercambiando x1 con x2 , luego x1 con x3 , y as´ı sucesivamente. O sea, podemos escribir (recordar que las permutaciones se aplican de derecha a izquierda, y omitimos ciclos de largo uno): (x1 x2 . . . xr ) = (x1 xr ) . . . (x1 x3 )(x1 x2 ) Como toda permutaci´ on se puede descomponer en ciclos, toda permutaci´on puede expresarse en t´erminos de transposiciones. Por ejemplo: (1 3 6)(2 4 5 7) = (1 6)(1 3)(2 7)(2 5)(2 4)

85

N´ otese que las transposiciones se pueden traslapar, en que un elemento puede moverse m´as de una vez. Esta representaci´ on no es u ´nica, adem´ as de reordenar las transposiciones podemos usar un conjunto completamente diferente de ´estas, como: (1 3 6)(2 4 5 7) = (1 5)(3 5)(3 6)(5 7)(1 4)(2 7)(1 2) Sin embargo, hay una caracter´ıstica en com´ un entre todas estas descomposiciones. Sea c(π) el n´ umero total de ciclos de π, de forma que si π tiene tipo [1α1 2α2 . . . nαn ] entonces c(π) = α1 + α2 + . . . + αn , y combinamos π con una transposici´ on τ , dando τ π. Nos interesa determinar la relaci´on entre c(π) y c(τ π). Si τ intercambia a con b, tenemos τ (a) = b, τ (b) = a y τ (k) = k si k 6= a, b. Si a y b est´an en el mismo ciclo de π, podemos escribir: π = (ax . . . yb . . . z) y otros ciclos La permutaci´ on compuesta τ π (primero π, luego τ ) es f´acil de calcular. Tenemos que π(a) = x, . . . , π(y) = b, . . . , π(z) = 1; y τ π(a) = τ (x) = x, . . . , τ π(y) = τ (b) = a; y tambi´en τ π(b) = π(b), . . . τ π(z) = τ (a) = b. O sea, se corta el ciclo y resulta: π = (ax . . . y)(b . . . z) y los otros ciclos con lo que c(τ π) = c(π) + 1. Por otro lado, si a y b pertenecen a ciclos distintos, o sea podemos escribir π = (ax . . . y)(b . . . z) y otros ciclos vemos que τ π(y) = τ (a) = b y τ π(z) = τ (b) = a, o sea, que los ciclos se funden: π = (ax . . . yb . . . z) y los otros ciclos con lo que c(τ π) = c(π) − 1. En resumen, seguir una permutaci´on por una transposici´on cambia el n´ umero de ciclos en 1, y tenemos: Teorema 8.3. Sup´ ongase que la permutaci´ on π de Sn puede escribirse como la composici´ on de r transposiciones y tambi´en como la composici´ on de r0 transposiciones. Entonces r y r0 son ambos pares o ambos impares. Demostraci´ on. Sea π = τr τr−1 . . . τ1 , con τi (1 ≤ i ≤ r) una transposici´on. Como τ1 tiene un 2-ciclo y n − 2 1-ciclos: c(τ1 ) = 1 + (n − 2) = n − 1 Combinando τ1 con τ2 , τ3 , . . . , τr finalmente se obtiene π. En cada paso c aumenta o disminuye en 1. Sea g el n´ umero de veces que aumenta y h el n´ umero de veces que disminuye, El n´ umero final de ciclos ser´a c(π) = (n − 1) + g − h Pero tenemos g + h = r − 1, con lo que: r =1+g+h = 1 + g + (n − 1 + g − c(π)) = n − c(π) + 2g De la misma forma, para cualquier otra manera de expresar π como producto de transposiciones hay un entero g 0 tal que r0 = n − c(π) + 2g 0 con lo que r − r0 = 2(g − g 0 ) que es par. 86

En vista del teorema 8.3 podemos clasificar las permutaciones en pares o impares dependiendo del n´ umero de transposiciones que las conforman. Definimos el signo de la permutaci´on π, escrito sgn π, como +1 si π es par, y −1 si es impar. O sea: sgn π = (−1)r donde π se puede escribir como la composici´ on de r transposiciones. En particular, sgn id = (−1)0 = +1. Claramente, si π se puede descomponer en r transposiciones y σ se puede descomponer en s transposiciones, entonces πσ se puede descomponer en r + s transposiciones, o sea: sgn(πσ) = (−1)r+s = (−1)r · (−1)s = sgn π · sgn σ En particular, como ππ −1 = id, resulta sgn π = sgn π −1 . De lo anterior podemos deducir: Teorema 8.4. Para todo entero n ≥ 2 exactamente la mitad de las permutaciones de Sn son pares y la otra mitad impares. Demostraci´ on. Sea π1 , π2 , . . . , πk la lista de permutaciones pares en Sn . Esta lista no es vac´ıa, ya que id es par. Sea τ una transposici´ on cualquiera en Sn , por ejemplo τ = (1 2)(3)(4) . . . (n). Entonces τ π1 , τ π2 , . . . , τ πk son todas distintas, ya que si τ πi = τ πj entonces por propiedades de las operaciones en un grupo πi = (τ −1 τ )πi = τ −1 (τ πi ) = τ −1 (τ πj ) = (τ −1 τ )πj = πj A´ un m´ as, todas estas permutaciones son impares, ya que sgn(τ πi ) = sgn τ · sgn πi = (−1) · (+1) = −1 Finalmente, toda permutaci´ on impar ρ es de una de las τ πi (1 ≤ i ≤ k), ya que: sgn(τ −1 ρ) = sgn τ −1 · sgn ρ = (−1) · (−1) = +1 con lo que τ −1 ρ es par, y debe ser πi para alg´ un i (1 ≤ i ≤ k), y as´ı ρ = τ πi . Con esto tenemos una biyecci´ on entre las permutaciones pares e impares. Resulta que el conjunto de permutaciones pares es un subgrupo de Sn , que se llama el grupo alternante y se anota An . Esto tiene aplicaci´ on en muchas ´ areas, por ejemplo en “matem´aticas recreativas”. Ejemplo Ocho bloques marcados 1 a 8 se disponen en un marco cuadrado como se indica en la figura 33a. Una movida legal corresponde a deslizar un bloque al espacio vac´ıo. Demuestre que es imposible lograr la configuraci´ on de 33b. 1 4 7

2 5 8

3 6

8 7 6

(a) Inicial

5 4 3

2 1

(b) Final

Figura 33: ¿Puede hacerse? Si anotamos el espacio en blanco por , la configuraci´on inicial puede escribirse 1 2 3 4 5 6 7 8 , y la final solicitada es 8 5 2 7 4 1 6 3 . Claramente toda movida legal es una transposici´on, y debe haber un n´ umero par de ellas para que termine en su posici´ on inicial. La permutaci´on entre la configuraci´on final solicitada y la inicial es (1 8 3 2 5 4 7 6)( ); el ciclo de largo 8 que aparece ac´a es impar, por lo que esto no puede hacerse. N´ otese que esto sirve para demostrar lo que no puede hacerse, no significa que no son excluidas son todas posibles. 87

8.2.

Grupos de permutaciones

Definici´ on Sea G un conjunto de permutaciones de un conjunto finito X. Si G es un grupo (con la composici´ on de permutaciones) decimos que G es un grupo de permutaciones de X. Si tomamos X = {1, 2, . . . , n}, entonces un grupo de permutaciones es simplemente un subgrupo de Sn . Por ejemplo, los siguientes son todos los subgrupos de S3 : H1 = {id} H4 = {id, (2 3)}

H2 = {id, (1 2)} H3 = {id, (1 3)} H5 = {id, (1 2 3), (1 3 2)} H6 = S3

Resulta que H5 = A3 , el grupo alternante que definimos antes. Para ver si un subconjunto de un grupo finito es un subgrupo, basta verificar si es cerrado por lo demostrado anteriormente. Un caso interesante son las permutaciones pares. Sabemos que la composici´on de permutaciones pares es par, por lo que esto es un subgrupo (el grupo alternante An ). El orden de An es 21 n! Muchos otros ejemplos se obtienen como grupos de simetr´ıa de objetos geom´etricos. Por ejemplo, si rotulamos los v´ertices de un cuadrado 1, 2, 3, 4 en orden de las manecillas del reloj (ver la figura 34), cada simetr´ıa induce

4

1

3

2 Figura 34: Un cuadrado

una permutaci´ on del conjunto {1, 2, 3, 4}, y obtenemos la tabla 3. Por consideraciones geom´etricas estas ocho Identidad Rotaci´ on en 90o Rotaci´ on en 180o Rotaci´ on en 270o Reflexi´ on en diagonal 1 3 Reflexi´ on en diagonal 2 4 Reflexi´ on en bisector perpendicular de 1 2 Reflexi´ on en bisector perpendicular de 1 4

id (1 2 3 4) (1 3)(2 4) (1 4 3 2) (2 4) (1 3) (1 2)(3 4) (1 4)(2 3)

Cuadro 3: Simetr´ıas del cuadrado permutaciones forman un grupo, espec´ıficamente un subgrupo de S4 . Una situaci´ on similar se produce cuando estudiamos grafos en vez de figuras geom´etricas, en donde las “simetr´ıas” son permutaciones de los v´ertices que transforman arcos en arcos. A una permutaci´on de este tipo se le llama automorfismo del grafo (viene a ser un isomorfismo del grafo consigo mismo). Un ejemplo de grafo se ve en la figura 35, e interesa saber cu´antos automorfismos tiene. Primero observamos que los v´ertices del grafo caen naturalmente en dos grupos: Los v´ertices {1, 3, 5} son de grado 4, mientras {2, 4, 6} son de grado 2. Ning´ un automorfismo puede transformar un v´ertice del primer grupo en uno del segundo. Por otro lado, est´ a claro que podemos tomar cualquier permutaci´on de {1, 2, 3} y extenderla a un automorfismo del grafo. 88

6

1

5

2

4

3 Figura 35: Un grafo

Por ejemplo, si (1 3 5) es parte de un automorfismo α, entonces α tiene que transformar 2 en 4, ya que 2 es el u ´nico v´ertice adyacente a 1 y 3, y 4 es el u ´nico v´ertice adyacente a sus im´agenes 3 y 5. De la misma forma, α lleva 4 en 6 y 6 en 2, por lo que α = (1 3 5)(2 4 6). En forma an´aloga, cada una de las seis permutaciones de {1, 2, 3} puede extenderse de forma u ´nica a un automorfismo del grafo: id se extiende a id (1 3 5) se extiende a (1 3 5)(2 4 6) (1 5 3) se extiende a (1 5 3)(2 6 4)

(1 3) se extiende a (1 3)(4 6) (1 5) se extiende a (1 5)(2 4) (3 5) se extiende a (3 5)(2 6)

O sea, hay exactamente seis automorfismos, que son las permutaciones listadas arriba.

8.3.

´ Orbitas y estabilizadores

Sea G un grupo de permutaciones de un conjunto X. Veremos que la estructura del grupo lleva naturalmente a una partici´ on de X. Definamos la relaci´ on ∼ sobre X mediante x ∼ y ⇔ g(x) = y para alg´ un g ∈ G. Verificamos que ∼ es una relaci´ on de equivalencia de la forma usual: (Reflexiva) Como id es parte de todo grupo, y id(x) = x para todo x ∈ X, tenemos x ∼ x (Sim´ etrica) Supongamos x ∼ y, de forma que g(x) = y para alg´ un g ∈ G. Como G es un grupo, g −1 ∈ G, y como −1 g (y) = x, tenemos y ∼ x (Transitiva) Si x ∼ y y y ∼ z debe ser g1 (x) = y y g2 (y) = z para g1 , g2 ∈ G, y como G es un grupo, g2 g1 ∈ G, con lo que g2 g1 (x) = z y x ∼ z Como ∼ es una relaci´ on de equivalencia, define una partici´on de X; x e y pertenecen a la misma clase si y s´ olo si hay una permutaci´ on en G que transforma x en y. A las clases de equivalencia se les conoce como ´ orbitas de G en X. La ´ orbita de x es la clase que contiene a x: Gx = {y ∈ X : y = g(x) para alg´ un g ∈ G} Intuitivamente, la ´ orbita Gx son los elementos de X que no se distinguen de x en G. Por ejemplo, en el grafo de la figura 36 los automorfismos (omitiendo ciclos de largo 1) se obtienen combinando:

89

h

a

d

k

e

g

c

b

i

l

m

f

j

Figura 36: Un ejemplo de grafo

id (a b)

id (d f )

id (h i)(k l) (h j)(k m) (i j)(l m) (h i j)(k l m) (h j i)(k m l)

Hay un total de 2 × 2 × 6 = 24 permutaciones en este grupo. Son ´orbitas {a, b}, {c}, {d, f }, {e}, {g}, {h, i, j}, {k, l, m}, y se ve que “son parecidos” los elementos de cada una de ellas. Las ´ orbitas presentan un par de problemas num´ericos obvios: ¿Cu´antas ´orbitas hay? ¿Qu´e tama˜ nos tienen? Si G es un grupo de permutaciones, llamaremos G(x → y) al conjunto de permutaciones que llevan x a y, o sea: G(x → y) = {g ∈ G : g(x) = y} En particular, G(x → x) es el conjunto de permutaciones que tienen a x como punto fijo. Este conjunto se llama el estabilizador de x, y se anota Gx . N´ otese que si γ1 y γ2 est´an en Gx : γ2 γ1 (x) = γ2 (x) = x por lo que γ2 γ1 ∈ Gx , y Gx es un subgrupo de G. Tambi´en tenemos: Teorema 8.5. Sea G un grupo de permutaciones de X, y sea h ∈ G(x → y). Entonces G(x → y) = hGx el coset derecho de Gx respecto a h. Demostraci´ on. Si α pertenece al coset derecho hGx , tenemos α = hβ para alg´ un β ∈ Gx . O sea: α(x) = hβ(x) = h(x) = y con lo que α pertenece a G(x → y). Al rev´es, si γ ∈ G(x → y), entonces: h−1 γ(x) = h−1 (y) = x de manera que h−1 γ = δ, donde δ ∈ Gx , y as´ı γ = hδ ∈ hGx . Hemos demostrado que todo elemento de G(x → y) pertenece a hGx , y viceversa, y ambos conjuntos son iguales. Podemos usar el teorema 8.5 para calcular el tama˜ no del conjunto G(x → y), si recordamos que el tama˜ no del coset hGx es igual al tama˜ no del subgrupo: |G(x → y)| = |hGx | = |Gx | De forma muy similar al teorema 8.5 se demuestra lo siguiente: 90

Teorema 8.6. Sea G un grupo de permutaciones de X, y sea h ∈ G(x → y). Entonces G(x → y) = Gy h el coset izquierdo de Gy respecto a h. Demostraci´ on. Si α pertenece a Gy h, entonces α = βh para alg´ un β ∈ Gy , o sea: α(y) = βh(y) = β(x) = y y β ∈ G(x → y). Al rev´es, supongamos γ ∈ G(x → y), y consideremos: γh−1 (y) = γ(x) = y y por tanto γh−1 ∈ Gy , o γ ∈ Gy h. De los anteriores se sigue: Corolario 8.7. Sea G un grupo de permutaciones de X, sea x ∈ X un elemento cualquiera, e y un elemento en la ´ orbita de x. Entonces |Gx | = |Gy |. Demostraci´ on. Inmediato, ya que por los teoremas anteriores: |Gy | = |G(x → y)| = |Gx |

Teorema 8.8. Sea G un grupo de permutaciones de X, y sea x un elemento cualquiera de X. Entonces: |Gx| × |Gx | = |G| Demostraci´ on. Usamos la idea de contar por filas y columnas. El conjunto de pares (g, y) tales que g(x) = y puede describirse mediante una tabla: ···y··· .. . g .. .

Xsi (g, y) est´ a en S

rg (S)

cy (S) Sea S = {(g, y) : g(x) = y} como en la ilustraci´on de la tabla arriba. Como g es una permutaci´on, hay un u ´nico y tal que g(x) = y para cada g, con lo que rg (S) = 1. El total por columna cy (S) es el n´ umero de permutaciones g tal que g(x) = y, o sea, |G(x → y)|. Si y est´ a en la ´orbita Gx tenemos |G(x → y)| = |Gx |. Por otro lado, si y no est´ a en la ´ orbita Gx, |G(x → y)| = 0. Las dos formas de contar los elementos de S dan: X X cy (S) = rg (S) y∈X

g∈G

Al lado izquierdo hay |Gx| t´erminos que valen |Gx | cada uno, y los dem´as valen 0; al lado derecho hay |G| t´erminos que valen 1 cada uno. As´ı tenemos el resultado prometido. Por ejemplo, en el grafo de la figura 36 el grupo G de automorfismos tiene orden 24. La ´orbita de a es Ga = {a, b}, y |Ga| = 2 mientras el estabilizador Ga es las permutaciones que mantienen fijo a, de las que hay 2 × 6 = 12. De la misma forma, Gh = {h, i, j}, |Gh| = 3 y |Gh | = 2 × 2 = 4. Este teorema tambi´en permite calcular el tama˜ no de un grupo si se conoce el tama˜ no de una ´orbita y el estabilizador respectivo. Consideremos por ejemplo el grupo G de rotaciones en el espacio de un tetraedro, ver la figura 37. Las rotaciones alrededor del eje marcado son las que mantienen fijo el v´ertice d, y hay 3 de ´estas, |Gd | = 3. Por otro lado, girando el tetraedro en el espacio se puede colocar en la posici´on d cualquiera de los 4 v´ertices, o sea |Gd| = 4. En consecuencia, el grupo de rotaciones en el espacio de un tetraedro es de orden |G| = |Gd | × |Gd| = 3 × 4 = 12. 91

a

c d

b Figura 37: Rotaciones de un tetraedro

8.4.

N´ umero de o ´rbitas

Vamos ahora a contar el n´ umero de ´ orbitas de un grupo G de permutaciones de X. Cada ´orbita es un subconjunto de elementos indistinguibles bajo G, y el n´ umero de ´orbitas nos dice cu´antos tipos de elementos distintos hay. Como un ejemplo, sup´ ongase que se quieren fabricar tarjetas de identidad cuadradas, divididas en nueve cuadrados de los cuales se perforan dos. V´ease la figura 38 para algunos ejemplos. Est´a claro que las primeras dos no

Figura 38: Ejemplos de tarjetas de identidad se pueden distinguir, ya que se obtiene la segunda rotando la primera; en cambio, la tercera claramente es diferente de las otras, independiente de si se gira o se da vuelta. El grupo que est´ a actuando ac´ a es el grupo G de ocho simetr´ıas de un cuadrado, pero nos interesa el efecto que tiene sobre las 36 configuraciones de dos agujeros, no s´olo su acci´on sobre los cuatro v´ertices. El n´ umero de ´ orbitas es el n´ umero de tarjetas distinguibles. Hacer ´esto por la v´ıa de dibujar las 36 configuraciones, y analizar lo que ocurre con cada una de ellas con las 8 simetr´ıas es bastante trabajo. Por suerte hay maneras mejores. Dado el grupo de permutaciones G definimos: F (g) = {x ∈ X : g(x) = x} 92

O sea, F (g) es el n´ umero de puntos fijos de g. Nuestro teorema siguiente relaciona ´esto con el n´ umero de ´ orbitas. Teorema 8.9 (Burnside). El n´ umero de ´ orbitas de G sobre X est´ a dado por: 1 X |F (g)| |G| g∈G

Demostraci´ on. Nuevamente, contar por filas y columnas. Sea: E = {(g, x) : g(x) = x} Entonces el total por fila rg (E) es el n´ umero de x fijados por g, o sea |F (g)|. El total por columna cx (E) es el n´ umero de g que tienen x como punto fijo, o sea, |Gx |. Contabilizando E de ambas formas nos da: X X |F (g)| = |Gx | g∈G

x∈X

Supongamos que hay t ´ orbitas, y elijamos z ∈ X. Entonces por el teorema 8.6 si x pertenece a la ´orbita Gz entonces |Gx | = |Gz |. Una ´ orbita contribuye al lado derecho |Gz| t´erminos, cada uno de los cuales es |Gz |, y la contribuci´ on total es |Gz| × |Gz | = |G|, o sea: t=

1 X |F (g)| |G| g∈G

que es exactamente lo que quer´ıamos demostrar. Ahora estamos en condiciones de resolver nuestro problema de tarjetas de identidad. Necesitamos calcular el n´ umero de configuraciones fijas bajo cada una de las ocho permutaciones. Por ejemplo, cuando g es la rotaci´ on en 180o , hay 4 configuraciones fijas (ver la figura 39). La tabla 4 resume los valores. Con estos valores tenemos que el Operaci´ on Identidad Rotaci´ on en 90o Rotaci´ on en 180o Rotaci´ on en 270o Reflexi´ on en diagonal 1 3 Reflexi´ on en diagonal 2 4 Reflexi´ on en perpendicular a 1 2 Reflexi´ on en perpendicular a 1 4

Fijos 36 0 4 0 6 6 6 6

Cuadro 4: N´ umero de configuraciones respetadas por cada operaci´on n´ umero de ´ orbitas es: 1 (36 + 0 + 4 + 0 + 6 + 6 + 6 + 6) = 8 8 En este caso ser´ıa sencillo listar las 8 configuraciones por prueba y error, pero el resultado es aplicable en forma mucho m´ as general. Ejemplo Se fabrican collares con 13 cuentas blancas y 3 negras cada uno. ¿Cu´antos collares diferentes pueden hacerse? Podemos pensar en las 16 cuentas ubicadas en los v´ertices de un pol´ıgono regular on
de 16 lados. Una configuraci´ queda definida por las posiciones de las 3 cuentas negras, de las que hay 16 = 560. Dos configuraciones son 3 equivalentes si se obtienen rotando el collar o d´andolo vuelta (una reflexi´on corresponde a darlo vuelta). Son 32 simetr´ıas en total: La identidad fija las 560 configuraciones Hay 15 rotaciones en ´ angulos 2πn/16 (1 ≤ n ≤ 15), ninguna de las cuales tiene configuraciones fijas 93

Figura 39: Configuraciones fijas con rotaciones de 180o Hay 8 reflexiones en ejes que unen los puntos medios de lados opuestos, ninguna de ellas tiene configuraciones fijas Hay 8 reflexiones en ejes que unen v´ertices opuestos. Las posiciones de las 3 cuentas negras se mantienen s´ olo si una de ellas est´ a en uno de los v´ertices por los que pasa el eje, y las otras dos est´an dispuestas en forma sim´etrica. Hay 7 posiciones para una de las cuentas negras (y su contraparte). Esto hace un total de 2 × 7 = 14. Resumiendo, el n´ umero de collares diferentes es: 1 (560 + 8 × 14) = 21 32

8.5.

´Indice de ciclos

Definimos el tipo de una permutaci´ on como [1α1 2α2 . . . nαn ] si tiene αi ciclos de largo i (1 ≤ i ≤ n). Una expresi´ on af´ın asociada a la permutaci´ on g es: αn 1 α2 ζg (x1 , x2 , . . . , xn ) = xα 1 x2 . . . xn

Para un grupo G de permutaciones definimos el ´ındice de ciclos: ζG (x1 , x2 , . . . , xn ) =

1 X ζg (x1 , x2 , . . . , xn ) |G| g∈G

Esto est´ a ´ıntimamente relacionado a una funci´ on generatriz en la que xi marca los ciclos de largo i. Interesa entonces calcular ζG para diversos grupos de manera de tenerlos a mano m´as adelante. Por ejemplo, para las simetr´ıas del 94

cuadrado como vistas antes: ζG (x1 , x2 , x3 , x4 ) =

8.6.

1 4 (x + 2x21 x2 + 3x22 + 2x4 ) 8 1

N´ umero de coloreos distinguibles

Supongamos un grupo G de permutaciones de un conjunto X de n elementos, y a cada elemento se le puede asignar uno de r colores. Si el conjunto de colores es K, un coloreo es una funci´on ω : X → K. El n´ umero total de coloreos es rn , a este conjunto le llamaremos Ω. Ahora bien, cada permutaci´on g en G induce una permutaci´ on gb de Ω: Para ω definimos gb(ω) como el coloreo en el cual el color asignado a x es el que ω asigna a g −1 (x), vale decir: (b g (ω))(x) = ωg −1 (x) La figura 40 muestra un ejemplo. La funci´ on que lleva g a gb es una representaci´on del grupo G en un grupo

$g$

$\omega$

$\hat{g}(\omega)$ Figura 40: Ejemplo de gb(ω)

b de permutaciones de Ω. Dos coloreos son indistinguibles si uno puede transformarse en el otro mediante una G b en Ω. El n´ permutaci´ on gb; vale decir, si ambas pertenecen a la misma ´orbita de G umero de coloreos distinguibles b (inequivalentes) entonces es el n´ umero de ´ orbitas de G. Antes de aplicar nuestro teorema para el n´ umero de ´ orbitas b son isomorfos. Supongamos que gb1 = gb2 , de forma que debemos verificar que G y G (b g1 (ω))(x) = (b g2 (ω))(x) y en consecuencia ω(g1−1 (x)) = ω(g2−1 (x))

(ω ∈ Ω, x ∈ X)

Como esto es v´ alido para todo ω, en particular vale para el coloreo que asigna el color especificado a g1−1 x y otro color a todos los dem´ as miembros de X. En este caso particular la ecuaci´on nos dice que g1−1 (x) = g2−1 (x), con lo que g1 = g2 , y los grupos son isomorfos. Teorema 8.10. Si G es un grupo de permutaciones de X, y ζG (x1 , . . . , xn ) es su ´ındice de ciclos, el n´ umero de coloreos inequivalentes de X con r colores es ζG (r, . . . , r), donde un coloreo de X es una funci´ on w : X → K. Demostraci´ on. Interesa el n´ umero de o ´rbitas del grupo G operando sobre coloreos. Hemos demostrado que la b Adem´as, la f´ormula que da el n´ representaci´ on g → gb es una biyecci´ on, de forma que |G| = |G|. umero de ´ orbitas de b en Ω es G 1 X 1 X |F (b g )| = |F (b g )| b |G| |G| b g b∈G

g∈G

95

donde F (b g ) es el conjunto de coloreos fijados por gb. Supongamos ahora que ω es un coloreo fijado por gb, de forma que gb(ω) = ω, y sea (x y z . . .) un ciclo cualquiera de g. Tenemos: ω(x) = ω(g −1 (y)) = (b g (ω))(y) = ω(y) de forma que ω asigna el mismo color a x e y, y aplicando el mismo razonamiento, este es el color asignado a todo el ciclo. Esto ocurre con cada uno de los ciclos de g. Si g tiene k ciclos en total, el n´ umero de coloreos posibles es rk , ya que podemos asignar uno de los r colores a cada uno de los k ciclos. De esta forma, si g tiene αi ciclos de largo i (1 ≤ i ≤ n), tenemos α1 + α2 + . . . + αn = k y |F (b g )| = rk = rα1 +α2 +...+αn = ζg (r, r, . . . , r) y el resultado sigue de sumar ´esto. Ejemplo Coloreos posibles.

1

2

3

4

Si miramos estas permutaciones, F (g) corresponder´ıa al conjunto de configuraciones que la permutaci´ on g mantiene fijas. Aqu´ı s´ olo hay 4 que mantiene la misma configuraci´on, es decir, |F (g)| = 4, y la permutaci´ on corresponde a g = (1 2)(3 4). A cada ciclo de la permutaci´on g se le puede asignar un color en forma independiente. O sea, en este caso hay 22 = 4 opciones.

Con ´esto, para obtener el n´ umero de coloreos inequivalentes basta calcular el ´ındice de ciclos del grupo. Por ejemplo, el n´ umero de coloreos de los v´ertices de un cuadrado con r colores se obtiene: 1 4 (x + 2x21 x2 + 3x22 + 2x4 ) 8 1 1 ζG (r, r, r, r) = (r4 + 2r3 + 3r2 + 2r) 8

ζG (x1 , x2 , x3 , x4 ) =

Pero podemos hacer algo m´ as. Si hay r colores, podemos definir variables zi (1 ≤ i ≤ r) para representar los distintos colores. Entonces la funci´ on generatriz de los n´ umeros de nodos de cada color que se pueden asignar a un ciclo de largo k es simplemente: z1k + z2k + . . . zrk ya que ser´ıan k nodos, todos del mismo color. Si hay αk ciclos de largo k, entonces corresponde el factor: (z1k + z2k + . . . zrk )αk La anterior discusi´ on demuestra el siguiente resultado. Teorema 8.11 (Enumeraci´ on de P´ olya). Sea G un grupo de permutaciones de X, y ζG (x1 , . . . , xn ) su ´ındice de ciclos. La funci´ on generatriz del n´ umero de coloreos inequivalentes de X en que hay ni nodos de color i (1 ≤ i ≤ r, un1 ,n2 ,...,nr , es: X U (z1 , z2 , . . . , zr ) = un1 ,n2 ,...,nr z1n1 z2n2 . . . zrnr n1 ,n2 ,...,nr

= ζG (z1 + z2 + . . . + zr , z12 + z22 + . . . + zr2 , . . . , z1n + z2n + . . . + zrn ) 96

CH3

H

Cl

H

H H

H

H

H H

CH3 H H

H (a) Benceno

H

H

CH3 H

(b) Xyleno

(c) Clorotolueno

Figura 41: Algunos compuestos arom´aticos La teor´ıa de enumeraci´ on de P´ olya fue desarrollada para aplicaci´on a la qu´ımica. Algunos ejemplos de f´ ormulas qu´ımicas se dan en la figura 41. Este tipo de compuestos, derivados del benceno (figura 41a) son hex´agonos que pueden girar en el espacio. Hay muchas posibilidades de grupos de ´atomos que pueden reemplazar los hidr´ ogenos (H), como es radicales metilo (CH3 ) o ´ atomos de cloro (Cl). Una pregunta obvia entonces es cu´antos compuestos distintos pueden crearse con un conjunto de radicales, o cu´antos son posibles con un n´ umero particular de cada uno de un conjunto de radicales dados. 1

6

2

5

3

4

Figura 42: Hex´agono Para responder a estas preguntas requerimos el ´ındice de ciclos del grupo del hex´agono, como el mostrado en la figura 42. Las simetr´ıas respectivas se listan en la tabla 5. En consecuencia, el ´ındice de ciclos del grupo es: ζG (x1 , x2 , x3 , x4 , x5 , x6 ) =

1 6 (x + 3x21 x22 + 4x32 + 2x23 + 2x6 ) 12 1

Hecho el trabajo duro, calcular cu´ antos compuestos pueden crearse con hidr´ogenos (H) y metilos (CH3 ) es f´ acil: Corresponden a colorear los v´ertices con dos colores, lo que nos da: 1 6 (2 + 3 · 22 · 22 + 4 · 23 + 2 · 2) 12 = 13

ζG (2, 2, 2, 2, 2, 2) =

Si nos interesa determinar cu´ antos compuestos distintos tienen 2 radicales cloro (Cl), 2 metilos (CH3 ) y 2 hidr´ ogenos (H), usamos las variables u, v y w para estas tres opciones, y el valor buscado es simplemente: [u2 v 2 w2 ]ζG (u + v + w, u2 + v 2 + w2 , u3 + v 3 + w3 , u4 + v 4 + w4 , u5 + v 5 + w5 , u6 + v 6 + w6 ) = 11 Por otro lado, un ´ atomo de carbono puede unirse con cuatro otros ´atomos, dispuestos en los v´ertices de un tetraedro. 97

Operaci´ on Identidad Rotaci´ on 1/6 Rotaci´ on 2/6 Rotaci´ on 3/6 Rotaci´ on 4/6 Rotaci´ on 5/6 Reflexi´ on en 1 4 Reflexi´ on en 2 5 Reflexi´ on en 3 6 Reflexi´ on entre 1 2 y 4 5 Reflexi´ on entre 2 3 y 5 6 Reflexi´ on entre 1 6 y 3 4

Ciclos (1)(2)(3)(4)(5)(6) (1 2 3 4 5 6) (1 3 5)(2 4 6) (1 4)(2 5)(3 6) (1 5 3)(2 6 4) (1 6 5 4 3 2) (1)(2 6)(3 5)(4) (1 3)(2)(4 6)(5) (1 5)(2 4)(3)(6) (1 2)(3 6)(4 5) (1 4)(2 3)(5 6) (1 6)(2 5)(3 4)

Tipo [16 ] [6] [32 ] [23 ] [32 ] [6] [12 22 ] [12 22 ] [12 22 ] [23 ] [23 ] [23 ]

Cuadro 5: Grupo de simetr´ıas del hex´agono

1 1

2 2

3 3

4

4 (a) Eje a trav´ es de un v´ ertice

(b) Eje en el punto medio de aristas

Figura 43: Operaciones de simetr´ıa (rotaciones) de un tetraedro Las operaciones de simetr´ıa de un tetraedro en el espacio (s´olo rotaciones, no reflexiones) son giros alrededor de un eje que pasa por un v´ertice y el centroide de la cara opuesta (ver 43a) y giros alrededor de un eje que pasa por el punto medio de una arista y el punto medio de la arista opuesta (ver 43b). Las simetr´ıas son de los tipos dados en la tabla 6, y en consecuencia el ´ındice de ciclos del grupo es ζT (x1 , x2 , x3 , x4 ) =

1 4 (x + 8x1 x3 + 3x22 ) 12 1

As´ı, si tenemos dos radicales diferentes hay ζT (2, 2, 2, 2) = 5 compuestos diferentes posibles, y ζT (4, 4, 4, 4) = 36 si hay 4. Si hay dos tipos de radicales, la funci´ on generatriz es: ζT (u + v, u2 + v 2 , u3 + v 3 , u4 + v 4 ) = u4 + u3 v + u2 v 2 + uv 3 + v 4 Vale decir, hay un solo compuesto de cada una de las composiciones posibles.

SMA/HvB/DI/UTFSM/2008 98

Operaci´ on Identidad Giro en v´ertice 4 en 1/3 Giro en v´ertice 4 en 2/3 Giro en arista 1 2 en 1/2

Ciclos (1)(2)(3)(4) (1 2 3)(4) (1 3 2)(4) (1 2)(3 4)

Tipo [14 ] [1 31 ] [1 31 ] [22 ]

Cuadro 6: Rotaciones de un tetraedro

99

Nº 1 4 4 3