Universidad de Valladolid

Facultad de Ciencias

Matemática discreta y otras

formas de conseguir tocar
una θ

Apuntes de la asignatura

Autor:
Álvaro Gobernado Garrido

Junio 2022
Cuando cuentes giros cuenta cuántos giros cuentas, porque si no
cuentas cuántos giros cuentas, nunca sabrás cuántos giros has
contado tú.
4
Índice general

I Combinatoria enumerativa. 7
1. Motivación. 9

2. Series de potencias. 11
2.1. La importancia del binomio de Newton. . . . . . . . . . 19
2.1.1. Calcular el inverso de una serie. . . . . . . . . . 20
2.2. Jugando con funciones generatrices. . . . . . . . . . . 21
2.3. Convergencia débil. . . . . . . . . . . . . . . . . . . . . 27
2.4. Recurrencias. . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.1. Recurrencias lineales. . . . . . . . . . . . . . . . 28
2.5. Funciones generatrices de dos variables. . . . . . . . . 32

3. Polinomios y permutaciones. 35
3.1. Polinomios indicadores de ciclos. . . . . . . . . . . . . 36
3.2. Acciones de grupo. . . . . . . . . . . . . . . . . . . . . . 38
3.3. Grupos de rotaciones de poliedros regulares. . . . . . 42
3.3.1. Orden de los grupos de movimiento. . . . . . . 43
3.3.2. Pero, ¿no hay más poliedros regulares? . . . . . 43
3.3.3. Clases enumerativas del grupo de rotaciones. . 45
3.4. Isometrı́as y el grupo puntual. . . . . . . . . . . . . . . 47
3.4.1. Isometrias en R2 . . . . . . . . . . . . . . . . . . . 48
3.4.2. Isometrı́as en R3 . . . . . . . . . . . . . . . . . . . 51

4. Teorı́a de Polya. 55
4.1. El teorema de Polya. . . . . . . . . . . . . . . . . . . . . 58

5. Politopos y series de Laurent. 67

5.1. Relaciones de orden. . . . . . . . . . . . . . . . . . . . . 68
5.1.1. Retı́culos. . . . . . . . . . . . . . . . . . . . . . . 70
5.2. Politopos. . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2.1. Cuerpo de fracciones. . . . . . . . . . . . . . . . 73

5
6 ÍNDICE GENERAL

5.2.2. Series de Laurent. . . . . . . . . . . . . . . . . . 74

5.3. Conos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.3.1. Conos regulares. . . . . . . . . . . . . . . . . . . 79
5.4. Teorema de Brion. . . . . . . . . . . . . . . . . . . . . . 83
5.4.1. Conos tangentes. . . . . . . . . . . . . . . . . . . 86
5.5. Expresar un cono como suma de conos regulares. . . 89
5.5.1. Fracciones continuas. . . . . . . . . . . . . . . . 89
5.5.2. Conos y fracciones continuas. . . . . . . . . . . 95

6. Principios básicos para contar. 97

6.1. Principio del palomar. . . . . . . . . . . . . . . . . . . . 97
6.2. Principio de inclusión-exclusión. . . . . . . . . . . . . 100
6.3. Números de Stirling. . . . . . . . . . . . . . . . . . . . . 105
6.3.1. Funciones generatrices de los números de Stir-
ling. . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.3.2. Relaciones de reciprocidad. . . . . . . . . . . . . 110

A. Cuentas 113

B. Algoritmos y su complejidad. 119

B.1. Algoritmos. . . . . . . . . . . . . . . . . . . . . . . . . . 119
B.2. Complejidad algorı́tmica. . . . . . . . . . . . . . . . . . 120
B.2.1. Orden de una función. . . . . . . . . . . . . . . 121
B.2.2. Escala de órdenes de complejidad. . . . . . . . 122
B.2.3. Estudio de la complejidad de algoritmos iterati-
vos. . . . . . . . . . . . . . . . . . . . . . . . . . . 122

C. Matemáticos 127

D. Recortables. 129
 Parte I

Combinatoria enumerativa.

7
Capı́tulo 1

Motivación.

La combinatoria enumerativa se encarga de contar. Puede ser

más o menos difı́cil, pero el objetivo es contar cuántos objetos hay
que cumplen ciertas propiedades. Trabaja pues, con conjuntos fini-
tos aunque perfectamente pueden estar contenidos en otros infini-
tos. Contar significa, por ejemplo, determinar de cuántas maneras
se pueden ordenar las cartas de una baraja, cuántas fichas de do-
minó se necesitan para cubrir un tablero m × n, o cómo emparejar
hombres y mujeres fieles dentro de un mismo pueblo.

A todas estas preguntas se les da respuesta en esta primera parte

de los apuntes. Como introducción, veamos dos ejemplos de lo que
nos vamos a encontrar.

 Ejemplo. Supongamos una reunión de alcohólicos anónimos.

Hoy hay 6 personas. Probar que hay 3 personas que son conoci-
dos mutuos o que 3 son desconocidos mutuos.

Solución. Sea X el conjunto de las 6 personas (anónimas). Fijado

un a ∈ X, podemos definir los conjuntos

A = {x ∈ X − {a} : x y a se conocen mutuamente}

B = {x ∈ X − {a} : x y a se desconocen mutuamente}

Con estos conjuntos tenemos

|X| = |{a}| + |A| + |B| ⇐⇒ 6 = 1 + |A| + |B| ⇐⇒ |A| + |B| = 5

pues A ∩ B = A ∩ {a} = B ∩ {a} = ∅. Como tanto |A| como |B| son

naturales, ha de ser |A| ≥ 3 o bien |B| ≥ 3.

9
10 CAPÍTULO 1. MOTIVACIÓN.

Supongamos |A| ≥ 3. Si en A existen 2 conocidos mutuos b

y c entonces {a, b, c} ⊆ X es un conjunto de tres conocidos
mutuos. En otro caso A contiene 3 desconocidos mutuos (al
menos).

Supongamos |B| ≥ 3. Si en B existen 2 desconocidos mutuos

b y c entonces {a, b, c} ⊆ X es un conjunto de tres desconoci-
dos mutuos. En otro caso A contiene 3 conocidos mutuos (al
menos).

OMC
 Ejemplo. Supongamos un pueblo donde todos sus habitantes
adultos están casados. Si H es el conjunto de hombres casados y
M el de las mujeres, aparece una biyección natural

h 7→ mujerDe(h)

con inversa m 7→ maridoDe(m). Además, resulta que algunos ha-

bitantes tienen relaciones extramatrimoniales, pero sólo con una
persona y siempre con alguien del pueblo (¿comparación con la ca-
rrera? Puede ser). Hay pues, otra biyección entre el conjunto de
hombres adúlteros y de mujeres adúlteras,

h 7→ señoritaDe(h)
m 7→ señoritoDe(m)

siendo inversas una de la otra. Habrá entonces el mismo número

de no adúlteros que de no adúlteras. Tenemos que ser capaces de
emparejarlos. ¿Cómo?
Solución. Fijemos un hombre h0 que es fiel a su mujer (el contra-
rio no tiene por qué ser cierto). Este hombre le pide a su mujer
que le acompañe al cine. Como la sinceridad es la base de la pare-
ja, mujerDe(h0 ) responderá con, o bien un sı́, significando que ella
también es fiel, o bien con la frase lo siento bb pero

señoritoDe(mujerDe(h0 ))

es mi amante. A lo mejor su mujer, mujerDe(señoritoDe(mujerDe(h0 ))),

está libre. Si mujerDe(h0 ) no es fiel, h0 irá a por la mujer del amante
de su mujer, y le hará la misma pregunta. Repitiendo este proceso,
todo hombre y mujer fiel terminarán emparejados. OMC
Capı́tulo 2

Series de potencias.

Tomemos una variable x.

Definición. Una serie (formal) de potencias de x sobre un anillo A

es una expresión de la forma

s = s(x) = a0 + a1 x + a2 x2 + · · · + an xn + · · ·

donde las sumas son formales, es decir, no nos preocupamos por si

s(x) converge o no, y ai ∈ A.

En realidad una serie es otra forma de almacenar la información

de una sucesión {an }∞
n=0 . La ventaja de utilizar series en vez de su-
cesiones es que podemos operar con ellas de manera más sencilla.
Además, como veremos más adelante, las series con coeficientes en
un anillo conmutativo A son a su vez otro anillo conmutativo.

Observación. El caso más frecuente es que los coeficientes sean

enteros, pues suelen representar el número de elementos que cum-
plen cierta propiedad.

Definición. Denotemos por A[[x]] al conjunto de todas las series con

coeficientes en el anillo conmutativo A. En este conjunto definimos
las operaciones
1. Suma (+) como

s1 + s2 = c 0 + c 1 x + c 2 x 2 + · · ·

donde, si s1 = a0 + a1 x + a2 x2 + · · · y s2 = b0 + b1 x + b2 x2 + · · ·
entonces ci = ai + bi .

11
12 CAPÍTULO 2. SERIES DE POTENCIAS.

2. Producto (·) como

s1 · s2 = c 0 + c 1 x + c 2 x 2 + · · ·

donde, si s1 = a0 + a1 x + a2 x2 + · · · y s2 = b0 + b1 x + b2 x2 + · · ·
entonces ci = a0 bi + a1 bi−1 + · · · + ai b0 .

Proposición. Si A es un anillo conmutativo, el conjunto A[[x]] junto

con las dos operaciones definidas anteriormente es un anillo con-
mutativo, donde s = 0 es el elemento neutro para la suma y s = 1 es
el elemento neutro para el producto.

(este tipo de proposiciones parecen inútiles porque nadie las de-

muestra, siempre son evidentes o un laborioso trabajo). Por eso mis-
mo vamos a probarlo nosotros. Al menos que lo veas hecho una vez
en tu vida.

Demostración. Sean s1 , s2 , s3 ∈ A[[x]], por ejemplo

s1 = a0 + a1 x + a2 x2 + · · ·
s2 = b 0 + b 1 x + b 2 x 2 + · · ·
s3 = c 0 + c 1 x + c 2 x 2 + · · ·

Evidentemente, las dos operaciones son cerradas, y nos queda com-

probar las propiedades que deberı́a cumplir A[[x]] para ser un anillo
conmutativo. Lo primero que vamos a probar es que las operaciones
(+) y (·) son conmutativas para simplificar el resto de propiedades.

1. La operación (+) es conmutativa. Tenemos que ver que s1 + s2 =

s2 + s1 . Esto es obvio pues

s1 + s2 = (a0 + ax + a2 x2 + · · · ) + (b0 + b1 x + b2 x2 + · · · )
= (a0 + b0 ) + (a1 + b1 )x + (a2 + b2 )x2 + · · ·
= (b0 + a0 ) + (b1 + a1 )x + (b2 + a2 )x2 + · · ·
= s2 + s1

2. La operación (·) es conmutativa. En este caso hay que probar

que s1 · s2 = s2 · s1 . Si llamamos t0 + t1 x + t2 x2 + · · · a la serie
resultante de multiplicar s1 · s2 y nos fijamos en un coeficiente
arbitrario k, entonces

tk = a0 bk + a1 bk−1 + · · · + ak b0
 13

Evidentemente en esta suma podemos conmutar cada produc-

to y suma,
tk = b0 ak + b1 ak−1 + · · · + bk a0
y este es justamente el k−ésimo elemento de la serie s2 · s1 .

3. La operación (+) es asociativa. Basta ver que (s1 + s2 ) + s3 =

s1 + (s2 + s3 ). Esto es sencillo pues el término k−ésimo de la
primera suma es (ak + bk ) + ck = ak + bk + ck y el de la segunda
es ak + (bk + ck ) = ak + bk + ck .

4. La operación (+) tiene un elemento neutro. Tomemos el elemen-

to 0 = 0 + 0x + 0x2 + · · · y veamos que es el neutro para la suma,
es decir, 0 + s1 = s1 ,

0 + s1 = (0 + 0x + 0x2 + · · · ) + (a0 + a1 x + a2 x2 + · · · )
= (0 + a0 ) + (0 + a1 )x + (0 + a2 )x2 + · · ·
= a0 + a1 x + a2 x2 + · · ·

5. Para cada s ∈ A[[x]] existe un elemento s̃ opuesto. Esto es, s+ s̃ =

0. Si tomamos s1 , la serie dada por

s̃ = −a0 − a1 x − a2 x2 − · · ·

cumple exactamente lo pedido. Diremos que s̃ es el opuesto de

s y escribimos s̃ = −s.

6. La operación (·) es asociativa. Como antes, tenemos que com-

probar que (s1 · s2 ) · s3 = s1 · (s2 · s3 ). Si t0 + t1 x + t2 x2 + · · · es la
serie resultante de realizar el primer producto, el coeficiente
k−ésimo será

tk = a0 bk (c0 + · · · ck ) + a1 bk−1 (c0 + · · · + ck ) + · · · + ak b0 (c0 + · · · + ck )

¿Esto es lo mismo que multiplicar el otro miembro? Tiene que

serlo. Si no te lo crees, pruébalo.

7. La operación (·) tiene elemento neutro. Tomemos 1 = 1 + 0x +

0x2 + · · · y veamos que es el elemento neutro. Otra vez, si t0 +
t1 x+t2 x2 +· · · es la serie resultante de multiplicar 1·s1 entonces

tk = a0 · 0 + a1 · 0 + · · · ak · 1 = ak

luego efectivamente es el elemento neutro.

14 CAPÍTULO 2. SERIES DE POTENCIAS.

8. La operación (·) es distributiva respecto de (+). Tenemos que

comprobar que s1 (s2 + s3 ) = s1 s2 + s1 s3 . Llamemos t = s2 + s3 =
t0 + t1 x + t2 x2 + · · · (es decir, tk = bk + ck ). Entonces

s1 (s2 + s3 ) = a0 (b0 + c0 ) + (a0 (b1 + c1 ) + a1 (b0 + c0 ))x

= a0 b0 + a0 c0 + (a0 b1 + a0 c1 + a1 b0 + a1 c0 )x + · · ·

Pongamos ahora s1 s2 = d0 +d1 x+· · · (es decir, dk = a0 bk +· · ·+ak b0 )

y s1 s3 = f0 + f1 x + · · · . Entonces

s1 s2 + s1 s3 = (d0 + f0 ) + (d1 + f1 )x + · · ·
= a0 b0 + a0 c0 + (a0 b1 + a1 b0 + a0 c1 + a1 c0 )x + · · ·
= s1 (s2 + s3 )

Al cumplirse todas estas propiedades entonces A[[x]] es un anillo

conmutativo. ¿Entiendes ahora por qué nadie quiere probar estas
cosas? OMC

Observación. Una serie s = a0 + a1 x + a2 x2 + · · · se dice constante si

a0 6= 0, ai = 0 si i > 0. En este caso escribimos s = a0 = a y multiplicar
una serie constante por otra cualquiera cualquiera se convierte en
multiplicar cada coeficiente de la segunda por la constante.

Observación. Dado que Z ⊆ Q ⊆ R ⊆ C, se conservan las conten-

ciones en los anillos de series,

Z[[x]] ⊆ Q[[x]] ⊆ R[[x]] ⊆ C[[x]]

Como A[[x]] es un anillo, no toda serie s ∈ A[[x]] tiene por qué

tener inverso para el producto (sino, serı́a un cuerpo). La siguiente
proposición nos da las condiciones bajo las cuales una serie s tiene
inversa.

Proposición. Consideramos A[[x]] y s ∈ A[[x]]. Entonces

1. Si A es Q, R, C entonces s es inversible si a0 6= 0.

2. Si A es Z entonces s es inversible si a0 = ±1.

3. En general, s es inversible si a0 es una unidad de A.

 15

Demostración. Probamos 3. Lo vamos a hacer dando una manera

constructiva de calcular s−1 . Dada s = a0 + a1 x + a2 x2 + · · · buscamos
s′ = b0 + b1 x + b2 x2 + · · · tal que ss′ = 1. Como a0 es unidad, existe b0
tal que a0 b0 = 1. Ahora, conocemos a0 , a1 y b0 luego calculamos b1 ,

a0 b1 + a1 b0 = 0 ⇐⇒ b1 = −a−1
0 (a1 b0 )

Para calcular b2 , conocemos a0 , a1 , a2 , b0 y b1 . Podemos despejar b2

y ası́ podemos ir siempre calculando b3 , b4 , ... Obtenemos ası́ s′ =
s−1 . OMC

Si s es una serie no nula, la podemos escribir como s = uxm

donde u = u0 + u1 x + · · · es una serie con u0 6= 0, y u es única. Si
s = am xm + am+1 xm+1 + · · · entonces s = (am + am+1 x + · · · )xm (si s tie-
ne a0 6= 0 entonces m = 0 y u = s). Esto nos da la siguiente definición.

Definición. En las condiciones anteriores, llamamos orden de s al

entero ord(s) = m. Si s = 0 entonces convenimos en que ord(s) =
−∞.

Proposición. Dadas s, t ∈ A[[x]] se cumple que

1. ord(s + t) ≥ mı́n(ord(s), ord(t))

2. ord(st) = ord(s) + ord(t)

3. ord(s) = 0 ⇐⇒ s es unidad en A[[x]]

 Ejemplo. Determinar el coeficiente de xk de la serie

(x3 + x4 + x5 + · · · )6

La manera torpe y tonta es multiplicar s = x3 + x4 + x5 + · · · seis

veces por sı́ misma. Busquemos por tanto otra solución. Notemos
lo siguiente: si s es una serie tal que ord(s) = m y escribimos s = uxm ,
entonces el coeficiente de xk en uxm es el mismo que el de xk−m en
u. Ası́, escribamos

x3 + x4 + x5 + · · · = x3 (1 + x + x2 + · · · )

y entonces

(x3 + x4 + x5 + · · · ) = [x3 (1 + x + x2 + · · · )]6 = x18 (1 + x + x2 + · · · )6

16 CAPÍTULO 2. SERIES DE POTENCIAS.

Usando la serie geométrica,

(x3 + x4 + x5 + · · · ) = [x3 (1 + x + x2 + · · · )]6

= x18 (1 + x + x2 + · · · )6
 6
18 1
=x
1−x
 
18 1
=x
(1 − x)6
X∞  
18 k+5 k
=x x
k=0
5

Haciendo uso de la nota, el coeficiente de xk en (x3 + x4 + x5 + · · · )6

es el mismo que el de xk−18 en
∞ 
X 
k+5
xk
k=0
5

que es exactamente
   
k − 18 + 5 k − 13
=
5 5

Supongamos s = a0 + a1 x + a2 x2 + · · · una serie de A[[x]] con a0 6= 0.

Dado n ∈ N y b una raı́z n−ésima de a0 , existe otra serie r en A[[x]]
del tipo r = b + b1 x + · · · tal que rn = s, que llamaremos raı́z n−ésima.
Para calcular b1 , b2 , ... lo hacemos con coeficientes indeterminados.

Definición. Si α ∈ C y k ∈ N, definimos el número combinatorio α

sobre k como  
α α(α − 1) · · · (α − k + 1)
=
k k!
Definición. Si α ∈ C y k ∈ N definimos
∞  
X      
α α k α α α 2
(1 + x) = x = + x+ x + ··· (2.1)
k=0
k 0 1 2

Observa que si α es natural, la fórmula anterior es el conocido bi-

nomio de Newton.
 17

Observación. La definición (2.1) se puede dar también cómo teore-

ma, en concreto el teorema binomal, que establece que para cuales-
quiera x, y ∈ R y n ∈ C entonces
X∞  
n n k n−k
(x + y) = x y
k=0
k
Una vez demostrado, se puede tomar como caso particular y = 1
para obtener (2.1).

Observación. Si α = −m con m ∈ N entonces

X∞  
−m 1 m+k−1 k
(1 + x) = = x (2.2)
(1 + x)m k=0
k
y en este caso el coeficiente
 
m+k−1
k
es también el número de monomios de grado k en m variables. Si
α = 1/m entonces
X∞  
1/m 1/m k
(1 + x) = x (2.3)
k=0
k
que calcula la raı́z m−ésima con b = 1 de 1 + x.

 Ejemplo. La serie s = 2x + 3x2 es un elemento de Z[[x]] donde no

es inversible (a0 = 0). Sin embargo,
2x + 3x2 = 2(x + 3/2x2 ) = 2x(1 + 3/2x) ∈ Q[[x]]
y esta última sı́ es inversible en Q[[x]]. Pero son la misma serie.

Definición. Sea s = a0 + a1 x + a2 x2 + · · · una serie en A[[x]]. Una

sustitución consiste en tomar una serie auxiliar z = aj xj + aj+1 xj+1 +
· · · a partir del j−ésimo término de s, tal que ord(z) ≥ 1 y escribir
s = a0 + · · · + aj−1 xj−1 + z
y operar con esta nueva serie. Suele ser útil si a0 = 1 tomar z =
a1 x + a2 x2 + · · ·

 Ejemplo. Dada s = 1+2x+3x2 +· · · , podemos calcular s−1 mediante

el método de coeficientes indeterminados (s−1 existe pues a0 = 1)
buscando s′ = b0 + b1 x + b2 x2 + · · · Entonces
18 CAPÍTULO 2. SERIES DE POTENCIAS.

1. 1b0 = 1 ⇐⇒ b0 = 1
2. 1b1 + 2 · 1 = 0 ⇐⇒ b1 = −2
3. 1b2 + 2(−2) + 3 · 1 = 0 ⇐⇒ b2 = 1
y ası́ obtenemos que s−1 = 1−2x+x2 +· · · Otra forma de hallar s−1 es
haciendo una sustitución z = 2x+3x2 (observa ord(z) = 1). Entonces
s = 1 + z y haciendo uso de (2.2) para m = 1 tenemos que
1
(1 + z)−1 = = 1 − z + z2 − z3 + · · ·
1+z
Entonces s−1 = 1−(2x+3x2 )+(2x+3x2 )2 −(2x+3x2 )3 +· · · Observa que
por el método de coeficientes indeterminados únicamente podemos
calcular tantos bi como ai tengamos de s. Sin embargo, haciendo
la sustitución z = 2x + 3x2 podemos calcular tantos términos como
ganas de multiplicar tengamos,
s−1 = 1 − 2x + x2 + 4x3 − 27x4 − 54x5 − 27x6 + · · ·
√
Supongamos ahora que queremos calcular s. Por coeficientes in-
determinados es posible, pero tomando en (2.3) m = 2 resulta
1 1 1
(1 + z)1/2 = 1 + z − z 2 + z 3 + · · ·
2 8 16
√
luego s = 1 + 12 (2x + 3x2 ) − 81 (2x + 3x2 )2 + 1
16
(2x + 3x2 )3 + · · ·

Lema. Si k ∈ N entonces
 
−1
= (−1)k
k

Demostración. Por definición,

 
−1 (−1)(−2) · · · (−1 − k + 1) (−1)(−2) · · · (−k) (−1)(−2) · · · (−k)
= = =
k k! k! 1 · 2···k
Si k es par, el numerador tiene un número par de factores y por tanto
se pueden emparejar de forma que se anulan los signos negativos.
Si k es impar, queda uno sin emparejar, luego
  
−1 1 si k par
=
k −1 si k impar
OMC
2.1. LA IMPORTANCIA DEL BINOMIO DE NEWTON. 19

Observación. En (2.1) si α ∈ N aparece el conocido binomio de

Newton. Sin embargo, el binomio de Newton se representa como
una serie finita
Xm   X∞  
m m k m m k
(1 + x) = x y no (1 + x) x
k=0
k k=0
k
m


¿Por qué? Observa que el valor k contiene en el numerador al fac-
tor 0 una vez que m < k, luego todos los términos a partir de ahı́
resultan nulos.

Lema. Si m, k ∈ N entonces
   
−m m+k−1
=
k k

Demostración. Por definición,

 
−m (−m)(−m − 1) · · · (−m − k + 1) m(m + 1) · · · (m + k − 1)
= = (−1)k
k k! k!
Cambiando el orden de los factores del numerador,
 
k (m + k − 1) · · · (m + 1)(m) k m+k−1
(−1) = (−1)
k! k
OMC

2.1. La importancia del binomio de New-

ton.
Volvamos una vez más sobre (2.1). Si consideramos la serie
∞
X
2 3
1 + x + x + x + ··· = xk
k=0

conocida como la serie geométrica, por cálculo sabemos que con-

verge si |x| ≤ 1. En este caso su suma es exactamente
∞
X 1
xk = = (1 − x)−1
k=0
1−x
Si x = −z entonces
1
= 1 − z + z2 − z3 + · · · (2.4)
1+z
20 CAPÍTULO 2. SERIES DE POTENCIAS.

2.1.1. Calcular el inverso de una serie.

Dada s = b0 + b1 x + b2 x2 + · · · , su inversa es
1 1 1 1 1
=  = =
b0 + b1 x + · · · b0 1 + b1
x + b2 2
x + ··· b0 (1 + z) b0 1 + z
b0 b0

donde se ha hecho la sustitución z = bb10 x + bb02 x2 + · · · y resulta que

basta reemplazar en (2.4) z por su sustitución. Si en (2.1) tomamos
α = −m con m ∈ N, entonces obtenemos una forma de calcular
el inverso de (1 + x)m . La relación (2.2) nos calcula los coeficientes
necesarios,
X ∞   ∞  
1 −m k X m + k − 1 k
= x = x
(1 + x)m k=0
k k=0
k

(observa que si m = 1 obtenemos (2.4)).

Proposición. El número combinatorio

 
m+k−1
(2.5)
k
representa el número de monomios de grado k en m variables.
Demostración. Sean x1 , ..., xm las m variables, e i1 , ..., im sus respec-
tivos grados con i1 + · · · + im = k. Es decir, buscamos las posibles
combinaciones de
xi11 xi22 · · · ximm
donde i1 , ..., im son conocidos. Una posible representación para los
monomios es escribir tantos puntos • como el valor ik correspon-
diente y una barra | para indicar que cambiamos de variable. Por
ejemplo, el monomio x3 y 2 lo representamos como
• • •| • •
Si una variable no aparece, no se escribe ningún punto y escribimos
dos barras seguidas. Nuestro problema entonces es determinar las
posibles ordenaciones de k + m − 1 elementos (k puntos y m − 1
barras). Este número es
   
k+m−1 k+m−1
=
m−1 k
OMC
2.2. JUGANDO CON FUNCIONES GENERATRICES. 21

 Ejemplo. Para m = 2 y k = 3 tenemos

x3 , xy 2 , x2 y, y 3

que de acuerdo con la representación de puntos y barras es

• • •|, •| • •, • • |•, | • ••

2.2. Jugando con funciones generatrices.

Supongamos que buscamos la función generatriz de la sucesión
{an }∞
n=0 dada por an = n + 1, es decir, la sucesión de los números na-
turales 1, 2, 3, 4, ... Dependiendo de lo listos que seamos, podemos
deducir de (2.2) que tomando m = 2 tenemos
1
2
= (1 − x)−2 = 1 + 2x + 3x2 + · · ·
(1 − x)
Pero no hace falta ir de guays. Tomemos la progresión geométrica
1
= 1 + x + x2 + x3 + · · ·
1−x
Si la derivamos,
 
d 1 d 1
= (1+x+x2 +x3 +· · · ) ⇐⇒ 2
= 0+1+2x+3x2 +· · ·
dx 1 − x dx (1 − x)
1
Si multiplicamos por 2, resulta que obtenemos la función
(1 − x)2
generatriz de los números pares,
2
= 2 + 4x + 6x2 + · · ·
(1 − x)2
La sucesión {an }∞
n=0 dada por

1 si n impar o 0
an
0 si n par

tiene función generatriz

1
g(x) =
1 − x2
22 CAPÍTULO 2. SERIES DE POTENCIAS.

¿Por qué? Si, de nuevo, volvemos sobre la progresión geométrica

pero sustituimos x por x2 ,
1
2
= 1 + (x2 ) + (x2 )2 + (x2 )3 + · · · = 1 + x2 + x4 + x6 + · · ·
1 − (x )
 Ejemplo. Un caso más difı́cil: ¿cuál es la función generatriz de
la sucesión 1, 0, 2, 0, 3, 0, 4, 0, ...? Pensemos. Sea g la función
generatriz buscada,
∞
X
g(x) = an xn
n=0
= 1 + 0x + 2x2 + 0x3 + 3x4 + 0x5 + 4x6 + · · ·
= 1 + 2x2 + 3x4 + 4x6 + · · ·
La sucesión de coeficientes son los números naturales y la de los
coeficientes son los números pares. Parece lógico que necesitaremos
sus funciones generatrices,
1
= 1 + 2x + 3x2 + 4x3 + · · ·
(1 − x)2
1
= 1 + x2 + x4 + x6 + · · ·
1 − x2
Qué tal si juntamos ambas sustituyendo en la primera x por x2 ,
1
g(x) = = 1 + 2x2 + 3x4 + 4x6 + · · ·
(1 − x2 )2

A estas alturas, deberı́a ser capaz de calcular la función genera-

triz de los números impares. Partiendo de
∞
X
g(x) = an xn = 1 + 3x + 5x2 + 7x3 + · · ·
n=0

podemos restar 2 + 4x + 6x2 + 8x3 + · · · menos 1 + x + x2 + x3 + · · · para

obtener
2 + 4x + 6x2 + 8x3 + · · ·
− 1 + x + x2 + x3 + · · ·
1 + 3x + 5x2 + 7x3 + · · ·
resultando en la serie deseada. Si restamos las funciones genera-
trices correspondientes,
2 1 2 − (1 − x) 1+x
g(x) = 2
− = 2
=
(1 − x) 1−x (1 − x) (1 − x)2
2.2. JUGANDO CON FUNCIONES GENERATRICES. 23

Puedes utilizar Matlab para comprobar que los cálculos son correc-
tos hallando el desarrollo de Taylor de g en torno a 0.

Veamos a continuación algunas propiedades de las funciones

generatrices. Supongamos f y g las funciones generatrices de las
sucesiones {an }∞ ∞
n=0 y {bn }n=0 respectivamente. Entonces

1. Dados cualesquiera α, β ∈ C, la función generatriz de {cn }∞

n=0
con cn = αan + βbn es

h(x) = αf (x) + βg(x)

2. La función generatriz de {cn }∞

n=0 con

cn = a0 bn + a1 bn−1 + · · · an b0

es f (x)g(x).

3. La función generatriz de {cn }∞

n=0 con

0 si 0 ≤ n ≤ m − 1
cn =
an−m si n ≥ m

es xm f (x). Esto es, desplazar el inicio de la sucesión an de a0 a

am .

4. La función generatriz de {cn }∞

n=0 con

cn = k n an

es f (kx).

5. La función generatriz de {cn }∞

n=0 con

c0 = a0 , cn = an − an−1 si n ≥ 1

es (1 − x)f (x).

6. La función generatriz de {cn }∞

n=0 con

cn = a0 + a1 · · · + an

es (1 − x)−1 f (x).
24 CAPÍTULO 2. SERIES DE POTENCIAS.

7. La función generatriz de {cn }∞

n=0 con

cn = (n + 1)an+1

es f ′ (x). De aquı́, si cn = nan su función generatriz es xf (x).

8. La función generatriz de {cn }∞

n=0 con

an−1
c0 = 0, cn = si n ≥ 1
n
es Z x
f (t)dt
0

 Ejemplo. ¿Cuál es la función generatriz de la sucesión

cn = 3n + 5

para cada n ≥ 0? Según la propiedad 1, podemos escribir

cn = 3an + 5bn

donde an = n y bn = 1 para todo n ≥ 0. Conocemos las funciones

generatrices de an y bn , respectivamente
x 1
f (x) = 2
y g(x) =
(1 − x) 1−x

(observa que hemos aplicado la propiedad 3 a la función generatriz

de 1 + 2x + 3x3 + · · · para que empiece en 0). Entonces la función
generatriz de {cn }∞
n=0 es
   
x 1
h(x) = 2f (x) + 5g(x) = 3 +5
(1 − x)2 1−x

 Ejemplo. Si la sucesión 1, 2, 3, 4,... tiene función generatriz

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

entonces las sucesiones 0, 1, 2, 3, 4,... y 0, 0, 1, 2, 3, 4,... tienen

funciones generatrices respectivas

x x2
f1 (x) = y f 2 (x) =
(1 − x)2 (1 − x)2
2.2. JUGANDO CON FUNCIONES GENERATRICES. 25

 Ejemplo. Probemos la propiedad 8. Sea {an }∞

n=0 una sucesión con
función generatriz f , es decir,
∞
X
f (x) = an xn = a0 + a1 x + a2 x2 + · · ·
n=0

Si integramos ambos miembros respecto de x,

Z Z
f (x)dx = (a0 + a1 x + a2 x2 + · · · )dx
1 1 1
= a0 x + a1 x2 + a2 x3 + · · · + an−1 + · · ·
2 3 n
que es exactamente la sucesión {cn }∞
n=0 dada por

an−1
c0 = 0, cn = si n ≥ 1
n

Calcule la función generatriz de cn = n2 si n ≥ 0 (Indicación: escriba

cn = nan para una sucesión an apropiada y aplique la propiedad 7).
Espero que haya obtenido
x(1 + x)
g(x) =
(1 − x)3
El siguiente ejemplo nos muestra cómo utilizar series y funciones
generatrices para calcular diferentes tipos de combinaciones de un
conjunto.

Sea S = {a, b, c} un conjunto con 3 elementos. Deseamos saber el

número total de formas en las que podemos elegir de 1 a 3 elemen-
tos de S.

Para cada elemento de S escribamos la función generatriz que nos

cuenta cuántas veces aparece cada elemento de S en él,

ga (x) = 1 + ax, gb (x) = 1 + bx, gc (x) = 1 + cx

entendiendo
1 = (ax)0 ≡ no se elige el elemento a
ax = (ax)1 ≡ se elige a una vez
k k k
a x = (ax) ≡ se elige a k veces
26 CAPÍTULO 2. SERIES DE POTENCIAS.

El producto de las tres funciones nos da los coeficientes que nece-

sitamos,
ga (x)gb (x)gc (x) = (1 + ax)(1 + bx)(1 + cx)
= 1 + (a + b + c)x + (ab + bc + ca)x2 + (abc)x3
Esto se lee de la siguiente manera: el coeficiente de xk nos da las
posibles combinaciones de tomar k elementos de S (evidentemente
1 = x0 indica que hay una única posibilidad de no tomar elementos;
y siempre 0 ≤ k ≤ |S|). Si no nos interesa conocer las combinacio-
nes y únicamente queremos el número de posibles combinaciones,
basta tomar a = b = c = 1,
ga (1)gb (1)gc (1) = 1 + 3x + 3x2 + x3
En general, si S = {s1 , ..., sn } con todos distintos, para determinar
las posibles maneras de elegir k elementos de S, basta hallar el
coeficiente de xk del producto gs1 (x) · · · gsn (x). En efecto, si ak es el
número de formas de elegir k elementos de S,
gsi (x) = (1 + x)
(tomamos s1 = s2 = · · · = sn = 1 pues sólo nos interesa el número) y
entonces n n
Y Y
gsi (x) = (1 + x) = (1 + x)n
i=1 i=1
y utilizando (2.1) tenemos que
∞
X ∞  
X
k n
ak x = xk
k=0 k=0
k

Los coeficientes buscados ak son

 
n
ak = si 0 ≤ k ≤ n
k
y 0 si k > n.

 Ejemplo. Sea el conjunto S = {a, a, b}. ¿Cuáles son las distintas

formas de elegir elementos de S? En este caso las funciones gene-
ratrices son
ga (x) = 1 + x + x2 y gb (x) = 1 + x
Multiplicando, ga (x)gb (x) = 1 + 2x + 2x2 + x3 . Ası́, hay dos formas de
elegir un objeto, 2 formas de elegir dos objetos y 1 forma de elegir
todos los objetos.
2.3. CONVERGENCIA DÉBIL. 27

2.3. Convergencia débil.

Supongamos A[[x]] el anillo de series de potencias y {sn }∞
n=0 una
sucesión de series en A[[x]], digamos

s0 = a00 + a01 x + a02 x2 + · · ·

..
.
sn = an0 + an1 x + an2 x2 + · · ·
..
.

Definición. Con la notación anterior, decimos que la sucesión {sn }∞

n=0
converge débilmente a la sucesión

ℓ = ℓ 0 + ℓ 1 x + · · · + ℓ n xn + · · ·

si cada sucesión de coeficientes {ank }∞

n=0 converge hacia ℓk , es decir,

n→∞
a00 , a10 , ..., an0 , ... −→ ℓ0
..
.
n→∞
a0n , a1n , ..., ann , ... −→ ℓn
..
.

A la sucesión ℓ = ℓ0 + ℓ1 x + · · · + ℓn xn + · · · la llamamos lı́mite débil de

{sn }∞
n=0 .

 Ejemplo. La sucesión

1, 1 + x, 1 + x + x2 , ..., 1 + x + · · · + xn , ...

converge débilmente a ℓ = 1 + x + x2 + · · · + xn + · · ·

Definición. Si {an }∞
n=0 es una sucesión de elementos de A, su fun-
ción generatriz asociada es

g = g(x) = a0 + a1 x + a2 x2 + · · · + an xn + · · ·

Pueden darse dos casos para g,

1. g es realmente una función g : C −→ C. En este caso es posible

determinar g(x) = 0.
 28 CAPÍTULO 2. SERIES DE POTENCIAS.

2. g es el desarrollo en serie de Taylor de una función desconoci-

da o no elemental. En este caso g(x) = 0 puede ser imposible
de calcular.

En la práctica, una función generatriz g será una función que al

desarrollarse en serie de potencias xk tiene como coeficientes exac-
tamente los términos de la sucesión.

Definición. Sea {an }∞n=0 una sucesión de elementos de A. Una fórmu-

la (o función) de recurrencia es una función ρ que determina an en
función de los n − 1 términos anteriores,
an = ρ(a0 , ..., an−1 )
Si ρ hace uso de los h > 0 elementos previos a an (an−1 , an−2 , ..., an−h )
entonces ρ es de paso h. Si h = n entonces el paso es infinito.

El tı́pico ejemplo de función recursiva es cómo calcular el factorial

de un número. La definición de n! = n(n − 1)(n − 2) · · · 1 se puede
convertir en 
1 si n = 0
n! =
n · (n − 1)! si n > 0
Una implementación en C podrı́a ser
1 int factorial (n) {
2 i f ( n==0) return 1;
3 else return n∗ f a c t o r i a l ( n−1) ;
4 }

2.4. Recurrencias.
2.4.1. Recurrencias lineales.
Recuerda que una combinación de los elementos a1 , ..., an es li-
neal si se relacionan entre ellos mediante sumas o/y producto por
escalares.

Definición. Sea {an }∞n=0 una sucesión de elementos de A. Una rela-

ción de recurrencia lineal es aquella donde ρ es lineal,
an = ρ(a0 , ..., an−1 ) = c1 an−1 + c2 an−2 + · · · + ch an−h , ch 6= 0
2.4. RECURRENCIAS. 29

para todo n ≥ h. Los h primeros términos reciben el nombre de con-

diciones iniciales. El valor de h es el orden de la relación.

Observación. Una sucesión {an }∞ n=0 es eventualemnte por recurren-

cia lineal si quizá los s primeros términos no cumplen la relación,
pero para n ≥ h + s entonces

an = c1 an−1 + c2 an−2 + · · · + ch an−h

 Ejemplo. La sucesión de Fibonacci es una relación lineal de orden

2,
an = an−1 + an−2 , n ≥ 2
con condiciones iniciales a0 = a1 = 1. Los primeros términos son 1,
1, 2, 3, 5, 8, 13, 21,... ¿Podemos dar una función generatriz para
esta serie?

Proposición. Sea g = a0 + a1 x + · · · + an xn + · · · la función generatriz

de la sucesión {an }∞
n=0 . Entonces

1. g es de la forma P (x)/Q(x) con grado(P ) < grado(Q) si, y sólo

si, {an }∞
n=0 es por recurrencia lineal.

2. g es de la forma R(x) + P (x)/Q(x) con grado(P ) < grado(Q) si,

y sólo si, {an }∞
n=0 es eventualmente por recurrencia lineal.

Demostración. 1. =⇒ ) Supongamos que {an }∞

n=0 es por recurren-
cia lineal, es decir,

an = ρ(a0 , ..., an−1 ) = c1 an−1 + c2 an−2 + · · · + ch an−h , ch 6= 0

Multiplicando ambos miembros por xn ,

an xn = (c1 an−1 + c2 an−2 + · · · + ch an−h )xn

Si ahora sumamos a partir del término desde el cual la recu-

rrencia es válida (es decir, desde n = h),
∞
X ∞
X ∞
X
an xn = c1 x an−1 xn−1 + · · · + ch xh an−h xn−h
n=h n=h n=h
30 CAPÍTULO 2. SERIES DE POTENCIAS.

hemos conseguido reproducir casi la función generatriz g. Nos

falta que empiece por n = 0. Podemos escribir la suma como

g − a0 − a1 x − · · · − ah−1 xh−1 = c1 x(g − a0 − a1 x − · · · − ah−2 xh−2 )

+ c2 x2 (g − a0 − a1 x − · · · − ah−3 xh−3 )
..
.
+ ch−1 xh−1 (g − a0 )
+ ch xh g

y esto es una expresión de una recurrencia lineal. Agrupamos

en un lado de la igualdad todos los miembros con g,

g(1 − c1 x − c2 x2 − · · · − ch xh ) = a0 + a1 x + · · · + ah−1 xh−1

− c1 x(a0 + a1 x + · · · + ah−2 xh−2 )
..
.
− ch−1 a0 xh−1

Si bautizamos Q(x) = 1 − c1 x − c2 x2 − · · · − ch xh y P (x) al miembro

derecho de la igualdad, tenemos

P (x)
g(x)Q(x) = P (x) ⇐⇒ g(x) =
Q(x)

Como todos los sumandos de P tienen grado estrictamente

menor que h, grado(P ) < h = grado(Q).
⇐=) Si g(x) = P (x)/Q(x) en las condiciones del enunciado, to-
memos P de antes y escribámoslo en potencias de xk crecien-
tes. Con un poco de cuidado,

P (x) = a0 + (a1 − c1 a0 )x + · · · + (ah−1 − c1 ah−2 − · · · − ch−1 a0 )xh−1

Renombrando b0 = a0 , b1 = a1 −c1 a0 ,... tenemos que P ∈ (A[x])h−1 .

El sistema

b0 = a0
b1 = −c1 a0 + a1
b2 = −c2 a0 − c1 a1 + a2 (2.6)
..
.
bh−1 = −ch−1 a0 − ch−2 a1 − · · · + ah−1
2.4. RECURRENCIAS. 31

considerando los aj como incógnitas tiene solución única. ¿Por

qué? Tomemos la aplicación

△ : Ah −→ (A[x])h−1
(a0 , ..., ah−1 ) 7→ b0 + b1 x + · · · bh−1 xh−1

que es lineal, y en la base canónica de (A[x])h−1 tiene matriz

 
1 0 ··· 0 0
x 1 ··· 0 0
 
 .. 
A =  ... .. . .
. .
..
. .
 
x x ··· 1 0
x x ··· x 1

que es triangular y por tanto invertible, es decir, el sistema

(2.6) tiene solución única para los aj . Estos términos son exac-
tamente las condiciones iniciales de la recurrencia.

2. Basta adaptar un poco la demostración anterior. Si grado(P ) >

grado(Q) podemos escribir g como

P (x) Pe(x) R(x)Q(x) + Pe(x)

g= = R(x) + =
Q(x) Q(x) Q(x)

Los términos de R son exactamente los s términos sueltos que

no siguen la recurrencia lineal.
OMC

Observación. La primera parte de la demostración nos da una for-

ma práctica de calcular la función generatriz de una sucesión: mul-
tiplicamos por xn la recurrencia, sumamos, y manipulamos la ex-
presión para hallar los primeros coeficientes. En los anexos hay un
par de ejemplos.

Corolario. En las condiciones anteriores, la aplicación

⊲ : Cs+h −→ (C[x])s × (C[x])h

(a0 , ..., ah+s−1 ) 7→ (R(x), Q(x))

es lineal y biyectiva, es decir, es un isomorfismo entre ambos espa-

cios vectoriales.
32 CAPÍTULO 2. SERIES DE POTENCIAS.

2.5. Funciones generatrices de dos varia-

bles.
En la definición del número combinatorio α sobre k, el elemento
α puede ser un elemento de cualquier anillo A conmutativo y con
unidad, y tal que Q ⊆ A. Ası́, podemos tomar A = Q[x, t] el anillo de
polinomios con coeficientes en Q en las variables x y t.

Si tomamos α = −t tenemos
 
−t −t(−t − 1) · · · (−t − m + 1) t(t + 1) · · · (t + m − 1)
= = (−1)m
m m! m!
(2.7)
Ahora, en (2.1) tomando otra vez α = −t se tiene
∞ 
X  X∞
−t −t t(t + 1) · · · (t + m − 1) m
(1 − x) = xm = x (2.8)
m=0
m m=0
m!

Examinemos (2.7). Por un lado, el término de la derecha es una se-

rie de potencias en las variables x, t; que converge débilmente por-
que las variables x, t están separadas. El término de la izquierda se
puede escribir como

(1 − x)−t = exp(− log(1 − x)t)

que se puede considerar como una función f (x, t) de clase C ∞ . En-

tonces f es igual a su desarrollo en serie de Taylor en un entorno
de x0 = (0, 0).

El alumno que superó satisfactoriamente Cálculo Infinitesimal re-

cordará que
1 1
log(1 − x) = x + x2 + x3 + · · ·
2 3
serie de orden 1, y por lo tanto es legal tomar
 
1 2 1 3
z = x + x + x + ··· t
2 3

y hacer la sustitución z = x en la expresión

1 2 1 3
ex = 1 + x + x + x + ··· (2.9)
2! 3!
2.5. FUNCIONES GENERATRICES DE DOS VARIABLES. 33

Otra sustitución posible es tomar

 
1 2 1 3
z = x + x + x + ···
2! 3

y hacer z = x en (2.9). Las dos expresiones resultantes tienen un

alto valor combinatorio que veremos en un capı́tulo posterior.
34 CAPÍTULO 2. SERIES DE POTENCIAS.
Capı́tulo 3

Polinomios y permutaciones.

Tomemos x1 , ..., xn n variables. Escribimos x = (x1 , ..., xn ) por pere-

za. A veces, en un ataque de pereza máxima, incluso escribiremos
xi para escribir xi11 · · · xinn

Definición. Un monomio en las variables x1 , ..., xn es una expresión

de la forma
M (x) = M (x1 , ..., xn ) = xi11 · · · xinn = xi
donde cada ik ∈ N es el grado de la variable xi .

Observación. Cuidado con el concepto de grado. Van a aparecer

muchos tipos de grado que deberán distinguirse según el contexto.

Supongamos que, por alguna razón que de momento desconoce-

mos, nos gustarı́a dar más importancia a una variable que a otra
dentro del monomio M . Entonces asignamos a cada variable xi un
peso pi (entendiendo que a mayor peso mayor importancia). Estos
pesos no aparecen reflejados en el polinomio, los determinamos
aparte.

Definición. Si M (x) es un monomio en x = x1 , ..., xn , llamamos gra-

do usual o simplemente grado a
gradou (M ) = grado(M ) = i1 + · · · + in
Definición. Si M (x) = xi11 · · · xinn es un monomio en las variables
x1 , ..., xn y suponemos que hemos fijado pesos p1 , ..., pn para x1 , ..., xn
respectivamente, llamamos peso total o grado pesado de M a
gradop (M ) = i1 p1 + · · · + in pn

35
36 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.

 Ejemplo. Tomemos un monomio sencillito, M (x, y) = x5 y 3 . El gra-

do de M es grado(M ) = 5 + 3 = 8. Si ahora damos pesos p1 = 3 a x y
p2 = 2 a y, tenemos que el grado pesado de M es

gradop (M ) = 3 · 5 + 2 · 3 = 15 + 6 = 21

Observa que si p1 = p2 = · · · = pn = 1 entonces gradop = gradou .

Definición. Llamamos polinomio en las variables x1 , ..., xn a una

combinación lineal finita de monomios M (x),

P (x) = A1 M1 (x) + · · · + Ak Mk (x)

Los coeficientes del polinomio son los valores A1 , ..., Ak que pertene-
cen a un anillo conmutativo.

Observación. Denotamos por A[x1 , ..., xn ] al conjunto de polinomios

en las variables x1 , ..., xn con coeficientes en A. Si la suma de mo-
nomios es infinita, entonces hablamos de series en las variables
x1 , ..., xn y escribimos A[[x1 , ..., xn ]].

3.1. Polinomios indicadores de ciclos.

Situémonos en el grupo de permutaciones de longitud n ∈ N (re-
cordemos que cualquier grupo finito G es isomorfo a un grupo de
permutaciones), que denotamos Sn . Si σ ∈ Sn es una permutación,
la podemos descomponer de manera única en producto de ciclos
disjuntos (el grupo Sn es efectivamente un grupo bajo la operación
de composición ◦ pero como siempre, la operación del grupo la re-
presentamos por ·). Por ejemplo, si σ = (1 4 3)(2 3)(2 4) ∈ S4 , se
descompone en σ = (1 4)(2 3).

Definición. Tomemos σ ∈ Sn y su descomposición en ciclos disjun-

tos. Si ij es el número de ciclos de longitud j que aparecen en la
descomposición de σ, llamamos monomio indicador de ciclos de σ a

Mσ (x) = xi11 · · · xinn

Observación. Si σ ∈ Sn se descompone en ciclos disjuntos, no tie-

nen por qué aparecer n ciclos. Los números que quedan fijos no
se escriben y se entienden como ciclos de longitud uno. Por ejem-
plo, σ = (1 4)(2 3) ∈ S5 deja fijo al número 5 (se podrı́a escribir
3.1. POLINOMIOS INDICADORES DE CICLOS. 37

σ = (1 4)(2 3)(5) pero es tonterı́a). Entonces el monomio indicador

de ciclos de σ es
Mσ (x) = x1 x22
Si tomamos la misma σ pero en S4 entonces

M (x) = x22

Observación. Si a M (x) = xi11 · · · xinn le asignamos peso j a cada xj

entonces gradop (M ) = n pues

i1 + 2i2 + · · · + nin = n

¿Pero qué lı́o de n hay aquı́? Para que i1 + 2i2 + · · · + nin = n tiene
que pasar que si aparece la variable xn en el monomio, el resto no
aparezcan (si hubiera otra xj el peso serı́a j + n 6= n). En el momento
en que parece xn significa que un ciclo tiene longitud n, es decir, no
tiene ningún punto fijo. Evidentemente, si σ ∈ Sn tiene un ciclo de
longitud n, sólo puede tener ese ciclo, y sólo puede tener un único
ciclo de longitud n. En conclusión, si aparece xn tiene que ser con
exponente in = 1.

Definición. Sea S un conjunto finito cualquiera y ρ : S −→ Sn una

aplicación arbitraria (no tiene por qué ser inyectiva o sobreyectiva
en general). Llamamos polinomio indicador de ciclos asociado a ρ al
polinomio dado por
!
1 X
Pρ (x) = Mρ(g) (x) (3.1)
|S| g∈S

Observación. El polinomio Pρ es un polinomio en Q[x1 , ..., xn ] con

grado pesado igual a n si pj = j.

Si G es un grupo con operación (·), podemos definir una relación

de equivalencia R0 que llamamos de conjugación dada por

gR0 g̃ ⇐⇒ ∃h ∈ G tal que g̃ = h−1 · g · h

Esta relación nos crea una partición de G en clases de equivalencia

disjuntas.

Proposición. En Sn , dos permutaciones son conjugadas si, y sólo

si, tienen la misma estructura en ciclos.
38 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.

Demostración. Observemos cómo actúa σρσ −1 sobre el entero σ(i):

σρσ −1 (σ(i)) = σ(ρ(i))

En otras palabras, σρσ −1 envı́a σ(i) a σ(ρ(i)): en la descomposición

en ciclos de σρσ −1 , σ(i) está a la izquierda de σ(ρ(i)), mientras que en
la descomposición de cicls de ρ, i está a a la izquierda de ρ(i). OMC
Corolario. En el grupo Sn hay tantas clases de conjugación como
monomios de grado pesado n existen (con el peso pj = j).
Demostración. Dos permutaciones son conjugadas si se descompo-
nen de la misma manera en ciclos, es decir, ambos tienen el mismo
monomio indicador. Es simplemente cambiar la etiqueta de los mis-
mos elementos. OMC
 Ejemplo. En S6 las permutaciones σ = (2 3)(5 6) y τ = (1 4)(2 5) son
conjugadas, pues ambas tienen como monomio indicador M (x) =
x21 x22 .

Si en la definición anterior tomamos como S un grupo finito G, y

pedimos que ρ : G −→ Sn sea un homomorfismo de grupos, entonces
g es conjugado de g̃ si, y sólo si, ρ(g) y ρ(g̃) son conjugados. Entonces
Mρ(g) = Mρ(g̃) . De aquı́ deducimos que en (3.1) basta calcular Mρ(g)
para un g en cada clase de conjugación (y no para todo g ∈ G como
se pide en la definición).

3.2. Acciones de grupo.

Definición. Sea G un grupo finito y X = {1, ..., n} un conjunto finito.
Decimos que una aplicación T : G × X −→ X es una acción de G
sobre X si cumple
1. T (gg̃, x) = T (g, T (g̃, x)) si g, g̃ ∈ G, x ∈ X.

2. T (e, x) = x si e es el neutro de G y x ∈ X.
Las dos condiciones anteriores equivalen a que, para cada elemento
g de G, la aplicación Tg = T (g, −) sea una aplicación biyectiva de X
en X, luego una acción se puede entender como un homomorfismo
entre G y Sn ,
T : G −→ Sn
g 7→ Tg
3.2. ACCIONES DE GRUPO. 39

Ejemplo. Tomemos el grupo Z/(3) = {0, 1, 2} y el conjunto X = C.

Este grupo actúa sobre C como

1. T (0, z) = z.

2. T (1, z) = ωz

3. T (2, z) = ω 2 z

donde ω es una raı́z cúbica de la unidad distinta de 1 y z ∈ C.

Ejemplo. Las acciones de grupo son muy frecuentes en geometrı́a.

Si consideramos P un poliedro (cuerpo geométrico con caras planas
y cerrado) y denotamos por c(P), a(P) y v(P) al conjunto de caras,
aristas y vértices de P (abusando del lenguaje, confundiremos c(P),
a(P) y v(P) con el número de caras, aristas y vértices respectiva-
mente), podemos tomarlos como conjuntos X de la definición an-
terior. Como G se puede tomar el grupo de transformaciones que
permutan c(P), a(P) y v(P); por ejemplo, el grupo de rotaciones de
R3 que deja invariante a P. Evidentemente, cuanto más regular sea
el poliedro, más elementos tendrá G y más difı́cil será conocer las
clases de conjugación de G.

Por diversas razones que veremos más adelante, conviene recor-

dar (o conocer) seis tipos de poliedros:

Tetraedro Cubo Octaedro

Dodecaedro Icosaedro Prisma

40 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.

Observación. Retengamos en mente la relación de Euler,

v(P) = 2 + a(P) − c(P) (3.2)

En los cinco poliedros regulares que hemos visto tenemos

Poliedro v(P) a(P) c(P)

Tetraedro 4 6 4
Cubo 8 12 6
Octaedro 6 12 8
Dodecaedro 20 30 12
Icosaedro 12 30 20

Cuadro 3.1: Vértices, aristas y caras de los poliedros regulares.

Podemos definir en un grupo G otra relación de equivalencia R1

que diremos menos fina que R0 (es decir, cada clase de equivalencia
por R1 es unión de varias clases de equivalencia por R0 ).

Definición. Si G es un grupo finito, definimos la relación de equi-

valencia R1 , que llamamos equivalencia enumerativa, como

gR1 g̃ ⇐⇒ ∃h ∈ G, ∃k ∈ N tales que g̃ = h−1 · g k · h

bajo la condición mcd(h, k) = 1. Diremos entonces que g y g̃ son

enumerativamente equivalentes.

Profundicemos un poco más en esta definición. Sabemos que si G

es un grupo finito, el orden de un elemento g ∈ G es el menor núme-
ro natural m ∈ N tal que g m = e donde e ∈ G es el elemento neutro.
Resulta que si k es otro número natural tal que mcd(m, k) = 1 en-
tonces el orden de g k es también m.

Si G = Sn , sabemos que el orden de un ciclo es exactamente su

longitud, y que el orden de cualquier σ ∈ Sn es el mı́nimo común
múltiplo de las longitudes de sus ciclos. Pues bien, presta aten-
ción. Si el orden de σ es m y k ∈ N es tal que mcd(m, k) = 1 entonces
k es también primo con el orden de todos los ciclos en los que se
descompone σ, pues m ya era el mcm de esas longitudes. En parti-
cular σ y σ k son permutaciones conjugadas.
3.2. ACCIONES DE GRUPO. 41

Proposición. Si ρ : G −→ Sn es una acción sobre X = {1, ..., n} y

g ∈ G es de orden m, y tomamos k ∈ N tal que mcd(m, k) = 1 entonces
ρ(g) y ρ(g k ) son permutaciones con el mismo polinomio indicador de
ciclos cualesquiera sean n y ρ.

Demostración. Como el orden de g es m, g m = e. En particular ρ

es un homomorfismo de grupos, luego ρ(g m ) = ρ(g)m = id luego el
orden m̃ de ρ(g) debe ser divisor de m. Entonces sigue cumpliendo
que mcd(m̃, k) = 1 y por tanto ρ(g) y ρ(g k ) son conjugados en Sn , es
decir, tienen el mismo polinomio indicador de ciclos. OMC

 Ejemplo. Tomemos el grupo simétrico D4 (presuponemos que lo

conoces, más adelante se define), que podemos representar con per-
mutaciones como

D4 = {id, (1 2 3 4), (1 3)(2 4), (1 4 3 2), (1 4)(2 3), (1 3), (2 4), (1 2)(3 4)}

Este grupo actúa sobre los vértices de un cuadrado y genera el po-

linomio indicador de ciclos

1
Pρ (x1 , x2 , x3 , x4 ) = (x41 + 2x21 x2 + 3x22 + 2x4 )
8

¿Por qué? Examinemos el grupo D4

orden de los ciclos

σ
1 2 4
id 4 0 0
(1 2 3 4) 0 0 1
(1 3)(2 4) 0 2 0
(1 4 3 2) 0 0 1
(1 4)(2 3) 0 2 0
(1 3) 2 1 0
(2 4) 2 1 0
(1 2)(3 4) 0 2 0

Entonces por (3.1) podemos calcular Pρ como 1/8 por la suma de

los monomios indicadores, que son
42 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.

σ monomio indicador
id x41
(1 2 3 4) x14
(1 3)(2 4) x22
(1 4 3 2) x14
(1 4)(2 3) x22
(1 3) x21 x12
(2 4) x21 x12
(1 2)(3 4) x22

Entonces
1
Pρ (x) = (x41 + 3x22 + 2x21 x2 + 2x4 )
8
y efectivamente 1 + 3 + 2 + 2 = 8 = |D4 | = gradop (Pρ ).

3.3. Grupos de rotaciones de poliedros re-

gulares.
Estudiemos a fondo los poliedros regulares que acabamos de
mencionar. En R3 tenemos exactamente el tetraedro, el cubo, el oc-
taedro, el dodecaedro y el icosaedro.

Definición. Si P es un poliedro regular, su poliedro dual P ∗ es el

que se construye tomando como vértices los centros de las caras
de P y como aristas las rectas que unen dos de los nuevos vértices
siempre que las caras de las que son centros se intersecan en una
arista de P.

Con la definición anterior, el cubo y el octaedro son duales, el

dodecaedro y el icosaedro son duales, y el tetraedro es su propio
dual. Observa el Cuadro 2.1. ¿Qué relación hay entre los poliedros
duales, v(P) y c(P)?

El grupo de rotaciones de R3 que deja invariante a un poliedro re-

gular también deja fijo a su dual, luego nos tenemos que preocupar
únicamente de tres grupos distintos: el del tetraedro, el del cubo y
el del icosaedro. Dichos grupos los representamos por G0 (T ), G0 (C)
y G0 (I) respectivamente. Si además de las rotaciones consideramos
las reflexiones, escribiremos G1 (T ), G1 (C) y G1 (I) respectivamente.
3.3. GRUPOS DE ROTACIONES DE POLIEDROS REGULARES. 43

A estos tres últimos grupos nos referiremos como grupo de movi-

mientos o grupos puntuales del poliedro P.

3.3.1. Orden de los grupos de movimiento.

Vamos a deducir el número de elementos de cada uno de los
seis grupos que acabamos de ver. Fijado un vértice v0 de uno de
los tres poliedros P que tratamos, un movimiento puede llevar ese
vértice a 4, 8 o 20 otros vértices según P sea un tetraedro, cubo o
un icosaedro.

v0 v0

Ahora, si v˜0 es el vértice de destino, hay 3! posibilidades si el mo-

vimiento es rotación o reflexión, y solo 3!/2 = 3 si el movimiento es
una rotación. En conclusión,

|G0 (T )| = 4 · 3 = 12, |G1 (T )| = 4 · 6 = 24

|G0 (C)| = 8 · 3 = 24, |G1 (C)| = 8 · 6 = 48
|G0 (I)| = 20 · 3 = 60, |G1 (I)| = 20 · 6 = 120

3.3.2. Pero, ¿no hay más poliedros regulares?

¿Sólo existen cinco poliedros regulares? Efectivamente. Si P es
un poliedro regular, una cara c0 de P tiene p aristas, y todas las
caras tendrán p aristas por ser regular. Si v0 es un vértice de P, en
él confluyen q aristas, y en todos los vértices también. Entonces se
han de cumplir las ecuaciones

2a(P) = pc(P)
2a(P) = qv(P)

Pero también ha de cumplirse la relación de Euler (3.2) luego sus-

tituyendo v(P) por 2a(P)/q y c(P) por 2a(P)/p tenemos que

1 1 1
+ >
q p 2
44 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.

donde p, q ≥ 3. Con estas condiciones, existen sólo cinco parejas de

enteros que cumplen todas las relaciones,

(3, 3) ∼ tetraedro
(4, 3) ∼ cubo
(3, 4) ∼ octaedro
(5, 3) ∼ dodecaedro
(3, 5) ∼ icosaedro

Observación. Resulta que sı́ hay más poliedros regulares. Los cinco
que acabamos de ver se llaman poliedros regulares convexos porque
eso, son convexos. Existen otros cuatro poliedros regulares no con-
vexos de nombres: pequeño dodecaedro estrellado, gran dodecaedro
estrellado, gran dodecaedro y gran icosaedro, que fı́sicamente son
(respectivamente)

Dodecaedro estrellado Dodecaedro estrellado

Gran dodecaedro Gran icosaedro

Por si acaso,

Definición. Un poliedro P es convexo si elegidos dos puntos cua-

lesquiera de P, el segmento que los une se queda dentro de P. Evi-
dentemente estos cuatro últimos no lo cumplen, basta tomar dos
puntos en dos picos distintos.
3.3. GRUPOS DE ROTACIONES DE POLIEDROS REGULARES. 45

3.3.3. Clases enumerativas del grupo de rotaciones.

En el espacio euclı́deo, toda rotación es un giro de ciertos grados
(no usamos radianes).

Clases enumerativas de G0 (T ).
Para el tetraedro, tenemos 3 clases distintas,

1. La clase de los giros de 120◦ y 240◦ alrededor de un eje que

pasa por un vértice y por el centro de la cara opuesta. Esta
clase tiene 8 = 2 · 4 elementos.

2. La clase de los giros de 180◦ alrededor de un eje que une el

centro de una arista con el centro de la arista opuesta. Esta
clase tiene 3 = 6/2 elementos.

3. La aplicación identidad es una clase por sı́ sola.

En la siguiente tabla resumimos el monomio indicador de ciclos de

un elemento de cada clase,

Clase monomio c(P) monomio v(P) monomio a(P)

1 x1 x3 x1 x3 x23
2 x22 x22 x21 x22
3 x41 x41 x61

Con estos datos podemos determinar los 3 polinomios indicadores

de ciclos,
1
Pρc (x) = (8x1 x3 + 3x22 + x41 )
12
1
Pρv (x) = (8x1 x3 + 3x22 + x41 )
12
1
Pρa (x) = (8x23 + 3x21 x22 + x61 )
12

Clases enumerativas de G0 (C).

El cubo tiene cinco clases distintas,

1. La clase de los 6 = 3 · 2 giros de 90◦ y 270◦ alrededor de un eje

que pasa por el centro de una cara del cubo y el centro de la
cara opuesta.
46 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.

2. La clase de los tres giros de 180◦ alrededor de un eje que pa-

sa por el centro de una cara del cubo y el centro de la cara
opuesta.

3. La clase de los 8 = 4 · 2 giros de 120◦ y 240◦ alrededor de un

eje que pasa por un vértice y el opuesto.

4. La clase de los 6 = 12/2 giros de 180◦ alrededor de un eje que

una el centro de una arista del cubo con el centro de la arista
opuesta.

5. La identidad.
Los monomios indicadores son entonces

Clase monomio c(P) monomio v(P) monomio a(P)

1 x21 x4 x24 x34
2 x21 x22 x42 x62
3 x23 x21 x23 x43
4 x32 x42 x21 x52
5 x61 x81 x12
1

Con estos datos concluimos que los polinomios respectivos para las
caras, vértices y aristas son
1
Pρc (x) = (6x21 x4 + 3x21 x22 + 8x23 + 6x32 + x61 )
24
1
v
Pρ (x) = (6x24 + 3x42 + 8x21 x23 + 6x42 + x81 )
24
1
Pρ (x) = (6x34 + 3x62 + 8x43 + 6x21 x52 + x12
a
1 )
24

Clases enumerativas de G0 (I).

El icosaedro tiene 4 clases enumerativas,
1. La clase de los 24 = 6 · 4 giros de 72◦ , 144◦ y 216◦ .

2. La clase de los 20 = 10 · 2 giros de 120◦ y 240◦ alrededor de un

eje que pase

a) por un vértice del dodecaedro y su vértice opuesto.

b) por el centro de una cara del icosaedro y el centro de la
cara opuesta.
3.4. ISOMETRÍAS Y EL GRUPO PUNTUAL. 47

3. La clase de los 15 = 30/2 giros de 180◦ alrededor de un eje que

pasa por el centro de una arista del dodecaedro y el centro de
la arista opuesta.

4. La identidad.

Los monomios indicadores serı́an

Clase monomio c(P) monomio v(P) monomio a(P)

1 x21 x25 x45 x65
2 x43 x21 x63 x103
3 x62 x10
2 x21 x14
2
4 x12
1 x20
1 x301

Ası́, los polinomios correspondientes son

1
Pρc (x) = (24x21 x25 + 20x43 + 15x62 + x12
1 )
60
1
Pρv (x) = (24x54 + 20x21 x63 + 15x10 20
2 + x1 )
60
1
Pρa (x) = (24x65 + 20x10 2 14
3 + 15x1 x2 + x1 )
30
60
Observación. A la vista de estos tres ejemplo, podemos concluir
que para determinar el polinomio indicador de ciclos de un grupo
G, basta escribir
1
Pρ (x) = (A1 M1 (x) + · · · + Ak Mk (x))
|G|

donde |G| es el número de elemento de G, Mi son los monomios

indicadores de cada clase de equivalencia de G bajo la relación R0
(o R1 también nos sirve) y Ai es el número de elementos de la clase
i−ésima bajo la misma relación.

3.4. Isometrı́as y el grupo puntual.

Para entender mejor el grupo de rotaciones y reflexiones de un
poliedro regular, necesitamos recordar varios conceptos de geometrı́a
afı́n.
48 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.

Definición. Sea V un espacio euclı́deo con producto escalar h•, •i.

Una isometrı́a de V es un endomorfismo f : V −→ V tal que
hu, vi = hf (u), f (v)i
Ejemplo. Las simetrı́as ortogonales respecto de un subespacio W ⊆
V son isometrı́as en V . En efecto, si v, w ∈ V con v = v1 + v2 y
w = w1 + w2 donde v1 , w1 ∈ W y v2 , w2 ∈ W ⊥ entonces
hsW (v), sW (w)i = hv1 , w1 i + hv2 , w2 i − hv1 , w2 i − hv2 , w1 i
hv, wi = hv1 , w1 i + hv2 , w2 i + hv1 , w2 i + hv2 , w1 i
Como v1 y w2 son ortogonales, y w1 y v2 también, entonces hv1 , w2 i =
hv2 , w1 i = 0 luego se da la igualdad.

Como consecuencia de la definición, una isometrı́a conserva nor-

mas y ángulos. La propiedad que más nos interesa de las isometrı́as
es la siguiente.

Proposición. Si f : V −→ V es una isometrı́a, la matriz de f en

cualquier base ortonormal es una matriz ortogonal. En particular,
el determinante de f es ±1.
Demostración. Sea B = {e1 , ..., en } una base de V ortonormal para
h•, •i y sea A = (aij ) la matriz de f en B. Como f es un isomorfis-
mo, B ′ = {f (e1 ), ..., f (en )} es también base de V , y además la ma-
triz de cambio de B ′ a B es precisamente A. Por ser f isometrı́a,
hf (ei ), f (ej )i = hei , ej i = δij , ası́ que B ′ es también base ortonormal y
por tanto A es ortogonal. En particular,
1 = det(At A) = det(A)2 ⇐⇒ det(A) = ±1
OMC
(recuerda que δij vale 1 si i = j y cero en cualquier otro caso).

Estamos en condiciones de clasificar las isometrias en R2 y R3 .

3.4.1. Isometrias en R2 .
Definición. Se llama giro de ángulo α al endomorfismo f : R2 −→ R2
con matriz en la base canónica de R2
 
cos(α) − sen(α)
Gα =
sen(α) cos(α)
3.4. ISOMETRÍAS Y EL GRUPO PUNTUAL. 49

En este caso det(Gα ) = 1.

Definición. Se llama simetrı́a respecto de la recta L al endomorfismo

f : R2 −→ R2 con matriz en la base canónica
 
cos(α) sen(α)
Sα =
sen(α) − cos(α)

En este caso det(Sα ) = −1 y la recta L es L((1, 0)).

Observación. En vez de usar la base canónica de R2 se puede uti-

lizar cualquier base B = {e1 , e2 } ortonormal. Entonces la recta L =
L(e1 ).

Proposición. La composición de

1. dos simetrı́as es un giro.

2. un giro y una simetrı́a (en cualquier orden) es una simetrı́a.

3. dos giros es un giro.

Demostración. Basta observar los determinantes,

1. (−1)(−1) = 1 =⇒ un giro.

2. (−1)1 = 1(−1) = −1 =⇒ una simetrı́a.

3. 1 · 1 = 1 =⇒ un giro.

OMC

De esta proposición extraemos una información esencial: el con-

junto de los giros en R2 bajo la operación de composición es un
grupo. El conjunto de únicamente las simetrı́as no es un grupo,
pero si juntamos giros y simetrı́as obtenemos un nuevo grupo.

Definición. El grupo de giros (o rotaciones) que dejan fijo el centro

de un polı́gono regular de n lados se llama grupo cı́clico de orden n,
que denotamos Cn .
50 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.

Definición. El grupo de giros y reflexiones (o simetrı́as) que dejan

fijo el centro de un polı́gono regular de n lados se llama grupo diédri-
co de orden 2n, que denotamos Dn .

Por ejemplo, si tomamos un triángulo equilátero (n = 3) entonces

los dos grupos C3 y D3 son (la primera fila el grupo C3 , las dos filas
el grupo D3 ).

 Ejemplo. Vamos a calcular el polinomio indicador de ciclos del

triángulo anterior. Lo primero es representar D3 como S3 , es decir,
con permutaciones. Para ello, numere las tres aristas del 1 al 3
(en el orden que quiera) y estudie dónde acaba cada arista tras un
giro/reflexión. Las seis permutaciones serán

id, (2 1 3), (2 3 1), (1 2), (2 3), (1 3)

(o (1 3 2) y (1 2 3)). Ahora tenemos dos opciones. Aplicar la defini-

ción (3.1) o bien hacer caso a una observación y calcular primero
las clases de conjugación. Vamos a hacerlo de las dos formas. Si
calculamos el monomio indicador de cada permutación,

σ monomio indicador
id x31
(2 1 3) x13
(2 3 1) x13
(1 2) x11 x12
(2 3) x11 x12
(1 3) x11 x12

De aquı́ es inmediato que el polinomio es

1 1
Pρ (x) = (x31 + x13 + x13 + x11 x12 + x11 x12 + x11 x12 ) = (x41 + 2x13 + 3x11 x12 )
6 6
3.4. ISOMETRÍAS Y EL GRUPO PUNTUAL. 51

Si lo hacemos con las clases de conjugación, vemos que sólo hay

tres, la identidad, los 3−ciclos y las trasposiciones,

σ elementos en la clase monomio

id 1 x31
(2 1 3) 2 x13
(1 2) 3 x11 x12

Ahora es directo el polinomio,

1
Pρ (x) = (x31 + 2x13 + 3x11 x12 )
6

3.4.2. Isometrı́as en R3 .
En este caso tendremos que distinguir si f es diagonalizable o
no. Tomemos B = {e1 , e2 , e3 } una base ortonormal de R3 .

1. Si Mf (B) = I3 entonces f es la identidad.

2. Si  
1 0 0
Mf (B) = 0 1 0
0 0 −1
entonces f es una simetrı́a respecto de un plano ∆. En particu-
lar, ∆ = L(e1 , e2 ) (la posición de los ±1 pueden varı́ar, el plano
será el generado por los vectores correspondientes al +1).

3. Si  
1 0 0
Mf (B) = 0 −1 0
0 0 −1
entonces f es una simetrı́a respecto de la recta L = L(e1 ). Tam-
bién se conoce como simetrı́a axial.

4. Si Mf (B) = −I3 entonces f es la simetrı́a central respecto del

origen.

Observa que si f es diagonalizable, siempre se obtiene una simetrı́a.

Si ahora f es no diagonalizable, tenemos únicamente dos casos,
52 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.

1. f es un giro respecto de una recta L si

 
1 0 0
Mf (B) = 0 cos(α) − sen(α)
0 sen(α) cos(α)
donde L = L(e1 ).
2. f es una composición de una simetrı́a y una rotación si la ma-
triz de f en la base B es
    
−1 0 0 1 0 0 −1 0 0
 0 cos(α) − sen(α) = 0 cos(α) − sen(α)  0 1 0
0 sen(α) cos(α) 0 sen(α) cos(α) 0 0 1
En particular, f es la composición de la simetrı́a respecto del
plano L(e2 , e3 ) (la matriz diagonal) con el giro de ángulo α y eje
la recta L(e1 ).
Los grupos de movimientos que obtenemos en R3 son los 6 que
ya hemos visto.

Definición. Al conjunto de isometrı́as de un espacio euclı́deo que

dejan fijo el centro de la figura centrada en el origen, junto con la
operación de composición, se le llama grupo puntual.

Observación. Los grupos puntuales (o de movimientos) de un pris-

ma regular y una pirámide regular son, respectivamente, Dn y Cn
para n lados que tenga la base. La pirámide puede entenderse como
un polı́gono en R2 , pues al tener un único pico no permite reflexio-
nes; los giros son los de la base.

Proposición. Si F es una figura con grupo de rotaciones G0 (F ) = G0

y grupo puntual G1 (F ) = G1 (ambos finitos) y suponemos que existe
una reflexión s ∈ G1 (F ) − G0 (F ) tal que gs = sg para cada g ∈ G0 ,
entonces
gR1 g ′ =⇒ sgR1 sg ′

Demostración. Si gR1 g ′ entonces existen h ∈ G0 , k ∈ N tales que g ′ =

h−1 g k h. Multiplicando por s,
sg ′ = h−1 sg k h ⇐⇒ sg ′ R1 sg
OMC
3.4. ISOMETRÍAS Y EL GRUPO PUNTUAL. 53

 Ejemplo. La simetrı́a central aplicada al cubo. Ası́, podemos rea-

lizar el estudio de G1 (C). Para empezar, se recomienda recortar y
montar 2 cubos de los que hay en los anexos; uno para moverlo y
otro para usar como referencia. Al estudiar G0 (C) hemos compro-
bado que hay 5 clases de equivalencia distintas, de órdenes 4, 2, 3,
2 y 1 respectivamente. Al introducir la simetrı́a central s, que es de
orden 2 pues s2 = id, conseguimos otras 5 clases de equivalencia,
que son
1. 6 giros de 90◦ y 270◦ compuestos con s (orden 8).
2. 3 giros de 180◦ compuestos con s (orden 4).
3. 8 giros de 120◦ y 240◦ compuestos con s (orden 6).
4. 6 giros con eje la recta que une los centros de dos aristas
opuestas compuestos con s (orden 4).
5. La identidad compuesta con s; de orden 2.
Apoya los dos cubos uno al lado del otro sobre la cara 2 de tal forma
que veas la cara 1. El cubo de la derecha será nuestra referencia y
el de la izquierda lo iremos moviendo. Un elemento de la primera
clase de equivalencia que acabamos de nombrar serı́a σ dada por
g s g s g s g
4 7→ 7 7→ 10 7→ 2 7→ 6 7→ 5 7→ 8 7→ 12
donde g indica un giro de 90◦ (o de 270◦ ) y s la simetrı́a. De la misma
forma un elemento de la segunda clase es
g s g
4 7→ 6 7→ 2 7→ 12
54 CAPÍTULO 3. POLINOMIOS Y PERMUTACIONES.
Capı́tulo 4

Teorı́a de Polya.

Vamos a adentrarnos en el mundo de los colores. En matemáti-

cas, podemos distinguir elementos que son iguales pero no pintando
cada uno de un color. Si tenemos dos dados que queremos diferen-
ciar, diremos que uno es azul y otro verde (por ejemplo). Vamos a
denotar por C al conjunto de colores que tenemos y por X al con-
junto de puntos que queremos pintar.

Definición. Una coloración del conjunto X con los colores de C es

simplemente una aplicación

col : X −→ C

Se puede entender que una coloración es una acción ρ : G −→ Sn

sobre el conjunto de los puntos X.

Definición. Si col1 , col2 son dos coloraciones de X, decimos que

son iguales (o equivalentes) si existe un elemento g ∈ G tal que la
permutación ρ(g) envı́a una coloración en la otra, es decir,

col2 = col1 ◦ ρ(g)

Dos coloraciones son esencialmente distintas si no son iguales. De-

notamos por N (r, ρ) al número de coloraciones esencialmente dis-
tintas con r elementos de la acción ρ.

 Ejemplo. Tomemos un cuadrado (más bien sus cuatro vértices)

y el conjunto de colores C = {•, •}. Diferentes coloraciones de los
vértices pueden ser

55
56 CAPÍTULO 4. TEORÍA DE POLYA.

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

Las coloraciones (1) y (2) son iguales (basta rotar el cuadrado).

Definición. Sea G un grupo y X un conjunto no vacı́o. Supongamos

que G actúa sobre X,
T : G × X −→ X
(g, x) 7→ T (g, x) = g · x
Si x ∈ X es un elemento cualquiera de X, definimos
1. La órbita de x como el conjunto
x = {g · x : g ∈ G} ⊆ X

2. El estabilizador de x como el subgrupo

Gx = {g ∈ G : g · x = x} ⊆ G

Y si g ∈ G, los puntos fijos de g es el conjunto

fj(g) = {x ∈ X : g · x = x} ⊆ X
Relacionemos estas definiciones con los conceptos de conjuga-
ción y subgrupos normales que vimos años pasados. Si G actúa por
conjugación (R0 ) sobre sı́ mismo, T : G × G −→ G entonces la órbita
de x ∈ G es
x = {gxg −1 : g ∈ G}
es decir, justamente la clase de conjugación de x. Si ahora H ⊆ G
es un subgrupo H de G, y H actúa por conjugación sobre G,
T : H × G −→ G
entonces el estabilizador de x ∈ H es
Hx = {h ∈ H : hxh−1 = x} = CH (x)
el centralizador de x en H (se recomienda ver Estructuras Algebrai-
cas, Definición 1.48). A continuación, veamos un resultado del año
pasado que nos conviene recordar.

Proposición. Sea G un grupo y x ∈ G. Entonces |x| = |G : CG (x)|. En

particular, si G es finito, |G| = |CG (x)| · |x|.
 57

Demostración. Sea x ∈ G. Definimos la aplicación

ϕ : x −→ {gCG (x) : g ∈ G}

de la siguiente manera: dado y ∈ x, existe un gy ∈ G tal que y = gxg −1 .

Entonces mandamos y 7→ gy CG (x).
1. Veamos que está bien definida. Si g, h ∈ G tales que y = gxg −1 , y =
hxh−1 , entonces

gxg −1 = hxh−1 =⇒ h−1 gxg −1 h = x =⇒ (h−1 g)x(h−1 g)−1 = x

=⇒ h−1 g ∈ Cl(x)
y se tiene que gCG (x) = hCG (x).

2. Veamos que es inyectiva. Si gCG (x) = hCG (x) entonces

h−1 g ∈ x =⇒ x = (h−1 g)x(h−1 g)−1 =⇒ x = h−1 gxg −1 h

de donde gxg −1 = hxh−1 .

3. Veamos que es sobreyectiva. Si α ∈ {gCG (x) : g ∈ G} existe

un g ∈ G tal que α = gCG (x) =⇒ y = gxg −1 ∈ x y entonces
ϕ(y) = gCG (x) = y.
Entonces ϕ es una biyección y por tanto |x| = |G : CG (x)|. En parti-
cular, si G es finito,
|G|
|G : CG (x)| =
|CG (x)|
OMC
Observación. La notación |G : CG (x)| es exactamente el número de
clases laterales de G, es decir, |x|. No se ha cambiado la notación
para poder copiar y pegar de los apuntes del año pasado.

Podemos formular la proposición anterior en términos de accio-

nes de grupo, simplificando notablemente la demostración.

Proposición. Sea G un grupo que actúa sobre un conjunto finito

X, T : G × X −→ X con T (g, x) = g · x. Entonces

|x| · |Gx | = |G|

58 CAPÍTULO 4. TEORÍA DE POLYA.

Demostración. Tomemos x ∈ G. Veamos que para cualquier g ∈ G,

hay exactamente |Gx | elementos en G de la forma h = ga con a ∈ Gx
tal que h · x = g · x. Esto es,

g · x = h · x ⇐⇒ x = g −1 h · x ⇐⇒ g −1 h ∈ G ⇐⇒ h = ga

para algún a ∈ Gx (pues g −1 h · x = g −1 ga · x = a · x = x). Esto prueba

que en x hay |Gx | elementos tales que h · x = g · x. Concluimos que

|x| · |Gx | = |G|

OMC
Lo que nos interesa es, dado un conjunto C de colores y un
conjunto finito X de puntos que deseamos colorear mediante col:
X −→ C, saber cuántas coloraciones esencialmente distintas hay.
Esto equivale a determinar el número n de órbitas (clases de conju-
gación) x1 , ..., xn que hay al actuar G sobre el conjunto de coloracio-
nes, que llamaremos Ω.

4.1. El teorema de Polya.

Veamos un pequeño lema atribuido a Cauchy y Frobenious pero
que irónicamente se conoce como lema de Burnside (Burnside era
un señor).

Lema (de Burnside). Sea G un grupo que actúa sobre un conjunto

finito X. Sean x1 , ..., xn las distintas órbitas de la acción del grupo
G sobre X. Entonces el número n de órbitas es
1 X
n= |fj(g)|
|G| g∈G

Demostración. Ya hemos comprobado que |x| · |Gx | = |G|, es decir,

|x| = |G|/|Gx |. La órbita de x ∈ X nos induce una relación de equi-
valencia
xRx′ ⇐⇒ ∃g ∈ G tal que g · x = x′
Entonces, para cada y ∈ x, y = x luego |Gx | = |Gy |. De aquı́,
X
|G| = |x||Gy | = |Gy |
y∈x
4.1. EL TEOREMA DE POLYA. 59

Si hay n órbitas,
n X
X X X
⋆
n|G| = |Gy | = |Gy | = |fj(g)|
i=1 y∈xi y∈X g∈G

donde ⋆ es justamente la definición de puntos fijos. De aquı́ con-

cluimos que
X 1 X
n|G| = |fj(g)| ⇐⇒ n = |fj(g)|
g∈G
|G| g∈G

OMC
 Ejemplo. Partiendo de las letras a y b se forman palabras de lon-
gitud 3. Ellas se consideran equivalentes si se obtienen una de la
otra al cambiar de lugar las letras extremas, por ejemplo abb ∼ bba.
¿Cuántas clases de equivalencia hay? Equivalentemente, ¿cuántas
palabras esencialmente distintas podemos construir? Para resolver
este problema, consideramos el grupo G = {id, σ} donde σ es la per-
mutación que intercambia las letras extremas. De acuerdo con el
lema de Burnside, el número de órbitas n es
1 X
n= |fj(g)|
|G| g∈G

Para empezar, el número total de palabras posibles es 23 = 8. Evi-

dentemente la identidad deja fijas todas las palabras, luego |fj(id)| =
8. Para la permutación σ tenemos 4 puntos fijos,
aba, aaa, bab, bbb
luego |fj(σ)| = 4. Entonces
1
n = (8 + 4) = 6
2

Teorema (de Polya). Sea X un conjunto finito, C un conjunto de r

colores y
Ω = {col : X −→ C tal que col es una coloración}
El número de coloraciones esencialmente distintas que podemos
hacer con los r colores en los puntos de X (equivalentemente, el
número de órbitas n de G actuando sobre Ω) es
N (r, ρ) = Pρ (r, r, ..., r)
60 CAPÍTULO 4. TEORÍA DE POLYA.

es decir, basta evaluar el polinomio indicador de ciclos en el número

de colores r = |C|.

Demostración. Tomemos el conjunto fjΩ (g) = {col ∈ Ω : gcol = col}.

Vamos a ver que g ∈ G fija una coloración col si, y sólo si, col colorea
con el mismo color los elementos de cada ciclo de g.
=⇒ ) Si g · col = col entonces (g · col)(x) = col(x) luego col(g −1 (x)) =
col(x) para cada x ∈ X. En particular se cumple para x = y, g(y), g 2 (y), ...
si y ∈ X. Por lo tanto,

col(y) = col(g −1 (y)) = col(g −1 (g(y))) = col(g(y))

Procediendo para g 2 (y), ..., g n (y) se tiene que

col(y) = col(g(y)) = · · · = col(g n (y))

Esto implica que si g fija a col entonces col asigna el mismo color a
cada elemento de todo ciclo de g.
⇐=) Si col es tal que cada ciclo de g es coloreado con el mismo co-
lor, entonces g −1 (x) y x tienen el mismo color para cada x ∈ X. Esto
quiere decir que col(g −1 (x)) = col(x) y entonces g · col(x) = col(x)
para todo x ∈ X. Concluimos que g · col = col luego g deja fijo a col.
Vemos ası́ que los elementos de fjΩ (g) son precisamente los elemen-
tos que colorean los elementos de cada ciclo con el mismo color.
Ahora, notemos que si σ es una permutación con m ciclos (1 ≤ m ≤
n) entonces hay |C|m = rm coloraciones posibles para σ. Entonces

|fjΩ (g)| = ri1 ri2 · · · rin

que es justamente

1 X
|fj (g)| = Pρ (r, r, ..., r)
|G| g∈G Ω

OMC

Explicación de la demostración. A ver. En la demostración se ha

escrito g(y) cuando g ∈ G, y ∈ X. El elemento g no es una aplicación
(no tiene por qué, vaya), pero al actuar G sobre X, podemos entender
la acción como (como ya hemos mencionado) ρ : G −→ Sn que asigna
a cada g ∈ G una permutación, que llamamos igual para confundir.
Entonces g(y) es la permutación ρ(g) actuando sobre y ∈ X. Se ha
4.1. EL TEOREMA DE POLYA. 61

utilizado también la igualdad (g · col)(x) = col(g −1 (x)). Esto es otra

acción
T : G × Ω −→ Ω
(g, col) 7→ T (g, col) = col(g −1 (y))
que se puede probar que efectivamente es una acción. Evidente-
mente, g −1 es la permutación inversa de g en el sentido que se acaba
de explicar.

 Ejemplo. ¿De cuántas formas distintas se pueden colorear las 4

perlas de un collar si disponemos de los colores rojo y azul? Estamos
ya en condiciones de responder a esta pregunta. Podemos represen-
tar las perlas como los vértices de un cuadrado

Entonces si X es el conjunto de las perlas X = {1, 2, 3, 4} vemos

claro que el grupo que actúa sobre X es el de los movimientos del
cuadrado D4 . Necesitamos entonces el polinomio indicador de D4 ,
que por casualidades de la vida hemos calculado en otro ejemplo,
1
Pρ (x) = (x41 + 2x21 x2 + 3x2 + 2x4 )
8
Entonces el número de coloraciones esencialmente distintas que
podemos hacer con dos colores es
Pρ (2, 2, 2, 2) = 6
que son justamente

(1) (2) (3)

(4) (5) (6)

62 CAPÍTULO 4. TEORÍA DE POLYA.

(cualquier otra que se te ocurra es una rotación de las anteriores).

 Ejemplo. Deseamos saber el número de isómeros (moléculas dis-

tintas) de la molécula de estructura
•

• C •

donde en • pueden ir los elementos CH3 (metilo), C2 H5 (etilo), H y

Cl. ¿Cuántas moléculas distintas usando a lo sumo cuatro elementos
podemos formar? ¿Y si queremos que no haya hidrógeno? La dispo-
sición de la molécula nos induce a pensar que el grupo que actúa
sobre X = {CH5 , C2 H5 , H, Cl} es el de las rotaciones de un tetraedro
sobre los vértices (los 4 exteriores). El polinomio indicador de ciclos
es
1
Pρv (x) = (8x1 x3 + 3x22 + x41 )
12
y por lo tanto el número de moléculas es N (4, ρ) = Pρv (4, 4, 4) = 36. Si
ahora queremos que el hidrógeno no aparezca, consideramos que
únicamente tenemos 3 colores X̃ = {CH3 , C2 H5 , Cl} y el número de
moléculas es
N (3, ρ) = Pρv (3, 3, 3) = 15

Observa que este problema es equivalente a determinar de cuántas

maneras distintas se pueden colorear los vértices de un tetraedro
con 4 (o 3) colores.

¿Y si queremos asignar distintos pesos a distintos colores? Es

decir, utilizar s1 veces el color r1 , s2 veces el color r2 ,... En este caso
tenemos un teorema más general que el de Polya.

Teorema (de Redfield-Polya). Sea C = {r1 , ..., rk } un conjunto de k

colores, X un conjunto de n puntos a colorear y
T : G × X −→ X
una acción de un grupo G sobre X. Dados s1 , ..., sk ∈ N tales que
s1 +· · ·+sn = n, el número N de coloraciones esencialmente distintas
4.1. EL TEOREMA DE POLYA. 63

de los puntos de X tales que se utiliza s1 veces el color r1 ,..., sk veces

el color rk es el coeficiente del monomio y1s1 y2s2 · · · yksk que resulta al
evaluar

N = Pρ (y1 + · · · + yk , y12 + · · · + yk2 , ..., y1n + · · · + ykn )

Demostración. De nuevo estamos contando clases de equivalencia

(las distintas coloraciones). Sea Ω el conjunto de todas las colora-
ciones posibles de C en X (de cardinalidad |Ω| = k n ). Esencialmente
aplicaremos el lema de Burnside varias veces. Fijado un peso s, el
número Ns de órbitas es
1 X
Ns = |fj(g)| (4.1)
|G| g∈G

Si S ⊆ Ω es el subconjunto de todas las coloraciones de peso s, todas

las órbitas dentro de S tienen el mismo peso s, luego multiplicando
(4.1) por s y sumando sobre todos los pesos posibles,
X 1 XX
N= Ns = |fj(g)|s
s
|G| s g∈G

Si W (col) es el peso de la coloración col,

(g)
X X
|fj(g)| = W (col)
s col

donde la segunda suma se realiza para todas las coloraciones tales

que col = gcol, luego

(g)
1 XX
N= W (col) (4.2)
|G| g∈G
col

Que el lı́mite superior de la suma sea (g) significa que sustituimos

en T (col, −) − por g. Vamos a calcular

(g)
X
W (col)
col
64 CAPÍTULO 4. TEORÍA DE POLYA.

Al sustituir g dividimos X en ciclos. Como col = gcol entonces

col(x) = col(gx) = col(g 2 x) = · · ·

es decir, col es constante para cada ciclo. El recı́proco también es

cierto, si col es constante en cada ciclo, entonces col = gcol (ya que
x y g(x) están en el mismo ciclo). Si X1 , ..., Xℓ son los ciclos de g
entonces
(g) ℓ Xk
X Y |X |
W (col) = sj i
col i=1 j=1

Si ρ(g) se descompone en ciclos como ρ(g) = (b1 b2 ...) entonces

(g) k
! b1 k
! b2
X X X
= sj s2j ···
col j=1 j=1

Sustituyendo en (4.2) obtenemos

k
! b1 k
! b2
1 X X X
N= sj s2j ···
|G| g∈G j=1 j=1

OMC

Se recomienda fuertemente ver Análisis combinatorio; K.Rı́bnikov

para entender la demostración.

 Ejemplo. Volvamos al ejemplo de los isómeros. Vimos que las

moléculas que no contenı́an hidrógeno eran 15. Las otras 21 lo
contienen en diferentes pesos entre 1 y 4. Para determinar cuántas
hay de cada tipo, recurrimos al teorema de Redfield-Polya. Asigna-
mos peso 1 a las moléculas CH3 , C2 H5 y Cl, y asignamos peso h al
hidrógeno. Entonces basta sustituir h+3, h2 +3, h3 +3 en el polinomio
indicador de ciclos,
1
Pρ (h + 3, h2 + 3, h3 + 3) = ((h + 3)4 + 8(h + 3)(h3 + 3) + 3(h2 + 3)2 )
12
= h4 + 3h3 + 6h2 + 11h + 15
La información buscada la dan los coeficientes, 1h4 indica una molécu-
la con 4 hidrógenos, 3h3 indica tres moléculas con 3 hidrógenos, 6h2
indica seis moléculas con dos hidrógenos, 11h indica 11 moléculas
4.1. EL TEOREMA DE POLYA. 65

con 1 hidrógeno y el 15 son las que ya tenı́amos sin hidrógeno (h0 ).

 Ejemplo. Las caras de un tetraedro se pintan en dos colores: rojo

y azul. Si dos tetraedros están pintados de un modo distinto, pue-
de ocurrir que uno de ellos se pueda girar de tal manera que ambos
dejen de parecer distintos. En este caso se corresponden con la mis-
ma coloración. ¿Cuántas coloraciones distintas existen? Tomamos
X = {1, 2, 3, 4} que se corresponden con las caras de un tetraedro, y
G = G0 (T ) actuando sobre X. El polinomio indicador de ciclos es
1 4
Pρ (x) = (x + 8x1 x3 + 3x22 )
12 1
Para hallar el número de coloraciones esencialmente distintas, bas-
ta evaluar en x = (2, 2, 2, 2),

P ρ(2, 2, 2, 2) = 5

 Ejemplo. ¿Cuántas coloraciones distintas podemos hacer sobre

las caras de un cubo de tal forma que cuatro sean rojas y dos azules?
Sea X = {1, ..., 6} el conjunto que representa las caras del cubo y
G = G0 (C). El polinomio indicador de ciclos es
1
Pρ (x) = (6x21 x4 + 3x21 x22 + 8x23 + 6x32 + x61 )
24
Como los colores rojo y azul no aparecen en la misma medida,
tendrán pesos distintos, digamos r el peso del rojo y a el del azul.
Basta sustituir xi por ri + ai y ver el coeficiente del monomio que nos
interesa, en este caso r4 a2 :
1
Pρ = ((r+a)6 +3(r+a)2 (r2 +a2 )2 +6(r+a)2 (r4 +a4 )+6(r2 +a2 )3 +8(r3 +a3 )2 )
24
El coeficiente buscado es 2.
66 CAPÍTULO 4. TEORÍA DE POLYA.
Capı́tulo 5

Politopos y series de Laurent.

Ya deberı́amos ser unos expertos trabajando con polinomios en

una o varias variables. Hasta ahora, un monomio con coeficientes
en K en las variables x1 , ..., xn era una expresión

M (x) = xi11 xi22 · · · xinn ∈ K[x1 , ..., xn ]

donde i1 , ..., in ∈ N. Si permitimos que los exponentes sean negativos,

obtenemos el conjunto

K[x1 , ..., xn , x−1 −1

1 , ..., xn ] ( a veces K[x, x−1 ])

donde sus elementos son de la forma

M (x) = λxi11 xi22 · · · xinn

con λ ∈ K, i1 , ..., in ∈ Z. Evidentemente,

K[x1 , ..., xn ] ⊆ K[x1 , ..., xn , x−1 −1

1 , ..., xn ]

Definición. Llamamos monomio de Laurent a cualquier elemento

M ∈ K[x1 , ..., xn , x−1 −1
1 , ..., xn ]. Llamamos polinomio de Laurent a una
suma finita de monomios de Laurent. Si la suma es infinita habla-
mos de series de Laurent (ponemos dos corchetes). Para abreviar
todavı́a más, escribiremos xm para indicar xm mn
1 · · · xn .
1

Observación. Si tratamos con monomios (resp. polinomios, series)

con exponentes positivos, hablaremos de monomios (res. polino-
mios, series) normales.

67
68 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

Proposición. El conjunto K[x1 , ..., xn , x−1 −1

1 , ..., xn ] junto con las ope-
raciones usuales de suma y producto de polinomios es un anillo.
Se llama anillo de polinomios de Laurent.

Antes de seguir, necesitamos saber lo que es un retı́culo. Para

ello, recordamos varios conceptos sobre conjuntos ordenados.

5.1. Relaciones de orden.

Supongamos un conjunto X no vacı́o. Definimos una relación
binaria RO sobre los elementos de X que cumpla

1. aRO a si a ∈ X.

2. Si aRO b y bRO a entonces a = b para cada a, b ∈ X.

3. Si aRO b y bRO c entonces aRO c para todo a, b, c ∈ X.

Una relación que cumple estas tres propiedades se llama relación de

orden (parcial). Observa que distintos elementos de X no tienen por
qué estar relacionados entre sı́. En el caso de que todos los elemen-
tos estén relacionados entre sı́ hablamos de un orden total, pero no
nos interesan.

Definición. Un conjunto parcialmente ordenado (o poset, de partially

ordered set en inglés) es un par (X, RO ) donde X es un conjunto no
vacı́o y RO una relación de orden parcial sobre los elementos de X.

Como de costumbre, al hablar de conjuntos ordenados hablaremos

únicamente de X sin mencionar a la relación a no ser que sea ne-
cesario. Normalmente utilizaremos la notación ≤ para referirnos a
una relación de orden (aunque no tenga nada que ver con la rela-
ción que conocemos de ser menor o igual en los números reales).

 Ejemplo. El conjunto de los números naturales junto con la re-

lación ser menor o igual es un conjunto parcialmente ordenado (en
realidad totalmente ordenado).

Definición. Sea X un conjunto parcialmente ordenado bajo la re-

lación ≤.
5.1. RELACIONES DE ORDEN. 69

1. Un máximo de X es un elemento M ∈ X tal que x ≤ M para

todo x ∈ X. Esto es, todos los elementos son menores o iguales
que M .

2. Un maximal de X es un elemento M ∈ X tal que no hay ningún

elemento de X mayor que M .

3. Un mı́nimo de X es un elemento m ∈ X tal que m ≤ x para todo

x ∈ X. Esto es, todos los elementos son mayores o iguales que
m.

4. Un minimal de X es un elemento m ∈ X tal que no hay ningún

elemento de X menor que m.

Observación. El máximo y el mı́nimo de un conjunto, si existen,

son únicos. Si existe el máximo será el único maximal; y si existe el
mı́nimo será el único minimal.

 Ejemplo. Si tomamos X = {A ⊆ Z : |A| = 1} y los ordenamos

por inclusión, todos los elementos de X son a la vez maximales y
minimales, pero no existe ni el máximo ni el mı́nimo.

Definición. Dado un conjunto ordenado (X, ≤) y un subconjunto

Y ⊆ X, tenemos

1. Una cota superior de Y en X es un elemento C ∈ X tal que

y ≤ C para todo y ∈ Y .

2. Un extremo superior de Y en X es un elemento S ∈ X que es el

mı́nimo entre todas las cotas superiores de Y en X.

3. Una cota inferior de Y en X es un elemento c ∈ X tal que c ≤ y

para todo y ∈ Y .

4. Un extremo inferior de Y en X es un elemento s ∈ X que es el

máximo entre todas las cotas inferiores de Y en X.

Observación. En todas las definiciones anteriores se pide que la

cota o el extremo esté en X, no en Y .

Observación. Tanto el extremo inferior como superior, si existen,

son únicos. Denotamos al extremo superior de Y en X por supX (Y )
y lo llamamos supremo; y al extremo inferior de Y en X por ı́nf X (Y ),
70 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

y lo llamamos ı́nfimo.

 Ejemplo. Sea I = (1, 2) ⊆ R. Cotas superiores para I en R son 2,

3, 5, 100, pero el extremo superior de I sólo puede ser 2 (es la mejor
de las cotas en el sentido de proximidad).

5.1.1. Retı́culos.
En particular, en la definición de cotas y extremos podemos to-
mar como subconjunto Y = {a, b} de tan sólo dos elementos de X.
Con esto,

Definición. Un retı́culo es un conjunto X parcialmente ordenado

con dos operaciones binarias y tal que todo par a, b ∈ X tiene un
único extremo superior sup(a, b) ∈ X y un único extremo inferior
ı́nf(a, b) ∈ X.

Quizá esta definición sea poco práctica. Una más sencilla y que
es un ejercicio probar que es equivalente es la siguiente:

Definición. Un retı́culo es un conjunto X junto con dos operaciones

binarias ∧ y ∨ que cumplen

1. a ∧ b = b ∧ a y a ∨ b = b ∨ a

2. (a ∧ b) ∧ c = a ∧ (b ∧ c) y (a ∨ b) ∨ c = a ∨ (b ∨ c)

3. a ∨ (a ∧ b) = a y a ∧ (a ∨ b) = a

4. a ∨ a = a y a ∨ a = a

para cada a, b, c ∈ X. Estas dos operaciones cumpliendo las 4 pro-

piedades definen un orden parcial ≤ en X dado por

a ≤ b ⇐⇒ a ∨ b = b

o equivalentemente, a ≤ b ⇐⇒ a ∧ b = a.

 Ejemplo. Es un retı́culo N con su orden usual y las operaciones

n ∧ m = mcd(n, m) y n ∨ m = mcm(n, m)
5.2. POLITOPOS. 71

5.2. Politopos.
Hemos introducido el concepto de retı́culo porque un monomio
de Laurent M lo podemos ver como una n−upla (i1 , ..., in ) de los
exponentes dentro de Zn , que resulta ser un retı́culo visto de la
siguiente forma: si B = {e1 , ..., en } es la base canónica de Rn entonces

Zn = {a1 e1 + · · · + an en : ai ∈ Z}

donde las operaciones son ∩ y ∪ (unión e intersección) y el or-

den es el de la inclusión. Ası́, la multiplicación de dos monomios
M1 , M2 ∈ K[x1 , ..., xn , x−1 −1
1 , ..., xn ] se corresponde con la suma de sus
dos n−uplas asociadas.

Gráficamente Zn ⊆ Rn se puede ver como el conjunto de los pun-

tos con componentes enteras. Si entendemos Rn como espacio afı́n
euclı́deo, los puntos de Zn se llaman puntos reticulares. Aparecen
por fin los protagonistas de esta sección.

Definición. Un subconjunto U ⊆ Rn se dice convexo si elegidos dos

puntos x, y ∈ U , el segmento que los une está totalmente contenido
en U .

Definición. Dados p1 , ..., pr ∈ Rn r puntos de Rn , su envolvente con-

vexa es el mı́nimo conjunto convexo de Rn que contiene a los r pun-
tos. Escribimos conv(p1 , ..., pr ).

Definición. Un politopo es la generalización de un polı́gono a un

espacio n−dimensional.

Definición. Un politopo reticular es la envolvente convexa de un

número finito de puntos reticulares. Si F = {p1 , ..., pr } es el conjun-
to finito de puntos, se llaman vértices del politopo reticular a los
puntos v ∈ F tales que la envolvente convexa de F − {v} es un sub-
conjunto propio del politopo (por subconjunto propio entendemos
cualquier subconjnto distinto del total).

Proposición. Dados p1 , ..., pr ∈ Rn puntos de Rn , se cumple que

conv(p1 , ..., pr ) = {λ0 p0 + · · · + λr pr : λi ≥ 0, λ1 + · · · + λr = 1}

72 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

Demostración. Probamos ambas inclusiones. Sea C el conjunto

C = {λ0 p0 + · · · + λr pr : λi ≥ 0, λ1 + · · · + λr = 1}

que es convexo.
⊆) Tomando, por ejemplo, t1 = 1 y el resto igual a cero, se
cumple que {p1 , ..., pr } ⊆ C lo que implica que conv(p1 , ..., pr ) ⊆
C.

⊇) Como conv(p1 , ..., pr ) es convexo y contiene a {p1 , ..., pr } en-

tonces conv(p1 , ..., pr ) es cerrado para combinaciones lineales
convexas de elementos de {p1 , ..., pr } luego C ⊆ conv(p1 , ..., pr ).
OMC
Observa que si p1 , ..., pr ∈ Zn entonces

conv(p1 , ..., pr ) = L(p1 , ..., pr )

viendo p1 , ..., pr como vectores.

Sea ahora P (x) = M1 (x) + · · · + Mr (x) un polinomio de Laurent.

Cada monomio Mk tiene asociada una n−upla (i11 , ..., i1n ) para M1 ,...,
(ir1 , ..., irn ) para Mr . Llamamos soporte de P al conjunto

sop(P ) = {(i11 , ..., i1n ), ..., (ir1 , ..., irn ) : ijk ∈ Z}

de las n−uplas asociadas a los monomios de P .

Definición. Llamamos politopo de Newton Nw(P ) del polinomio de

Laurent P a la envolvente convexa de sop(P ).

 Ejemplo. En R2 , un politopo reticular puede ser un triangulo T

con vértices en (0, 0), (0, 1) y (1, 0).

Observa que T no contiene más puntos reticulares que sus vértices.

5.2. POLITOPOS. 73

 Ejemplo. Si P (x) = 2 − x + 3xy − xy 2 + x2 y su soporte es

sop(P ) = {(0, 0), (1, 0), (1, 1), (1, 2), (2, 1)}

y entonces su politopo de Newton asociado es Nw(P ) = conv(sop(P )),

es decir,

Definición. Si Q es un politopo reticular, llamamos polinomio in-

dicador reticular de Q al polinomio dado por la suma de todos los
monomios de Laurent M con coeficientes 1 cuyas n−uplas de expo-
nentes están en Q.

 Ejemplo. En el triángulo anterior, los monomios de Laurent aso-

ciados son los correspondientes a los vértices,

M1 (x) = x0 y 0 , M2 (x) = x0 y 1 , M3 (x) = x1 y 0

Entonces el polinomio indicador reticular de T es

PT (x) = x + y + 1

El soporte de PT es exactamente el conjunto de vértices de T .

Más adelante nos interesará un método robusto para calcular el

polinomio indicador reticular de cualquier politopo Q.

5.2.1. Cuerpo de fracciones.

Como nota auxiliar, vamos a reproducir cómo se construye el
cuerpo de fracciones dado un dominio.

Si D es un dominio de integridad, definimos en D × D − {0} una

relación de equivalencia RF dada por

(a, b)RF (c, d) ⇐⇒ ad = bc

74 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

Al hacer el cociente (D × D − {0})/RF , representamos la clase de

equivalencia de (a, b) como a/b (de ahı́ el nombre de cuerpo de frac-
ciones) y llamamos a este conjunto cociente Q(D). Para los anillos
de polinomios (que también son dominios) se utiliza la notación

Q(D[x1 , ..., xn ]) = D(x1 , ..., xn )

A los elementos de D(x1 , ..., xn ) los llamamos funciones racionales.

Ası́, Z(x1 , ..., xn ) es el conjunto de las funciones racionales de la for-
ma
 
P (x1 , ..., xn )
Z(x1 , ..., xn ) = : P, Q ∈ Z[x1 , ..., xn ] = Q(x1 , ..., xn )
Q(x1 , ..., xn )

En Q(D) se definen las operaciones (+) y (·) como

a c ad + bc a c ac
+ = y · =
b d bd b d bd
y entonces (Q(D), +, ·) es un cuerpo (pruébese).

5.2.2. Series de Laurent.

Fijemos nuestra atención en las series de Laurent. Para ello, con-
viene tener fresco el capı́tulo de series.

Si s1 , s2 ∈ K[[x1 , ..., xn , x−1 −1

1 , ..., xn ]] son dos series de Laurent, las po-
demos sumar término a término como hacı́amos con las series nor-
males. Las series de Laurent junto con la suma forman un grupo
conmutativo. Sin embargo, no siempre podremos multiplicar dos
series de Laurent. Si tomamos

s1 (x) = s2 (x) = · · · + x−3 + x−2 + x−1 + 1 + x + x2 + x3 + · · ·

¿Cómo definimos su producto? No podemos hacerlo como con se-

ries normales, pues no hay una suma finita para cada cj si s1 s2 =
c0 + c1 + · · · . Lo que si que podemos definir en las series de Laurent
es un producto exterior de un polinomio de Laurent y una serie de
Laurent.

Definición. Sea A un anillo conmutativo. Un A−módulo M es un

grupo conmutativo (M, +) junto con una operación externa · : A ×
M −→ M que cumple
5.2. POLITOPOS. 75

1. a · x = x · a

2. a · (x + y) = a · x + a · y

3. (a + b) · x = a · x + b · x

4. (ab) · x = a · (b · x)

5. 1 · x = x

para cualesquiera a, b ∈ A, x, y ∈ M .

Observa, por ejemplo, que si A es un cuerpo entonces un A−módulo

es un A−espacio vectorial. En particular, tomando A como el anillo
de polinomios de Laurent, tenemos que las series de Laurent son un
módulo sobre A, que llamaremos L. Es decir, sı́ podemos multiplicar
polinomios de Laurent por series de Laurent. En analogı́a con los
espacios vectoriales, los polinomios de Laurent serı́an los escalares.

Definición. Una serie de Laurent s se dice racional si existen po-

linomios normales P, Q ∈ K[x1 , ..., xn ] con Q no nulo y tales que
s = P/Q ⇐⇒ Qs = P . Denotamos por RL al conjunto de series
de Laurent que son racionales dentro de C[[x1 , ..., xn , x−1 −1
1 , ..., xn ]].

Proposición. El anillo de polinomios de Laurent C[x1 , ..., xn , x−1 −1

1 , ..., xn ]
está contenido en RL.
Demostración. Sea P ∈ C[x1 , ..., xn , x−1 −1
1 , ..., xn ] no nulo. Entonces exis-
m
te un monomio x con cada componente de m suficientemente
grandes, tal que xm P ∈ C[x1 , ..., xn ]. Como

C[x1 , ..., xn ] ⊆ C[x1 , ..., xn , x−1 −1 −1 −1

1 , ..., xn ] ⊆ C[[x1 , ..., xn , x1 , ..., xn ]]

se tiene que P ∈ RL. OMC

Proposición. RL es un submódulo de L.
Demostración. Tenemos que comprobar

1. RL es un subgrupo aditivo de L.

2. Para cada s ∈ RL y todo P ∈ C[x1 , ..., xn , x−1 −1

1 , ..., xn ] se tiene que
sP ∈ RL.

Veámoslo.
76 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

1. Primeramente, 1 ∈ RL pues 1 ∈ C[x1 , ..., xn , x−1 −1

1 , ..., xn ] ⊆ RL.
Ahora, dadas s, s′ ∈ RL, existen P, Q, P ′ , Q′ polinomios normales
en C[x1 , ..., xn ] con Q y Q′ no nulos y tales que Qs = P y Q′ s′ =
P ′ . Multiplicando por Q y Q′ respectivamente, (QQ′ )s = Q′ P y
(Q′ Q)s′ = QP ′ . Restando ambas expresiones,

(QQ′ )(s − s′ ) = (Q′ P − QP ′ )

Ası́, s−s′ es una serie racional pues hemos encontrado F = QQ′

y G = Q′ P − QP ′ tales que s − s′ = G/F .

2. Tomemos s ∈ RL y P ∈ C[x1 , ..., xn , x−1 −1

1 , ..., xn ]. Entonces exis-
ten G no nulo y F polinomios normales con Gs = F . Si P = 0
entonces P s = 0 y 0 ∈ RL. Si suponemos P distinto de cero,
G(P s) = P F es un polinomio de Laurent, entonces multipli-
cando ambos miembros por un monomio con exponentes su-
ficientemente grandes tenemos que los nuevos (P F )′ , G′ son
polinomios ordinarios que cumplen

G′ (P s) = (P F )′ =⇒ P s ∈ RL

Ası́, probamos que para todo s ∈ RL y todo P polinomio de

Luarent se cumple P s ∈ RL.

OMC

5.3. Conos.
Entendemos por semirrecta un segmento que parte de un punto
p y se prolonga indefinidamente en un único sentido,

También nos referiremos a ellas como rayos 1 .

Definición. Un cono en Rn es la envolvente convexa de un conjunto

de rayos que parten de un mismo vértice. Diremos que el cono está
1
La palabra rayo en este contexto poco tiene que ver con su significado usual.
En realidad se trata de una mala traducción del inglés, donde semirrecta se dice
ray.
5.3. CONOS. 77

generado por dichos rayos.

Observación. En R2 , un cono es el sector circular que contiene a

todos los rayos con vértice común p0

p0

En R3 obtenemos un prisma,

p0

entendiendo que cuando el número de rayos tiende a infinito, la en-

volvente convexa resultante es un cono de verdad.

Definición. Fijemos un vértice p0 que sea un punto reticular de

Rn . Si consideramos S un conjunto finito de rayos que parten de
p0 y cada rayo de S tiene al menos otro punto reticular distinto de
p0 , entonces la envolvente convexa de S se llama cono racional con
vértice p0 y escribimos

Cp0 = conv(S)

 Ejemplo. En R2 tomemos p0 = (1, 1) y consideramos los rayos: r1

que pasa por (2, 1), r2 que pasa por (2, 2) y r3 que pasa por (3, 2). La
envolvente convexa de p0 y r1 , r2 , r3 es un cono racional con vértice
(1, 1).
78 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

C(1,1)

p0

Si estamos trabajando en Rn , un hiperplano afı́n de Rn será un

subespacio afı́n de dimensión n − 1. Está claro que un hiperplano
H ⊆ Rn divide al propio Rn en tres partes: el propio H, y los puntos
a cada lado de H.

Definición. Si H ⊆ Rn es un hiperplano afı́n, un semiespacio es la

región cerrada que hay a cada lado del hiperplano. Si H = {x ∈ Rn :
a1 x1 + · · · + an xn = b} entonces los dos semiespacios serán
H≥ = {x ∈ Rn : a1 x1 + · · · + an xn ≥ b}
H≤ = {x ∈ Rn : a1 x1 + · · · + an xn ≤ b}
Definición. Un cono Cp0 se dice que es positivo si existe un hiper-
plano H que pasa por p0 y deja a todo Cp0 en uno (y sólo uno) de los
semiespacios de H.

Definición. Si Cp0 es un cono positivo, las aristas de Cp0 son los

rayos de S que son imprescindibles para generar Cp0 , es decir, son
los rayos que si se eliminan de S, la envolvente convexa resultante
está estrictamente contenida en Cp0 .

 Ejemplo. En el último ejemplo, las aristas de C(1,1) son r1 y r3 , r2

no es necesario para generar C(1,1) .

Si el vértice de un cono es el origen, escribimos simplemente

C y lo llamamos cono vectorial pues en realidad es un subespacio
vectorial de Rn . Observa que cualquier cono Cp0 se puede escribir
como Cp0 = p0 + C. Aquı́, C recibe el nombre de cono de direcciones
de Cp0 en analogı́a con la geometrı́a afı́n (en realidad, en geometrı́a
~ para indicar que C
hubiéramos escrito Cp0 = p0 + C ~ es el espacio de
direcciones).
5.3. CONOS. 79

Mezclamos ahora todo un poco.

Definición. El soporte de una serie de Laurent s se define como el

cono vectorial generado por todos los rayos de origen 0 y que pasan
por los puntos determinados por los exponentes de los monomios
de Laurent que aparecen en s.

5.3.1. Conos regulares.

Volvamos sobre el retı́culo Zn . Lo podemos ver como un Z−módulo
de dimensión n, y como tal podemos dar un sistema de generadores
o una base. Supongamos que B = {e1 , ..., en } es una base de Zn (luego
ei tiene coordenadas enteras), es decir,

Zn = {a1 e1 + · · · + an en : ai ∈ Z}

Escribamos dichos vectores en filas de una matriz n × n (no es es-

cribir las coordenadas de cada ei en la base B, simplemente juntar
todos los vectores en una matriz). Sea An ∈ Mn (Z) dicha matriz,
 
− e1 −
 
An (B) =  ... ... ... 
− en −

Definición. En las condiciones anteriores, decimos que un cono Cp0

es regular si

1. Podemos encontrar una base B de Zn cuyos elementos generan

C p0 .

2. Para dicha base, det(An (B)) = ±1.

Observación. Si Cp0 es el cono regular asociado a la base B, evi-

dentemente los n elementos de B son también sus aristas. Observa
también que todo cono regular es vectorial.

Definición. Sea B = {e1 , ..., en } una base de Zn y C su cono regular

asociado. Llamamos caras m−dimensionales de C a los conos gene-
rados por cualquier subconjunto S ⊆ B con |S| = m < n. Si m = n − 1
entonces hablamos de facetas de C.
80 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

Definición. Sean C y C ′ dos conos regulares. Decimos que son ad-

yacentes si su intersección es una faceta de cada uno (en realidad
estarı́a mejor dicho común a ambos). Un complejo de conos regula-
res es un conjunto finito de conos regulares donde la intersección
de ellos dos a dos es o bien una faceta (adyacentes) o bien el origen.

Teorema. Todo cono vectorial racional positivo C se puede expresar,

no de manera única, como unión de ciertos conos de un complejo
de conos regulares.
Demostración. Sea C un cono vectorial racional positivo. Por ser C
un racional, está generado por un conjunto finito de aristas, di-
gamos m. Para cada arista, sea vi un vector director de la misma,
1 ≤ i ≤ m. Sea V ⊆ {v1 , ..., vm } un subconjunto que sea base del
espacio vectorial L(v1 , ..., vm ). Las aristas asociadas a los elementos
de V forman un cono regular. Si este cono regular resulta ser C, he-
mos terminado. Sino, tomamos una arista externa al cono regular
con vector director vx1 . Podemos remplazar algún v1 por vx1 con un
poco de cuidado. Conseguimos ası́ otra base y sus aristas corres-
pondientes formarán otro cono regular. Ası́, los dos conos regulares
que hemos construido tienen en común una faceta (difieren en el
vector vi cambiado por vx1 ). Si la unión de estos dos conos es C, he-
mos terminado. Sino, basta repetir el proceso tomando otra arista
externa y cambiando la base. OMC
La interpretación práctica del teorema es que podemos entender
el cono C como una suma algebraica de conos regulares.

 Ejemplo. Situémonos en R2 y consideramos el cono vectorial dado

por los rayos asociados a los vectores v1 = (1, 0) y v2 = (1, 2),

(1, 2)

(1, 1)
(1, 0)

Sean también C1 y C2 los conos vectoriales de aristas (1, 0), (1, 1) y

(1, 1), (1, 2) respectivamente. El cono C no es regular pues si B =
{(1, 0), (1, 2)} se tiene que
 
1 0
A2 (B) = =⇒ det(A2 (B)) = 2 6= ±1
1 2
5.3. CONOS. 81

Se comprueba igual que C1 y C2 sı́ son regulares. Está claro que

C C1 ∪ C2 pero nos sobra el rayo de vector director v3 = (1, 1) para
que se de la igualdad. Si D es el cono 1−dimensional generado por
v3 entonces una escritura correcta es

C = C1 + C2 − D

Esto nos da, según el teorema anterior, una descomposición de C

en suma de conos regulares, pues

C = {C1 , C2 , D}

es un complejo de conos regulares. Según el teorema, esta escritura

no es única: tomamos ahora los vectores u1 = (0, 1) y u2 = (1, 2) y
consideramos el cono C ′ generado por v1 y u1 , el cono C3 generado
por v2 y u2 ; y D′ el generado por u2 . Entonces

C = C ′ − C3 + D ′

Definición. Sea C un cono vectorial racional y positivo. Su serie

indicatriz reticular es la serie de Laurent suma de todos los mono-
mios con coeficiente uno determinados por los puntos reticulares
que están dentro de C. En el caso en que C sea un cono regular
asociado a la base B, esta serie se llama expresión racional de la
serie generatriz de C y resulta ser
1
PC (x) = (5.1)
(1 − xa111 · · · xan1n ) · · · (1 − xa1n1 · · · xannn )

donde aij es el elemento (i, j) de la matriz An (B).

Si estamos en R2 , llamamos cuadrante a cada una de las cuatro

regiones que delimitan los ejes. En R3 tenemos ocho regiones que
delimitan los tres planos coordenados y los llamamos octantes. En
general, para Rn tendremos 2n regiones delimitadas por los n hiper-
planos coordenados que llamamos hiperoctantes.

Si C es el cono que coincide con el primer hiperoctante de Rn en-

tonces PC toma la forma
1
PC (x) = (5.2)
(1 − x1 ) · · · (1 − xn )
82 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

pues resulta B = {(1, 0, ..., 0), ..., (0, 0, ..., 1)} y por tanto An (B) = In .
Podemos entender (5.2) como la suma de la serie geométrica en n
variables.

Ası́, si C está expresado como suma algebraica de conos regulares,

su serie indicatriz reticular se puede expresar como suma de fun-
ciones racionales (justamente la suma de cada expresión racional
de la serie generatriz de cada cono regular). En vistas del ejemplo
anterior, uno podrı́a pensar que si C se expresa de dos formas dis-
tintas como suma de conos regulares, podemos también obtener
expresiones racionales distintas. He aquı́ el quid de la cuestión: la
expresión racional de C depende únicamente de C y no de cómo se
exprese como suma.

Podemos generalizar la definición de serie reticular a cualquier

cono Cp0 que no sea vectorial,

Definición. Sea Cp0 = p0 + C un cono racional y positivo de vértice

p0 . Definimos
1. La serie generatriz reticular de Cp0 como la serie suma de los
monomios con coeficiente uno de los puntos reticulares de Cp0 .
Escribimos PCp0 .
2. La expresión racional de Cp0 como
PC p 0 = M p 0 · PC
donde Mp0 es el monomio asociado al punto p0 (observa que
reciben el mismo nombre).
 Ejemplo. Tomemos el cuadrilátero en R2 de vértices p0 (0, 0), p1 (0, 2),
p2 (4, 2) y p3 (2, 0).

p1 p2

p0
p3

Podemos entender que tenemos cuatro conos de vértices p0 , p1 , p2 y

p3 . Construyamos la expresión racional de cada uno.
5.4. TEOREMA DE BRION. 83

El cono de vértice p0 es vectorial y una base B0 = {(1, 0), (0, 1)} hace
que sea regular. Su expresión racional será por tanto
1
PCp0 (x) =
(1 − x)(1 − y)

coherente con que Cp0 sea el primer cuadrante de R2 . Para p1 tene-

mos
C p1 = p 1 + C 1
donde C1 es regular para la base B1 = {(1, 0), (0, −1)}. Entonces por
un lado
1
PC1 (x) =
(1 − x)(1 − y −1 )
y por otro Mp1 (x) = y 2 luego

y2
PCp1 (x) =
(1 − x)(1 − y −1 )
Para p2 tenemos Cp2 = p2 + C2 donde C2 es regular con expresión
racional
1
PC2 (x) =
(1 − x )(1 − x−1 y −1 )
−1

asociado a la base B2 = {(−1, 0), (−1, −1)}. Como Mp2 (x) = x4 y 2 en-
tonces
x4 y 2
PCp2 (x) =
(1 − x−1 )(1 − x−1 y −1 )
Por último, para p3 se tiene

x2
PCp3 (x) =
(1 − x−1 )(1 − xy)
¿qué base hemos usado? ¿por qué?

5.4. Teorema de Brion.

Volvamos sobre los politopos reticulares. Si Q es un politopo re-
ticular, dijimos que su polinomio indicador reticular contiene la in-
formación de qué puntos reticulares se encuentran dentro de Q.
Necesitábamos por tanto una manera eficiente de calcular PQ . Para
ello, tenemos el teorema de Brion.
84 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

Teorema (de Brion). Si Q es un politopo reticular, su polinomio

indicador es exactamente la suma extendida a cada vértice de Q de
las funciones racionales PCp ,
X
PQ (x) = PCp (x)
p

El objetivo de esta sección es ser capaces de demostrar este teo-

rema. Para ello, todavı́a necesitamos introducir otros conceptos.

Definición. Definimos las aplicación F : RL −→ C(x) como la única

que envı́a cada serie de Laurent s ∈ RL en su función racional que
la define, es decir,
P
F (s) = con P, Q ∈ C[x1 , ..., xn ] y s = P/Q
Q
Nos referiremos a F como la aplicación.

Proposición. La aplicación F es un homomorfismo de C[x, x−1 ]−módu-

los.
Demostración. Primeramente, hay que comprobar que F está bien
definida. Tomemos s ∈ RL y supongamos

P P′
F (s) = y F (s) = ′
Q Q
Entonces

Qs = P y Q′ s = P ′ =⇒ (Q′ Q)s = Q′ P y (QQ′ )s = QP ′

Como QQ′ = Q′ Q han de ser iguales Q′ P y QP ′ . Al ser C[x] un

dominio de integridad, P/Q y P ′ /Q′ son la misma función racio-
nal. Para comprobar que F es efectivamente un homomorfismo de
módulos, actuamos igual que probar que es lineal: sean s, r ∈ RL y
P, Q ∈ C[x, x−1 ], y veamos que

F (P r + Qs) = P F (r) + QF (s)

Como r y s son series racionales, existen F̃ , G, H, K polinomios nor-

males, G y H no nulos, y tales que Gr = F̃ y Hs = K, Entonces

(GH)(P r + Qs) = (H F̃ )P + (GK)Q

5.4. TEOREMA DE BRION. 85

Multiplicando ambos miembros por xm y xn de grados suficiente-

mente altos obtenemos
G′ H ′ (P r + Qs) = (H ′ F̃ ′ )P + (G′ K ′ )Q
donde
G′ = Gxm , H ′ = Hxn , F̃ ′ = F̃ xm , K ′ = Kxn
y G′ , H ′ , F̃ ′ , K ′ ∈ C[x]. Ası́,
(H ′ F̃ ′ )P + (G′ K ′ )Q F̃ K
F (P r + Qs) = ′ ′
= P + Q = P F (r) + QF (s)
HG G H
OMC
Definición. Un cono racional en Rn es simplicial si es de la forma
n
X
C p0 = p 0 + λi v i
i=1

donde λi ≥ 0 y v1 , ..., vn ∈ Zn son linealmente independientes.

Teorema. Sea Cp0 un cono simplicial en Rn . Hay un homomorfismo

de L−módulos
F : C[x, x−1 ] −→ C(x1 , ..., xn )
tal que F (PCp0 ) = PCp0 .
Demostración. El homomorfismo es exactamente el de la proposi-
ción anterior restringido a C[x, x−1 ]. Sea Cp0 un cono simplicial
Cp0 = p0 + L(v1 , ..., vn )
Sabemos que
n
Y
(1 − xvi )PCp0 = Mp0
i=1

es la expresión racional de Cp0 . Además, para cada s ∈ RL hay un

polinomio no nulo Q tal que Qs = P para algún P ∈ C[x1 , ..., xn ]. Si
definimos
F (T ) = P/Q ∈ C(x1 , ..., xn )
entonces F (T ) no depende de Q. Como F está bien definido,
P M p0
=
Q (1 − xv1 ) · · · (1 − xvn )
OMC
86 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

Definición. Un sı́mplice es un politopo que resulta de considerar la

envolvente convexa de un número finito de puntos afı́nmente inde-
pendientes en Rn . Dichos puntos los llamaremos vértices.

Observación. Puede parecer que esta definición es igual que la de

politopo reticular. La única diferencia es que ahora no pedimos que
los puntos sean de Zn .

 Ejemplo. Definimos la dimensión de un sı́mplice como la dimen-

sión del subespacio afı́n que generan. Un punto es un sı́mplice
de dimensión 0. Un segmento es un sı́mplice de dimensión 1, un
triángulo de dimensión 2 y un tetraedro de dimensión 3.

Cuidado ahora con la definición de cara. No se corresponde total-

mente con el lenguaje coloquial. Si tienes un cubo a mano, contarı́as
que tiene 6 caras pero sin embargo tiene 28 .

Definición. Si p0 , ..., pr son r+1 puntos afı́nmente independientes de

Rn y S = conv(p0 , ..., pr ) es el sı́mplice que los contiene, una cara de
S es el sı́mplice asociado a cualquier subconjunto A ⊆ P({p0 , ..., pr }),
es decir, la envolvente convexa de cualquier subconjunto de partes
de {p0 , ..., pr }.

Observación. El alumno menos torpe se habrá dado cuenta de que

∅ ∈ P({p0 , ..., pr }) pero no tiene sentido hablar de la envolvente con-
vexa del vacı́o,¿o si? Si el lector ha cursado Geometrı́a Proyectiva
reconocerá lo siguiente: se conviene en que el vacı́o es un sı́mplice
de dimensión −1.

5.4.1. Conos tangentes.

Intentemos ahora comprender lo que es un cono tangente. De
manera informal, lo vamos a definir de forma recursiva sobre las
caras del sı́mplice S = conv(p0 , ..., pr ). Sea F una cara de S.
1. Si F = ∅ entonces su cono tangente será el propio sı́mplice S.
2. Si F = p es un vértice, el cono tangente a p es el generado por
todas las aristas de S que confluyen en p.
3. Si F es una arista, el cono tangente a dicha arista es la unión
de los conos tangentes a los vértices en dicha arista.
5.4. TEOREMA DE BRION. 87

4. Si F = S entonces el cono tangente es todo el semiespacio

donde está S.
Obtenemos ası́ la siguiente definición,

Definición. Si S es un sı́mplice y F una cara del mismo, el cono

tangente a F es la intersección de todos los semiespacios determi-
nados por las facetas que contienen a F .

 Ejemplo. Tomemos los puntos p0 (0, 0), p1 (2, 0) y p2 (3/2, 1). El sı́mpli-
ce S que tiene como vértices estos tres puntos es
p2

p0 p1

Si tomamos F = ∅ entonces el cono tangente a F es el propio S. Si

elegimos un vértice por ejemplo p0 , el cono tangente a F = p0 es

p2

p0 p1

Por último, eligiendo la arista F = p0 p1 y F = S tenemos respectiva-

mente

p2
p2

p0 p1
p0 p1
88 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

Veamos el último resultado necesario para demostrar el teorema

de Brion,

Teorema. Si S es un sı́mplice entonces

X
0= (−1)dim(G) PCG
G

donde la suma se realiza sobre las caras G de S y PCG es la serie

generatriz reticular del cono tangente a G (el cono es CG ).

Demostración. Consideramos el coeficiente de xm para algún m ∈

Zn de la suma de la derecha. Sea F la cara de menor dimensión en
cuyo cono tangente está m. Ası́ mismo, m está en el cono tangente
a cualquier cara G que contenga a F , de las cuales hay exactamente
 
n−m
(5.3)
k

de dimensión m + k si 0 ≤ k ≤ n − m. Entonces en la suma, el

coeficiente de xm es (1 − 1)n−m = 0 (o (−1 + 1)). Si desarrollamos
(1 − 1)n−m por (2.1) tenemos

X
n−m
n−m

n−m
(1 − 1) = (−1)i = 0
i=0
i

Como en total hay n − m + 1 caras de diferentes dimensiones y, para

cada dimensión k, hay (5.3) caras que contienen a m, se tiene que

X
n−m
n−m
 X
0= (−1)i = (−1)dim(G)
i=0
i G⊇F

OMC

Con este teorema podemos demostrar una versión del teorema de

Brion para politopos reticulares (hay una versión para un sı́mplice
general).

Demostración del teorema de Brion. Apliquemos la función F que

venı́amos usando a la igualdad
X
0= (−1)dim(G) PCG
G
5.5. EXPRESAR UN CONO COMO SUMA DE CONOS REGULARES.89

Se cumple (es fácil probarlo) que F (PCG ) = 0 excepto cuando G = ∅

o cuando F es un vértice, que en este caso F (PCG ) = MF (monomio
asociado al vértice G). Entonces
X
0 = −PQ (x) + PCp
p

donde la suma se realiza sobre los vértices p de Q. OMC

El caso general del teorema no nos interesa.

5.5. Expresar un cono como suma de co-

nos regulares.
El problema de escribir un cono cualquiera como suma de conos
regulares es factible para n = 2. Pero para poder entender el proce-
so, necesitamos conocer las fracciones continuas y cómo expresar
un número x como una fracción continua simple.

Observación. Si Cp0 es un cono de origen p0 , sabemos que lo pode-

mos escribir como
C p0 = p 0 + C 0
donde C0 es un cono que podemos hacer vectorial si tenemos cuida-
do dando sus generadores. Para cada rayo que salga de p0 , podemos
dar las coordenadas de su vector director d0 bien con origen en p0
o bien con origen en 0. Dándolas desde el origen, conseguimos que
C0 sea un cono vectorial que luego trasladamos hasta p0 . Ası́, lla-
mamos vectores directores primitivos de un cono Cp0 a los vectores
directores del cono vectorial C0 dados desde el origen y con el módu-
lo de sus coordenadas lo más pequeño posible.

 Ejemplo. Consideramos el cono en R3 de centro p0 = (0, 0, 0) y de

generadores u0 = (2, 0, 0), v0 = (0, 2, 0), w0 = (0, 0, 2). Los vectores di-
rectores primitivos de C(0,0,0) son ũ0 = (1, 0, 0), ṽ0 = (0, 1, 0) y w̃0 (0, 0, 1).

5.5.1. Fracciones continuas.

Si x es cualquier número real, lo podemos expresar en su forma
decimal como hemos aprendido desde pequeños. Sin embargo, al-
gunos también aprendimos los números mixtos.
90 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

Definición. Un número mixto es una expresión de la forma

b
A
c
donde A, b, c ∈ Z, b < c y mcd(b, c) = 1.

 [Link] fracción 12/9 la podemos reducir a 4/3 pero también

la podemos expresar como
1
1
3

La manera práctica de entender A cb es A + cb . Podemos utilizar

números mixtos dentro de números mixtos,
5 1
= 1
12 221
2

pues 2 21 = 5/2, 2 5/2

1
= 12/5 y 1
12/5
= 5/12. Conseguimos ası́ una torre
de números mixtos.

Definición. Una fracción continua simple es una expresión de la

forma
1
a1 +
a2 + a3 1+ 1
..
.
donde a1 ∈ Z y ai ∈ N ∪ {0} si i > 1. Si no pedimos que todos los
numeradores sean 1, hablamos solamente de fracciones continuas.

Observación. La notación de fracciones es engorrosa. Para fraccio-

nes continuas simples, escribimos

[a1 ; a2 , a3 , ...]

 Ejemplo. Podemos escribir 59/11 como

59 4 1 1 1 1
= 5 = 5 + 11 = 5 + 3 =5+ 1 =5+
11 11 4
2+ 4
2+ 4 2 + 1+1 1
3 3

o simplemente [5; 2, 1, 3]. Para −81/25 podemos escribir

81 19 1 1 1
− = −4 = −4 + 25 = −4 + 6 = −4 +
25 25 19
1 + 19 1 + 3+1 1
6
5.5. EXPRESAR UN CONO COMO SUMA DE CONOS REGULARES.91

Observa que el último número que aparece es el denominador de la

última fracción.

Observación. Todo número real x admite una representación en

fracción continua simple. En particular,

1. x tiene una representación como fracción continua simple fi-

nita si, y sólo si, x ∈ Q.

2. x tiene una representación como fracción continua simple in-

finita si, y sólo si, x ∈ I.

Demostración. En efecto, si x ∈ R, lo podemos escribir como [x]+d(x)

donde d(x) es la parte decimal de x. Entonces [x] = a1 y solamente
nos interesa representar como fracción continua la parte decimal.
Si x es racional, tiene parte decimal finita luego el algoritmo para
calcular las fracciones simples termina. Si x fuera irracional, tiene
parte decimal infinita. OMC

Cómo calcular una fracción continua simple.

El método práctico de calcular la fracción continua de un número
racional x = p/q es el siguiente:

1. El valor a1 es simplemente la parte entera de p/q. Sea r1 el resto

de dividir q entre p.

2. Aplicando la división euclı́dea, podemos escribir

p = r1 a2 + r2

luego a2 será el cociente de dividir p entre r1 .

3. En general, rk−2 = rk−1 ak + rk luego

rk−2 rk−1
rk ak

nos proporciona ak para k = 3, 4, ....

4. Paramos cuando el resto obtenido sea cero.

 92 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

 Ejemplo. Aplicando el algoritmo a 59/11,

 
59
a1 = =5
11

El resto de dividir 59 entre 11 es r1 = 4. Ahora,

11 = 4 · 2 + 3 =⇒ a2 = 2 y r2 = 3

Continuamos
4 = 3 · 1 + 1 =⇒ a3 = 1 y r3 = 1
Por último,
3 = 1 · 3 + 0 =⇒ a4 = 3 y r4 = 0
Entonces terminamos y 59/11 = [5; 2, 1, 3]. ¿Podemos implementar
este algoritmo en Matlab? ¿Podemos calcular su complejidad?
1 function a = funcionContinua ( p , q )
2 r (1) = p; r (2) = q;
3 i =2;
4 while ( r ( i ) ˜= 0)
5 %calcula los restos
6 r ( i +1) = mod( r ( i −1) , r ( i ) ) ;
7 %despejando, ai+1 = ri−1r−r i
i+1

8 q ( i +1) = ( r ( i −1)−r ( i +1) ) /r ( i ) ;

9 i = i +1;
10 end
11 a = q ( 3 : length ( q ) ) ;

Al ir calculando los sucesivos valores de an , podemos ir escri-

biendo las fracciones que vamos obteniendo,
1 1
r1 = a1 , r2 = a1 + , ..., rn = a1 +
a2 a2 + a3 1+ 1
..
.
Proposición. Para calcular rn con n > 1 basta reemplazar en la
expresión de rn−1 el valor an−1 por an−1 + n1 .
Demostración. Pongamos P0 = 0 y Q0 = 1. Podemos representar cada
rk como
1
a1 P1 a1 + a2 a2 a1 + 1 a2 P1 + P0
r1 = = , r2 = = =
1 Q1 1 a2 · 1 + 0 a2 Q1 + Q0
5.5. EXPRESAR UN CONO COMO SUMA DE CONOS REGULARES.93
 
1
a2 + a3
P 1 + P0 a3 P2 + P1 P3
r3 =   = =
a2 + 1
Q1 + Q0 a3 Q 2 + Q 1 Q3
a3

y en general,
an Pn−1 + Pn−2
rn =
an Qn−1 + Qn−2
luego tenemos las expresiones de recurrencia

Pn = an Pn−1 + Pn−2 con P0 = 1

(5.4)
Qn = an Qn−1 + Qn−2 con Q0 = 0

si n ≥ 2. OMC

Definición. En las condiciones de la proposición anterior, llamamos

convergentes o aproximantes de x ∈ R a las sucesivas fracciones
r1 , r2 , ..., rn , es decir,

P1
r 1 = a1 = = [a1 ]
Q1
1 P2
r2 = a1 + = = [a1 ; a2 ]
a2 Q2
1 P3
r3 = a1 + 1 = = [a1 ; a2 , a3 ]
a2 + a3 Q3
..
.

 Ejemplo. Podemos escribir 17/10 como

17 1
=1+ = [1; 1, 2, 3]
10 1 + 2+1 1
3

Sus aproximantes son

r1 = 1 = [1]
1
r2 = 1 + = [1; 1]
1
1 5
r3 = 1 + 1 = = [1; 1, 1, 2]
1+ 2 3

y obviamente r4 = 17/10 = [1; 1, 2, 3].

 94 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

Observación (método práctico). La manera práctica de calcular

r1 , ..., rn es usando (5.4) y construyendo una tabla de aproximantes
de la forma
n 1 2 3 ··· n
an a1 a2 a3 · · · an
Pn 0 1 P 1 P 2 P 3 · · · Pn
Qn 1 0 Q1 Q2 Q3 · · · Qn
972
 Ejemplo. La fracción 421 admite la representación en fracción
continua como [2; 3, 4, 5, 6]. La tabla de aproximantes la construimos
con (5.4),
P1 2
r1 = =
Q1 1
Ahora, P2 = 3 · 2 + 1 y Q2 = 3 · 1 + 0 luego r2 = 7/3. Ası́,
P3 4·7+2 30 P4 5 · 30 + 7
= = , =
Q3 4·3+1 13 Q4 5 · 13 + 68
P5 6 · 157 + 30 972
= =
Q5 6 · 68 + 13 421
La tabla serı́a
n 1 2 3 4 5
an 2 3 4 5 6
Pn 0 1 2 7 30 157 972
Qn 1 3 13 68 421

1 function A = tablaAproximantes ( v )
2 %v es un vector con los coeficientes de las fracciones continuas
3 %Inicializamos los vectores para almacenar P y Q
4 n = length ( v ) ;
5 P = zeros ( n, 1 ) ;
6 Q = zeros ( n, 1 ) ;
7 %Las condiciones iniciales, Matlab empieza los vectores
8 %en 1, luego P0 en la teorı́a es P1 en Matlab
9 P ( 1 ) =1; P ( 2 ) =v ( 1 ) ; Q( 2 ) =1;
10 for k=3:n+1 %cuidado
11 P ( k ) = v ( k−1) ∗P ( k−1)+P ( k−2) ;
12 Q( k ) = v ( k−1) ∗Q( k−1)+Q( k−2) ;
13 end
14 %Construimos la matriz (solamente la última parte)
15 %Cuidado con los ı́ndices
 5.5. EXPRESAR UN CONO COMO SUMA DE CONOS REGULARES.95

16 A = zeros ( 4 ,n ) ;
17 A( 1 , 1 :n ) = 1:n ;
18 A( 2 , 1 :n ) = v ( 1 : n ) ;
19 A( 3 , 1 :n ) = P ( 2 : n+1) ;
20 A( 4 , 1 :n ) = Q( 2 : n+1) ;

Combinando las dos funciones que hemos visto para fracciones

continuas,
1 >> v = funcionContinua (3803 ,3607)
2 v =
3

4 1 18 2 2 12 1 2
5

6 >> A = tablaAproximantes ( v )
7 A =
8

9 1 2 3 4 5 6 7
10 1 18 2 2 12 1 2
11 1 19 39 97 1203 1300 3803
12 1 18 37 92 1141 1233 3607

5.5.2. Conos y fracciones continuas.

Saber calcular fracciones continuas nos sirve para poder des-
componer cualquier cono Cp0 en dimensión 2 como suma de conos
regulares. El proceso consiste en escribir Cp0 = p0 + C0 es descom-
poner C0 . Para ello, tengamos en cuenta que todo cono C se puede
escribir (salvo cambios de signos) como suma de conos que sean la
envolvente convexa de los rayos (1, 0) y (d, e) con mcd(d, e) = 1. Lo
que buscamos es encontrar dos rayos (a1 , b1 ) y (a2 , b2 ) tales que su
envolvente convexa (el cono que generan) contenga al rayo (d, e) y
sea regular.

Para encontrar (a1 , b1 ) y (a2 , b2 ) basta escribir la fracción d/e como

fracción continua. Dos aproximantes consecutivos Pk /Qk y Pk+1 /Qk+1
generan dos rayos (Pk , Qk ) y (Pk+1 , Qk+1 ) cumpliendo que el cono que
generan es regular y contiene a (d, e).

 Ejemplo. El cono C generado por los rayos de origen (0, 0) y vec-

tores directores (1, 0) y (17, 10) no es regular. Buscamos un cono
96 CAPÍTULO 5. POLITOPOS Y SERIES DE LAURENT.

regular que contenga a (17, 10). Para ello,

17 1
=1+ = [1; 1, 2, 3]
10 1 + 2+1 1
3

Como aproximantes no podemos tomar a1 ni an luego

1 1 5
r2 = [1; 1] = 1 + = 2 y [1; 1, 2] = 1 + 1 = = r3
1 1+ 2
3

Ası́, el cono buscado es el generado por (5, 3) y (2, 1). En total, el

cono original lo escribimos como suma de 3. Sean

C1 generado por (1, 0), (2, 1)

C2 generado por (2, 1), (5, 3)
C3 generado por (2, 1)

y entonces C = C1 + C2 − C3 .
Capı́tulo 6

Principios básicos para

contar.

En este capı́tulo vamos a ver dos resultados fundamentales de

combinatoria: el principio del palomar y el principio de inclusión-
exclusion.

6.1. Principio del palomar.

Comencemos con un par de datos: (1) un ser humano tiene de
media 150000 pelos en la cabeza y, (2), en Valladolid viven unas
300000 personas. Ahora, prueba que en Valladolid hay al menos
dos personas con el mismo número de pelos.

La pregunta es, cuanto menos, surrealista. Y además parece bas-

tante difı́cil de responder. Pero, en realidad, es una pregunta muy
obvia. Veamos otro caso más sencillo: supongamos que hay palo-
mas y huecos en un palomar. Si cada paloma se mete en un hueco,
y hay más palomas que huecos, a la fuerza dos palomas han de
compartir hueco. En este capı́tulo, utilizaremos la notación n para
denotar al conjunto

n = {0, 1, ..., n − 1} si n ∈ N ∪ {0}

Lema (Principio del palomar). No existe ninguna aplicación

f : m −→ n

que sea inyectiva si m > n.

97
98 CAPÍTULO 6. PRINCIPIOS BÁSICOS PARA CONTAR.

Demostración. Por inducción sobre n,

Supongamos n = 0 (luego m > 0). No existen aplicaciones

f : m −→ 0 pues m 6= ∅ pero 0 = ∅. En particular, no hay
aplicaciones inyectivas de m en 0.

Ahora supongamos que es cierto para n, es decir, no existen

aplicaciones inyectivas

f : m −→ n

si m > n.

Para comprobar que es cierto para n + 1, probamos que si exis-

tiera f : m −→ n + 1 con m > n + 1 inyectiva, entonces también
existirı́a para n (que hemos supuesto imposible). Si m > n en-
tonces existe un l > n tal que m = l + 1. Supongamos, pues,
que sı́ existe f : m −→ n + 1 inyectiva. Por la definición de m, la
existencia de f equivale a la de

f˜ : l ∪ {l} −→ n ∪ {n}

Distingamos dos casos,

/ im(f˜|l ) (es decir justamente la imagen de l es n). En-

1. n ∈
tonces
f˜|l : l −→ n
es inyectiva, y como l > n se contradice la hipótesis de
inducción.
2. n ∈ im(f˜|l ). Entonces n = f˜(i) si i < l. Como f˜ es inyec-
tiva, sabemos que f (l) = j 6= f˜(i), es decir, f˜(l) = j < n.
Definamos g : l −→ n como

j si x = i
g(x) =
f˜(x) si 0 ≤ x < l, x 6= i

Como g la hemos definido a partir de f˜ que era inyectiva,

g también lo es, aunque l > n; esto contradice la hipótesis
de inducción.

OMC
6.1. PRINCIPIO DEL PALOMAR. 99

Con este resultado podemos dar respuesta a la pregunta de los

pelos: como en Valladolid hay más personas que pelos por cabeza,
al menos dos tienen que coincidir. En realidad, hay al menos
 
300000
=2
150000
personas con el mismo número de pelos.

Observación. Que una aplicación f : A −→ B no sea inyectiva sig-

nifica que existen a, b ∈ A tales que f (a) = f (b). Esto nos dice que
en muchos casos habrá que buscar cómo definir f para aplicar el
principio del palomar.

 Ejemplo. Parking de la UVa, debajo del aulario de Ciencias, en

plena convocatoria ordinaria: todo lleno de coches. Podemos asegu-
rar que hay dos coches tales que el número de coches de la misma
marca presentes en el parking es el mismo para los dos. Es decir,
existen c1 y c2 dos coches tales que

|M (c1 )| = |M (c2 )|

donde M (ci ) = {coches de la misma marca que ci }. ¿Por qué? Sea C

el conjunto de coches del parking, y sea

m : C −→ N ∪ {0}

la aplicación que asigna a cada coche c ∈ C el número de coches

distintos de c que son de su misma marca. Supongamos que hay
n coches. Si todos los coches son de la misma marca, m(c) = n − 1
para cada c ∈ C. Entonces dos coches cualesquiera resuelven el pro-
blema. Si no son todos de la misma marca, entonces m(c) < n − 1
para todo c ∈ C, es decir, m : C −→ n − 1 y estamos en condicio-
nes de aplicar el principio del palomar: existen dos coches distintos
c1 , c2 ∈ C tales que m(c1 ) = m(c2 ).

Proposición (Principio del palomar, 2ª versión). Sean m, n, p tres

números naturales. Si se desean colocar np + m objetos en n cajas,
alguna caja debe contener al menos p + 1 objetos.
Demostración. Si cada caja contiene como mucho p objetos, el núme-
ro total de objetos que podemos colocar es np < np + 1 ≤ np +
m. OMC
100 CAPÍTULO 6. PRINCIPIOS BÁSICOS PARA CONTAR.

Observación. Un enunciado aún más general es el siguiente: si se

desean colocar n objetos en m cajas, al menos una caja contiene al
menos lnm
m
objetos (⌈x⌉ es la función techo) y hay otra caja que tiene como mu-
cho jnk
m
objetos (⌊x⌋ es la función suelo). La función techo redondea x al en-
tero más próximo por exceso, y la función suelo por defecto.

 Ejemplo. El principio del palomar en informática. Podemos uti-

lizar este principio para asegurar que cualquier algoritmo de com-
presión sin pérdida que reduce el tamaño de un archivo de entrada
(como la palabra compresión sugiere) también hará que otro archivo
de entrada sea más grande. En efecto, si esto no fuera ası́, el con-
junto de todas las secuencias de longitud menor o igual que ℓ podrı́a
ponerse en biyección con el conjunto (de menor tamaño) de las se-
cuencias de longitud estrictamente menor que ℓ (pues el algoritmo
es sin pérdida), algo que contradice el principio del palomar.

6.2. Principio de inclusión-exclusión.

Proposición (Principio de inclusión-exclusión). Supongamos que
tenemos n conjuntos A1 , A2 , ..., An posiblemente con elementos en
común. Entonces el número total de elementos k que tienen entre
todos es igual a
k = k1 − k2 + k3 − · · · + (−1)n+1 kn
donde ki es la suma de los elementos que pertenecen a (por lo me-
nos) i conjuntos, 1 ≤ i ≤ n.
Demostración. Sea a ∈ A1 ∪ · · · ∪ An cualquiera. El número de veces
que a aparece en
k1 − k2 + k3 − · · · + (−1)n+1 kn
es        
n n n n+1 n
− + − · · · + (−1)
1 2 3 n
n


donde esta suma es exactamente 0 = 1. OMC
6.2. PRINCIPIO DE INCLUSIÓN-EXCLUSIÓN. 101

 Ejemplo. ¿Cuántos enteros del 1 al 100 no son divisibles por 2, 3

o 5? Sea S = {1, ..., 100} y consideramos los conjuntos

A2 = {x ∈ S : x es divisible por 2}
A3 = {x ∈ S : x es divisible por 3}
A5 = {x ∈ S : x es divisible por 5}

Evidentemente, |A1 | = 50, |A2 | = 33 y |A5 | = 20. Ahora bien, necesita-

mos contar las uniones de los conjuntos,

A6 = A2 ∪ A3 = {x ∈ S : x es divisible por 6}
A10 = A2 ∪ A5 = {x ∈ S : x es divisible por 10}
A15 = A3 ∪ A5 = {x ∈ S : x es divisible por 15}
A30 = A2 ∪ A3 ∪ A5 = {x ∈ S : x es divisible por 30}

con |A6 | = 16, |A10 | = 10, |A15 | = 6 y |A30 | = 3. Entonces el número

total es

k = 100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26

Observación. Este principio nos ayuda a contar cuántos objetos

hay que no cumplen ciertas propiedades. En la expresión

k = k1 − k2 + k3 − · · · + (−1)n+1 kn

el valor de k1 es siempre el número total de elementos, luego se pue-

de despejar k1 si fuera (o fuese) necesario.

 Ejemplo. En el grado de Matemáticas de cierta universidad, el

porcentaje de alumnos que aprueban Cálculo Infinitesimal (CI) es del
80 %, el porcentaje de alumnos que aprueban Investigación Opera-
tiva (IO) es del 85 %, y el 75 % aprueban ambas. Si se sabe que 45
alumnos han suspendido ambas, ¿cuántos alumnos hay en total ma-
triculados en las dos asignaturas? Sea S el conjunto de los, digamos
n, alumnos matriculados. Construimos los conjuntos

ACI = {x ∈ S : x ha aprobado CI}

AIO = {x ∈ S : x ha aprobado IO}
AL = ACI ∩ AIO = {x ∈ S : x ha aprobado CI e IO}

(A-sub L de Listos). Entonces

|ACI | = 0′ 8n, |AIO | = 0′ 85n, |AL | = 0′ 75n

102 CAPÍTULO 6. PRINCIPIOS BÁSICOS PARA CONTAR.

Aplicando el principio de inclusión-exclusión,

45 = n − (0′ 8n + 0′ 85n) − (0′ 75n)

45 = n − 0′ 95n
n = 45/0′ 005
n = 900 alumnos

Veamos una demostración alternativa al principio de inclusión-

exclusión más elegante.

Demostración. Pongamos A = A1 ∪ · · · ∪ An ⊆ S y sean B = S − A,

Bi = S −Ai si i = 1, ..., n. Podemos reescribir el principio de inclusión-
exclusión como X
|B| = (−1)|J| |AJ |
J⊆{1,...,n}

donde AJ se define como la intersección de los Ai tales que i ∈ J.

Consideramos la función indicatriz de X ⊆ S como

0 si a ∈ /X
1X (a) =
1 si a ∈ X

Estas funciones 1X pertenecen al anillo

Ap(S; R) = {f : S −→ R tal que f aplicación}

y por lo tanto cumplen

1. 1∅ (a) = 0 para cada a ∈ S.

2. 1S (a) = 1 para cada a ∈ S.

3. 1S−X = 1 − 1X

4. 1X∩Z = 1X 1Z

Ası́, podemos escribir

n
Y n
Y XY
1B = 1 Bi = (1 − 1Ai ) = (−1)|J| 1AJ
i=1 i=1 J i∈J

OMC
6.2. PRINCIPIO DE INCLUSIÓN-EXCLUSIÓN. 103

 Ejemplo. Calcular la cantidad de números primos menores o

iguales que un número N dado. Sea S = [1, N ] ∩ N el conjunto S =
{1, 2, ..., N }. Consideramos los conjuntos

Ai = {n ∈ S : n es múltiplo de pi }, i = 1, ..., r

√
donde pi son los números primos menores o iguales que N . El
número pedido será |B|+r−1. Para N = 125 necesitamos el conjunto
S = {1, 2, ..., 125} y los subconjuntos

A1 = {n ∈ S :n es múltiplo de 2}
A2 = {n ∈ S :n es múltiplo de 3}
A3 = {n ∈ S :n es múltiplo de 5}
A4 = {n ∈ S :n es múltiplo de 7}
A5 = {n ∈ S :n es múltiplo de 11}

y las posibles combinaciones de los productos de números primos

con resultado menor o igual que 125. En total obtenemos 21 con-
juntos,

A6 múltiplos de 6, A7 múltiplos de 10
A8 múltiplos de 14, A9 múltiplos de 22
A10 múltiplos de 15, A11 múltiplos de 21
A12 múltiplos de 33, A13 múltiplos de 35
A14 múltiplos de 55, A15 múltiplos de 77
A16 múltiplos de 30, A17 múltiplos de 42
A18 múltiplos de 66, A19 múltiplos de 105
A20 múltiplos de 70, A21 múltiplos de 110

Faltan muchas combinaciones que no interesan pues serı́an los

múltiplos de números mayores que 125. Necesitamos calcular el
cardinal de cada Ai , que hacemos como

 
125
|Ai | =
k

donde k = 2, 3, 5, 7, 11, 6, 10, ..., 110. Resumimos la información en la

siguiente tabla,
104 CAPÍTULO 6. PRINCIPIOS BÁSICOS PARA CONTAR.

i múltiplos de cardinal
1 2 62
2 3 41
3 5 25
4 7 17
5 11 11
6 2·3 20
7 2·5 12
8 2·7 8
9 2·11 5
10 3·5 8
11 3·7 5
12 3·11 3
13 5·7 3
14 5·11 2
15 7·11 1
16 2·3·5 4
17 2·3·7 2
18 2·3·11 1
19 2·5·7 1
20 2·5·11 1
21 3·5·7 1

luego hay
5 15 21
!
X X X
125 − Ai + Ai − Ai + 5 − 1 = 26 + 5 − 1 = 30
i=1 i=6 i=16

 Ejemplo. La función ϕ de Euler. Otra forma de probar la igualdad

Y 1

ϕ(n) = n 1−
pi
pi |n

es utilizando el principio de inclusión-exclusión. Si pi con i = 1, ..., r

son los primos menores o iguales que n, definimos el conjunto S =
{1, 2, ..., n} y los subconjuntos
Ai = {x ∈ S : x es múltiplo de pi }
entonces X n
ϕ(n) =
pJ
J⊆{1,...,r}
6.3. NÚMEROS DE STIRLING. 105

donde pJ es el producto de todos los pi tales que i ∈ J. El cardinal

de cada AJ es n/AJ y por lo tanto
Xr
1 X 1 n
ϕ(n) = n − + + · · · + (−1)r
p
i=1 i i6=j
pi pj p1 · · · pr
   
1 1
=n 1− ··· 1 −
p1 pr

 Ejemplo. El número de permutaciones de Sr que no tienen puntos

fijos. Tomamos los subconjuntos de Sr
Ai = {σ ∈ Sr : σ deja fijo el ı́ndice i}
Entonces el número n de permutaciones de Sr que no tienen puntos
fijos es
X    
|J| r r
n= (−1) |AJ | = r! − (r − 1)! + (r − 2)! + · · · + (−1)r (r − r)!
1 2
J⊆{1,...,r}

6.3. Números de Stirling.

Existen varias formas de definir los números de Stirling. La más
sencilla es la siguiente: supongamos que estamos trabajando con
el grupo Sn y queremos saber cuántas permutaciones σ ∈ Sn hay
que se descomponen en k ciclos disjuntos donde k ∈ N ∪ {0} es un
número fijo. Por ejemplo, si n = 5 y k = 2, tendrı́amos
(1 2 3 4)(5), (1 2 3 5)(4), (1 2 4 5)(3), (1 3 4 5)(2), (2 3 4 5)(1)
(1 2 3)(4 5), (1 2 4)(3 5), (1 3 4)(2 5), (2 3 4)(1 5), (1 2 5)(3 4)
(1 3 5)(2 4), (2 3 5)(1 4), (1 4 5)(2 3), (2 4 5)(1 3), (1 3 5)(1 2)
En total hay escritas 15 configuraciones. Pero en realidad hay más,
pues cada ciclo de longitud 4 equivale a 6, pues (1 2 3 4) representa
en realidad a
(1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 3 2), (1 4 3 2)
Igualmente, en cada 3−ciclo tenemos en realidad dos, luego
(5 ciclos longitud 5) · (6 ciclos que representa) = 30
(10 ciclos longitud 2) · (2 ciclos que representa) = 20
106 CAPÍTULO 6. PRINCIPIOS BÁSICOS PARA CONTAR.

Ası́, hay 50 permutaciones en S5 que se descomponen en 2 ciclos.

Definición. Llamamos número de Stirling de primera espacio sin

signo al número de permutaciones de Sn que se descomponen en k
ciclos. Escribimos n(n, k).

 Ejemplo. Antes hemos calculado s(5, 2) = 50.

Propiedades. Los números de Stirling de primera especie sin signo

cumplen

1. s(n, n) = 1. En efecto, la única permutación que se descompone

en n ciclos es la identidad.

2. s(n, 1) = (n − 1)! Esto es porque representa las permutaciones

de longitud n en Sn (que son (n − 1)!).

Por convenio se toma n(n, 0) = 0.

Proposición. Los números s(n, k) cumplen la relación

s(n + 1, k) = s(n, k − 1) + ns(n, k) (6.1)

Demostración. Pensemos. Si añadimos un elemento nuevo a una

configuración en ciclos, puede ocurrir

1. El elemento es invariante, es decir, forma un ciclo consigo mis-

mo. En este caso, estará acompañado de s(n, k − 1) formas dis-
tintas de distribución en ciclos.

2. Si el nuevo elemento se integra en los ya existentes, lo podemos

incluir en n lugares distintos, luego formará ns(n, k) configura-
ciones diferentes.

Sumando ambas posibilidades obtenemos el número total de con-

figuraciones. OMC

 Ejemplo. Estamos en S3 y añadimos el 4. Las posibles formas de

incluirlo son

(1)(2 3)(4), (2)(1 3)(4), (3)(1 2)(4), (1 4)(2)(3), (1)(2 4)(3), (1)(2)(3 4)
 6.3. NÚMEROS DE STIRLING. 107

Ası́, s(4, 3) = s(3, 2) + 3s(3, 3).

Con esta fórmula de recurrencia y teniendo en cuenta las pro-

piedades de s(n, k), obtenemos una forma de calcular los números
de Stirling, implementando la fórmula (6.1) en Matlab.
1 function s = s t i r l i n g ( n, k )
2 i f ( k==0) s =0;
3 else i f ( k==n ) s = 1;
4 else i f ( k==1) s = f a c t o r i a l ( n−1) ;
5 else s = s t i r l i n g ( n−1 ,k−1) + (n−1) ∗ s t i r l i n g ( n−1 ,k ) ;
6 end ; end ; end ; end

Los números que hemos definido se llaman sin signo porque son
todos positivos. Si tomamos como definición de números de Stirling
de primera especie otra, aparecen de manera natural los signos.

Definición. Los números de Stirling de primera especie (signados)

son los coeficientes de la expansión
n
X
(x)n = s(n, k)xk
k=0

donde (x)n = x(x − 1)(x − 2) · · · (x − n + 1) es el factorial descendente

de x ∈ C.

Observación. La relación entre s(n, k) y s(n, k) es

s(n, k) = |s(n, k)| = (−1)n−k s(n, k)

Además de los de primera especie, existen los números de Stir-

ling de segunda especie,

Definición. Los números de Stirling de segunda especie S(n, k) se

definen como la cantidad de maneras que existen de hacer una par-
tición de un conjunto de n elementos en k subconjuntos no vacı́os.

Proposición. Los números de Stirling de segunda especie cumplen

la relación
S(m + 1, r) = S(m, r − 1) + rS(m, r)
108 CAPÍTULO 6. PRINCIPIOS BÁSICOS PARA CONTAR.

Demostración. Dada una partición de los m + 1 elementos en r sub-

conjuntos no vacı́os disjuntos, tenemos dos posibilidades,

1. El elemento que hemos añadido forma él solo uno de los sub-
conjuntos, luego quedan r − 1 conjuntos formados por m ele-
mentos: S(m, r − 1).

2. El elemento añadido forma parte de uno de los r subconjuntos

que ya habı́a: rS(m, r) pues podemos colocar cada elemento en
uno de los r subconjuntos.

OMC

Propiedades. Los números de Stirling de segunda especie cumplen

1. S(m, 1) = 1

2. S(m, 2) = 2m−1 − 1


3. S(m, m − 1) = m2

4. S(m, m) = 1

Demostración. 1. Obvio pues la única manera de hacer una única

partición de un conjunto es poniendo todos en la misma.

2. Notemos primero que hay 2m pares ordenados de subconjuntos

complementarios A y B. En un caso A es el vacı́o, y en el otro
B es vacı́o, luego aún quedan 2m − 2 subconjuntos. Como no
nos importa el orden,

2m − 2
S(m, 2) = = 2m−1 − 1
2

3. Esto resulta de que al dividir m elementos entre m − 1 subcon-

juntos necesariamente uno ha de tener 2 elementos y los otros
m−2 tienen un único elemento. Luego basta elegir 2 elementos
entre m que hay.

4. La única manera de colocar m elementos en m subconjuntos

es que cada subconjunto tenga un elemento.
OMC
 6.3. NÚMEROS DE STIRLING. 109

Pruebe a implementar de manera recursiva los números de Stirling

de 2ª especie en Matlab.
1 function s = s t i r l i n g 2 a E s p e c i e (m, r )
2 i f ( r ==0)s =0;
3 else i f ( r==m) s =1;
4 else i f ( r ==1) s =1;
5 else s = s t i r l i n g 2 a E s p e c i e (m−1 , r −1)+r ∗
s t i r l i n g 2 a E s p e c i e (m−1 , r ) ;
6 end ; end ; end ; end

6.3.1. Funciones generatrices de los números de Stir-

ling.
Consideramos las funciones en las variables x, t siguientes,

X∞
1
F (x, t) = s(m, r)xm tr
m,r=0
m!
X∞
1
G(x, t) = S(m, r)xm tr
m,r=0
m!

Teorema. Considerando F y G,

1. Las series de potencias F y G son convergentes en un disco

abierto centrado en (0, 0).

2.
F (x, t) = (1 − x)−t = exp(− log(1 − x)t)
G(x, t) = exp((exp(x) − 1)t)

3. Si C(m, r) y D(m, r) son los coeficientes de xm tr en las series de

potencias respectivas
1 1 1 1
1 + x + x2 + x3 + · · · , 1 + x + x2 + x3 + · · ·
2 3 2! 3!
entonces los números de Stirling admiten la representación

m! m!
s(m, r) = C(m, r) y S(m, r) = D(m, r)
r! r!
110 CAPÍTULO 6. PRINCIPIOS BÁSICOS PARA CONTAR.

Demostración. Los desarrollos de Taylor de las funciones F y G son

∞
X   ∞
−t m −t m X s(m, r) m r
(1 − x) = (−1) x = x t = F (x, t)
m=0
m m=0
m!

∞ r x
X X∞
t (e − 1)r S(m, r) m r
exp((exp(x) − 1)t) = = x t = G(x, t)
r=0
r! r,m=0
m!

Con esto probamos 1 y 2. Para 3, notemos que podemos llegar a F

y G haciendo en
1 2 1 3
f (x) = ex = 1 + x + x + x + ···
2! 3!
las sustituciones
   
1 2 1 3 1 2 1 3
z = x + x + x + · · · t, z = x + x + x + · · · t
2 3 2! 3!

Obtenemos ası́ que, fijado un r, los monomios del tipo xm tr aparecen

sólo al hacer las sustituciones en el término
1 r
x
r!

En particular los coeficientes s(m,r)

m!
y S(m,r)
m!
de los monomios xm tr de
F y G son iguales a C(m, r)/r! y D(r, m)/r! respectivamente. OMC

6.3.2. Relaciones de reciprocidad.

Tomemos V el C−espacio vectorial de los polinomios de grado
≤ m en la variable t que se anulan en t = 0. Este espacio tiene
dimensión m pues
B = {tm , tm−1 , ..., t2 , t}
es una base de V . Otra base de V puede ser

B̃ = {t(t − 1) · · · (t − m + 1), t(t − 1) · · · (t − m + 2), ..., t(t − 1), t}

Podemos expresar el cambio de base de una a otra con los números

de Stirling.
6.3. NÚMEROS DE STIRLING. 111

Proposición. Se cumplen las relaciones

1. t(t − 1) · · · (t − j + 1) = s(j, j)tj − s(j, j − 1)tj−1 + · · · + (−1)j−1 s(j, 1)

2. tj = S(j, j)t(t − 1) · · · (t − j + 1) + S(j, j − 1)t(t − 1) · · · (t − j + 2) +

· · · + S(j, 1)t

Demostración. Para probar 1 basta hacer el cambio − por t en la

expresión (2.7). Para 2, notemos que si t > 0 y t ∈ N entonces tj es
el número de coloraciones de j casas con t colores; que cada colo-
ración da una partición del conjunto de casas en i ≤ j conjuntos; y
que para cada partición hay t(t − 1) · · · (t − i + 1) formas de colorear
los subconjuntos de la partición. OMC
Para terminar, escribamos las matrices de B y B̃,
 
−s(1, 1) 0 ··· 0
 −s(2, 1) s(2, 2) · · · 0 
 
M (B) =  .. .. . . .. 
 . . . . 
j
−s(m, 1) −s(m, 2) · · · (−1) s(m, j)
 
S(1, 1) 0 ··· 0
 S(2, 1) S(2, 2) ··· 0 
 
M (B̃) =  .. .. .. .. 
 . . . . 
S(m, 1) S(m, 2) · · · S(m, j)
Resulta que son inversas una de la otra.
112 CAPÍTULO 6. PRINCIPIOS BÁSICOS PARA CONTAR.
Apéndice A

Cuentas que no hemos hecho

explı́citamente en los apuntes
pero como nadie las va a
hacer pues aquı́ están.

Obtener la función generatriz de la sucesión de Fi-

bonacci.
Vamos a intentar encontrar la función generatriz de la sucesión
de Fibonacci, es decir, una función g tal que al desarrollarse en
series de potencias
g(x) = a0 + a1 x + a2 x2 + · · ·
los coeficientes aj sean exactamente los términos de la sucesión.
Como pista, sabemos que tiene que ser una función racional pues
la sucesión de Fibonacci es una recursión lineal.

La idea feliz es manipular la expresión

an = an−1 + an−2
para llegar a otra que se parezca a
g(x) = a0 + a1 x + a2 x2 + · · ·
Evidentemente, se da la igualdad
∞
X ∞
X ∞
X ∞
X
g(x) = an xn = (an−1 + an−2 )xn = an−1 xn + an−2 xn
n=0 n=0 n=0 n=0

113
 114 APÉNDICE A. CUENTAS

Ahora tenemos que sumar desde donde la recurrencia es válida.

Para el primer sumando será n = 1 y para el segundo, n = 2:
∞
! ∞
!
X X
0 n 0 1 n
g(x) = a−1 x + an−1 x + a−2 x + a−1 x + an−2 x
n=1 n=2

Ahora cambiamos los exponentes sumando y restando 1 (o 2) para

no cambiar la igualdad,
∞
! ∞
!
X X
g(x) = a−1 + an−1 xn−1+1 + a−2 + a−1 x + an−2 xn−2+2
n−1=1−1 n−2=2−2

Si realizamos los cambios n − 1 = n y n − 2 = n en el sumando

correspondiente,
∞
! ∞
!
X X
g(x) = a−1 + an xn+1 + a−2 + a−1 x + an xn+2
n=0 n=0

Agrupando y sustituyendo por g(x),

g(x) = a−1 + xg(x) + a−2 + a−1 x + x2 g(x)

y despejando g,
a−1 + a−2 + a−1 x
g(x) =
−x2 − x + 1
Ahora basta calcular a−1 y a−2 . La suma a−1 + a−2 = a0 luego a−1 +
a−2 = 1. Para a−1 ,

a1 = a0 + a−1 ⇐⇒ 1 = 1 + a−1 ⇐⇒ a−1 = 0

Entonces la función generatriz es

1
g(x) =
−x2 −x+1
Si desarrollamos g en su serie de Taylor alrededor de x = 0 con
ayuda de Matlab,
1 syms x
2 f = 1/(−xˆ2−x+1) ;
3 T10 = t a y l o r ( f , x , ’ Order ’ ,10)

que efectivamente coincide con la sucesión de Fibonacci, la salida

por pantalla es
 115

1 T10 =
2

3 55∗xˆ9 + 34∗xˆ8 + 21∗xˆ7 + 13∗xˆ6 + 8∗xˆ5 + 5∗xˆ4 + 3∗

xˆ3 + 2∗xˆ2 + x + 1

Vamos a ver otro ejemplo de cómo calcular la función generatriz

de una recurrencia. Esta vez lo damos como una pequeña historia.
La población de ranas de un lago infinitamente grande se
cuadruplica cada año. El primer dı́a de cada año, se sacan
100 ranas para ser llevadas a otro lago (eufemismo). Si
originalmente habı́a 50 ranas, ¿cuántas habrá en n años?
Si an es el número de ranas al final del n−ésimo año, entonces nues-
tro problema se representa por la recurrencia

an+1 = 4an − 100, a0 = 50, n ≥ 0

Para encontrar una función generatriz, multiplicamos ambos miem-

bros por xn+1 ,
an+1 xn+1 = (4an − 100)xn+1
Recordemos que nuestro objetivo es llegar a una función g(x) tal
que al desarrollarse en serie obtengamos los coeficientes {an }∞
n=0 .
Sumemos desde n = 0,
∞
X ∞
X ∞
X
n+1 n+1
an+1 x = 4an x − 100xn+1
n=0 n=0 n=0

El primer miembro es casi la función generatriz, a falta de a0 ,

∞
X
an+1 xn+1 = a1 x + a2 x2 + · · · = g(x) − a0
n=0

En el segundo miembro, el primer sumando es

∞
X ∞
X
n+1
4an x = 4x an xn = 4xg(x)
n=0 n=0

y el segundo sumando es
∞
X ∞
X  
n+1 n 1 100x
100x = 100x x = 100x =
n=0 n=0
1−x 1−x
116 APÉNDICE A. CUENTAS

Entonces podemos escribir

100x
g(x) − a0 = 4xg(x) −
1−x
Reordenando,
a0 100x
g(x) = −
1 − 4x (1 − x)(1 − 4x)
Como a0 = 50, la función generatriz buscada es
50 100x
g(x) = −
1 − 4x (1 − x)(1 − 4x)
Como ejercicio, se propone hallar las funciones generatrices de
1. an+1 = 1,05an + 500, a0 = 1000
2. an+2 = 3an+1 − 2an , a0 = 0, a1 = 1
donde las soluciones son
1000 500x x
(1) g(x) = + , (2) g(x) =
1 − 1,05x (1 − x)(1 − 1,05x) 1 − 3x + 2x2

Ir un paso más allá.

Además de calcular la función generatriz, dada una recurrencia li-
neal
an = ρ(a0 , ..., an−1 ) (A.1)
podemos encontrar una fórmula no recursiva para obtener an en
función únicamente de n convirtiendo (A.1) en

an = ρ(n)

Para obtener esta nueva fórmula, necesitamos conocer su función

generatriz g(x). Por definición, el coeficiente de xn de g es exacta-
mente an . Ası́, al desarrollar la expresión de g, el coeficiente de xn
también ha de ser an . Basta entonces expresar la función g en po-
tencias de xn . Veámoslo con un ejemplo. Para la recurrencia

an+1 = 4an − 100, a0 = 50, n ≥ 0

ya hemos obtenido su función generatriz

50 100x
g(x) = −
1 − 4x (1 − x)(1 − 4x)
 117

Expresemos cada uno de los sumandos como potencias de x. Para

el primero,
50 1
= 50 ·
1 − 4x 1 − 4x
Haciendo la sustitución z = 4x (legal pues su orden es 1) tenemos
que
X∞ X∞ X∞
1 1
50 · = 50 · = 50 z n = 50 (4x)n = 50 4 n xn
1 − 4x 1−z n=0 n=0 n=0

El segundo es un poco más delicado, lo necesitamos descomponer

en una suma de fracciones simples.
100x A B A(1 − 4x) + B(1 − x)
= + =
(1 − x)(1 − 4x) 1 − x 1 − 4x (1 − x)(1 − 4x)
De aquı́, A − 4Ax + B − Bx = 100x e igualando coeficientes
(−4A − B)x + (A + B) = 100x ⇐⇒ A + B = 0 y − 4A − B = 100
Entonces B = 100/3 y podemos escribir (hemos cambiado los signos
pero da igual)
100x 100 1 100 1
= · − ·
(1 − x)(1 − 4x) 3 1−x 3 1 − 4x
Si desarrollamos la suma,
∞ ∞
100 X n 100 X n
(x − 4n xn ) = (4 − 1)xn
3 n=0 3 n=0

Entonces los coeficientes buscados son los de xn ,

100 n
an = 50 · 4n − (4 − 1)
3
Observa que para n = 0 obtenemos exactamente a0 = 50. Para efec-
tuar los cálculos, puedes recurrir a la función partfrac de Matlab,
1 syms x ;
2 p a r t f r a c (100∗x /((1 − x ) ∗(1 −4∗x ) ) )
3

4 ans =
5

6 100/(3∗(x − 1) ) − 100/(3∗(4∗x − 1) )
118 APÉNDICE A. CUENTAS

La acción col(g −1 ).
Proposición. La aplicación de G sobre Ω dada por

T : G × Ω −→ Ω
(g, col) 7→ T (g, col) = col(g −1 (y))

es una acción de G sobre Ω.

Demostración. Basta comprobar que T cumple las condiciones de
la definición de acción.

1. Sea id ∈ G la permutación identidad, que cumple

id−1 (x) = id(x) = x, ∀x ∈ X

Entonces
T (id, col)(x) = col(id−1 (x)) = col(x)
para cada col ∈ Ω.

2. Sean g, h ∈ G y col ∈ Ω. Entonces

T (gh, col)(x) = col((gh)−1 (x))

= col(h−1 g −1 (x))
= T (g, col(h−1 ))(x)
= T (g, T (h, col))(x)

Ası́ T está bien definida. OMC

Apéndice B

Algoritmos y su complejidad.

Para entender que un algoritmo sea de complejidad polinómica

(véase el teorema sobre descomposición de conos vectoriales racio-
nales positivos), necesitamos por una parte entender qué es un al-
goritmo, y por otro cómo medir la complejidad del mismo.

B.1. Algoritmos.
Definición. Un algoritmo es un conjunto de reglas operatorias cuya
aplicación permite resolver un problema dado haciendo uso de un
número finito de operaciones.

Básicamente, un algoritmo es una sucesión de instrucciones que

transforman unos datos de entrada en otros de salida. Para im-
plementar un algoritmo, existen lenguajes algorı́tmicos, una herra-
mienta expresiva con una libertad y flexibilidad próxima a la de los
lenguajes naturales pero con el rigor de un lenguaje de programa-
ción (flashback del código algorı́tmico de Belarmino).

Un ejemplo de algoritmo es el que hemos visto de recursión para

calcular n!. El lenguaje algorı́tmico no está para nada estandari-
zado, si bien las palabras clave son las mismas: mientras (while),
para (for ), si-entonces (if ),...

Se recomienda descargar y utilizar el programa PSeInt para escribir

código algorı́tmico y comprobar que funciona. Por ejemplo, el códi-
go para la función recursiva del factorial en código algorı́tmico serı́a

119
 120 APÉNDICE B. ALGORITMOS Y SU COMPLEJIDAD.

1 Funcion fac <− FactorialFun ( N )

2 s i N=0 entonces
3 fac = 1
4 sino
5 fac = N∗ FactorialFun ( N−1)
6 fin si
7 Fin Funcion

B.2. Complejidad algorı́tmica.

Para determinar cómo de bueno es un algoritmo, se evalúan dos
aspectos: el tiempo que tarda en ejecutarse y el espacio de memoria
que necesita durante ese tiempo. Si TA y EA representan el tiempo
y el espacio necesario, es obvio que ambos dependen de la cantidad
n de datos que recibe el algoritmo A como entrada: TA (n) y EA (n).

Parece razonable que la bondad de un algoritmo no dependa ni del

lenguaje de programación, ni del compilador ni de la máquina (or-
denador) elegida. Entonces

Definición. Una operación es básica o elemental si su tiempo de

ejecución se puede acotar superiormente por una constante inde-
pendiente del tamaño de la entrada, máquina, lenguaje o compila-
dor.

Definición. Dado un algoritmo A, definimos su tiempo de ejecuc-

ción TA (n) como el número de operaciones básicas que realiza con
una entrada de tamaño n.

Observa que aunque se llame tiempo no medimos realmente tiempo

en segundos, sino pasos que realiza el algoritmo.

Tenemos claro entonces que el tiempo de ejecución de un algo-

ritmo depende del tamaño de la entrada. Pero también depende de
cómo sea esa entrada. No se tarda lo mismo en ordenar un vector de
10 elementos desordenado que ya ordenado. Surge ası́ la necesidad
de medir TA en distintas situaciones de n:

1. El peor caso es el supuesto en el que las condiciones de n son

B.2. COMPLEJIDAD ALGORÍTMICA. 121

las peores posibles. Este valor nos da una cota superior para
TA .

2. El caso medio se calcula tomando un n aleatorio.

3. El mejor caso supone que n tiene las condiciones ideales para

que A sea lo más eficiente posible. Nos da una cota inferior de
TA , pero no es de gran utilidad.

Para valores pequeños de n, TA es irrelevante, obtenemos valores

muy similares en los tres casos. Nos interesa cuando n → ∞, luego
estudiaremos
lı́m TA (n)
n→∞

La forma usual de medir este lı́mite es haciendo uso de la notación

O de Landau.

B.2.1. Orden de una función.

Definición. Sean f, g : N −→ R+ dos funciones. Se dice que g es el
orden de f , y se escribe g ∈ O(f ), si existen c ∈ R+ y n0 ∈ N tales
que, para cada n ≥ n0 ,
g(n) ≤ cf (n)
Propiedades. Algunas propiedades del orden son

1. O(loga (n)) = O(logb (n)) cualesquiera sean a, b ∈ R+ .

2. Si g(n) = ak nk + · · · + a1 n + a0 con ak 6= 0 entonces g ∈ O(nk ).

3. Si g(n) = cn entonces g ∈ O(n) (caso particular del anterior).

4. Si g(n) = 1 + 2 + · · · + n entonces g ∈ O(n2 ) (¿por qué?)

5. Si g(n) = 1 + 4 + 9 + · · · + n2 entonces g ∈ O(n3 ) (¿por qué?)

Además, la relación de orden cumple

6. Para cualquier f, f ∈ O(f (n)).

7. El orden es transitivo,

f ∈ O(g(n)) y g ∈ O(h(n)) =⇒ f ∈ O(h(n))

8. Las constantes no influyen, O(cf (n)) = O(f (n)) para c ∈ R+ .

122 APÉNDICE B. ALGORITMOS Y SU COMPLEJIDAD.

1. Por la propiedad (1), la base del logaritmo no importa. Escri-

biremos únicamente O(log(n)).

2. O(f (n) + g(n)) = máx(O(f (n)), O(g(n))).

3. O(f (n)g(n)) = O(f (n))O(g(n)).

B.2.2. Escala de órdenes de complejidad.

Usualmente, se utilizan las siguientes funciones para medir la
complejidad algorı́tmica, donde cuánto más abajo en la tabla peor
es el algoritmo.

O(1) complejidad constante

O(log(n)) complejidad logarı́tmica
O(n) complejidad lineal
O(nk ) complejidad polinómica si k > 1
O(2n ) complejidad exponencial
O(n!) complejidad exponencial

Observación. Los conjuntos O(f (n)) nos proporcionan cotas supe-

riores para TA . Se trata de encontrar entonces la menor

f : N −→ R+ tal que TA ∈ O(f (n))

Por ejemplo, si TA ∈ O(n3 ) entonces evidentemente TA ∈ O(n4 ) o

TA ∈ O(n!) pero esto no nos aporta nada.

B.2.3. Estudio de la complejidad de algoritmos ite-

rativos.
Centraremos el estudio en algoritmos no recursivos por ser los
más sencillos, y porque todo algoritmo recursivo puede ser escrito
de manera no recursiva (¿cómo serı́a el factorial?).

Proposición. Dado un algoritmo A implementado de dos maneras

I1 e I2 con tiempos de ejecución t1 y t2 respectivamente, existen cons-
tantes k, n0 ∈ N tales que para cada n ≥ n0 , t1 ≤ kt2 .

 Ejemplo. Podemos implementar el factorial de un número n de

forma iterativa de dos maneras: con un while y con un for:
 B.2. COMPLEJIDAD ALGORÍTMICA. 123

1 Funcion fac <− f a c t o r i a l w h i l e ( n )

2 i = 1
3 fac = 1
4 mientras i <= n Hacer
5 fac = fac ∗ i
6 i = i +1
7 FinMientras
8 Fin Funcion

1 Funcion fac <− f a c t o r i a l f o r ( n )

2 fac = 1
3 para i desde 1 hasta n Hacer
4 fac = fac ∗ i
5 FinPara
6 Fin Funcion

Para n = 4 el primer algoritmo realiza 18 operaciones y el segun-

do 13, difieren en la operación elemental i = i+1. En general, para
n arbitrario, el algoritmo for realiza n + 1 comparaciones y n mul-
tiplicaciones, es decir, 2n + 1 operaciones que dependen de n; y el
algoritmo while realiza n + 1 comparaciones, n multiplicaciones y n
sumas, es decir, 3n + 1 operaciones que dependen de n. Entonces
3n + 1 3
lı́m =
n→∞ 2n + 1 2

Veamos ya por fin cómo calcular la complejidad de un algoritmo. El

principio básico es el siguiente: si A es un algoritmo no recursivo,
su tiempo de ejecución TA será el máximo de los tiempos de eje-
cución de cada instrucción que componen A. Ası́, nos basta saber
cuánto tarda cada tipo de instrucción. En concreto, los tipos son:
elemental, de selección, de repetición y llamadas a subprogramas.

Si I es la instrucción que estamos considerando, escribimos I ≡ [ ]

para indicar qué tipo de instrucción es.

Instrucciones elementales.
Definición. Consideramos instrucción elemental a aquellas que son
1. De entrada/salida.
 124 APÉNDICE B. ALGORITMOS Y SU COMPLEJIDAD.

2. Asignación de variables.

3. Expresiones aritméticas que no dependen directa o indirecta-

mente de n.

Escribimos I ≡ [elemental] y entonces TI ∈ O(1). Supongamos ahora

I1 , ..., In instrucciones no necesariamente elementales. Entonces la
instrucción resultante de realizar primero I1 , luego I2 ,... hasta In
cumple
I ≡ [I1 ; I2 ; ...; In ] =⇒ TI ∈ O(máx(f1 , f2 , ..., fn ))
si para cada j, TIj ∈ O(fj ).

Instrucciones de selección.
Una instrucción de selección es aquella donde se realiza una deci-
sión en función de una condición lógica. Coloquialmente, son las
instrucciones if y switch. Supongamos

I ≡ [si B entonces I1 si no I2 ]

con órdenes TB ∈ O(fB ), TI1 ∈ O(f1 ) y TI2 ∈ O(f2 ). Entonces

TI ∈ máx(O(fB ), O(f1 ), O(f2 ))

Si consideramos la instrucción switch para k opciones,

1 segun B hacer
2 caso 1:
3 caso 2:
4

5 caso k :
6 FinSegun

con TB ∈ O(fB ) y TIi ∈ O(fi ) para cada i = 1, ..., k entonces

I ≡ [según B hacer 1, ..., k] =⇒ TI ∈ máx(O(fB ), O(fi ))

Bucles.
Entendemos por bucles o instrucciones de repetición aquellas ins-
trucciones que se realizan un número finito de veces en función de
una condición lógica que llamaremos de entrada.
 B.2. COMPLEJIDAD ALGORÍTMICA. 125

Si el bucle se realiza k veces y consideramos la instrucción

I ≡ [mientras B hacer J],

suponiendo TB , TJ ∈ O(fi ) para cada iteración i = 1, ..., k entonces

k
!
X
TI ∈ O fi
i=1

Podrı́as preguntarte que cuánto vale k, pues en un while no hay un

tope de repeticiones que pueda realizar el bucle. Se toma siempre k
como el peor caso posible que podrı́a darse y ası́ obtenemos la cota
superior.

La instrucción I ≡ [para i desde x0 hasta x1 hacer J] tiene la misma

complejidad que el while pero no se tiene en cuenta pues la condi-
ción lógica es constante.

 Ejemplo. Consideramos el algoritmo para ordenar un vector de

tamaño n por el método de la burbuja,
1 Funcion burbuja ( vector , n )
2 para i desde 1 hasta n con paso 1
3 para j desde n hasta 2 con paso −1
4 s i vector [ j −1] > vector [ j ] entonces
5 temp=vector [ j −1]
6 vector [ j −1]= vector [ j ]
7 vector [ j ]=temp
8 FinSi
9 FinPara
10 FinPara
11 Fin Funcion

Analicemos este algoritmo. Las operaciones de asignación son ele-

mentales luego las lı́neas 5, 6 y 7 contienen instrucciones de tiempo
O(1). El máximo de estas tres vuelve a ser O(1) luego si T1 es el tiem-
po de las lı́neas 5-6-7 entonces T1 ∈ O(1). Estas tres operaciones
están dentro de un if, que poniéndonos en el peor caso (es decir,
que efectivamente se entra dentro del condicional) entonces el tiem-
po T2 de las lı́neas 4-5-6-7 vuelve a ser O(1) pues la condición lógica
es elemental. Nos queda por examinar los dos bucles for. Sabemos
126 APÉNDICE B. ALGORITMOS Y SU COMPLEJIDAD.

que el interior del segundo bucle (lı́nea 3) es de orden O(1). Como

se realizan n − i iteraciones,
n−i
!
X
T3 ∈ O i = O(n − i)
i=1

El primer bucle también se realiza n − 1 veces y entonces el tiempo

total es
n−1
X n(n − 1) 1 1
TA = (n − i) = = n2 + n =⇒ TA ∈ O(n2 )
i=1
2 2 2
Apéndice C

Matemáticos aparecidos en
los apuntes.

William Burnside.

Pionero en la teorı́a de grupos finitos, el inglés William Burnside

(1852 - 1927) es conocido principalmente por su obra Teorı́a de
Grupos de Orden Finito (1897).
El lema que hemos visto en teorı́a de este
hombre ya se habı́a descubierto por Frobe-
nius y Augustin Cauchy de manera totalmen-
te independiente. Como anécdota podemos
contar que G. Stokes le dio clase en Cambrid-
ge; seguro que a él si le entró el teorema de
Stokes en el examen.

Durante su vida Burnside publicó alrededor

de 150 artı́culos, de ellos unos 50 tratan de
teorı́a de grupos. De hecho, en los últimos
años de su vida se interesó por la teorı́a de la probabilidad. Su pri-
mer trabajo sobre este tema apareció en 1918. También dejó el ma-
nuscrito completo de un libro, que fue publicado un año después
de su muerte, con el tı́tulo de The Theory of Probability.

[Link]

127
128 APÉNDICE C. MATEMÁTICOS

George Polya.
George Polya nació en Hungrı́a en 1887. Obtuvo su doctorado en la
Universidad de Budapest y en su disertación para obtener el gra-
do abordó temas de probabilidad. Fué maestro en el Instituto Tec-
nológico Federalen Zurich, Suiza. En 1940 llegó a la Universidad de
Brown en E.U.A. y pasó a la Universidad de Stanford en 1942. En
sus estudios, estuvo interesado en el proceso del descubrimiento,
o cómo es que se derivan los resultados matemáticos. Advirtió que
para entender una teorı́a, se debe conocer cómo fué descubierta.
Las aportaciones de Pólya incluyen más de
250 documentos matemáticos y tres libros
que promueven un acercamiento al conoci-
miento y desarrollo de estrategias en la so-
lución de problemas. Su famoso libro Cómo
Plantear y Resolver Problemas que se ha tra-
ducido a 15 idiomas, introduce su método de
cuatro pasos junto con la heurı́stica y estra-
tegias especı́ficas útiles en la solución de pro-
blemas. Otros trabajos importantes de Pólya
son Descubrimiento Matemático (I y II), y Ma-
temáticas y Razonamiento Plausible (I y II).
Pólya, que murió en 1985 a la edad de 97
años, enriqueció a las matemáticas con un
importante legado en la enseñanza de estrategias para resolver pro-
blemas. En suma, dejó los siguientes Diez Mandamientos para los
Profesores de Matemáticas.

[Link]
Apéndice D

Recortables.

Con unas tijeras de punta redonda, recorte las figuras por su

borde exterior. Si necesita más copias, sitúe la página deseada en
la fotocopiadora y realice el número de copias necesarias.

Para pegar las caras, se recomienda utilizar pegamento de barra

para no manchar toda la mesa. En caso de no tener, celo está bien
también. Ya como última opción utiliza cola blanca. No utilice su-
perglue bajo ningún concepto.

129
131