Respuestas
Respuesta:
Ejemplo 26.- Descomponer en ciclos la permutaci´on
σ =
1 2 3 4 5 6 7 8 9
3 5 7 8 4 6 1 2 9
.
Siguiendo la demostraci´on del Teorema anterior, empezamos por considerar el ciclo al que
pertenece el 1. De esta forma vemos cu´al es la imagen del 1, luego la imagen de la imagen y
as´ı sucesivamente hasta regresar al 1.
1 −→ 3 −→ 7 −→ 1 ≡ (1 3 7).
Tomamos ahora el primer numero ´ no incluido en el ciclo anterior y construimos el ciclo al que
pertenece, (2 5 4 8). Continuamos hasta ver que
σ = (1 3 7)(2 5 4 8)(6)(9).
Aplicaciones de la descomposici´on en ciclos pueden encontrarse en diferentes trucos de magia realizados
con una baraja. Se trata de aparentar un desordenamiento de las cartas, cuando en realidad se est´an
haciendo ciertas permutaciones, cuya descomposici´on en ciclos se conoce. Para ello, resulta util ´ saber
que si un ciclo de longitud r se itera r veces, entonces todos los elementos quedan como al principio. Es
decir, σ
r
(k) = k, 1 ≤ k ≤ n.
Ejemplo 27.- Los numeros ´ del 1 al 15 est´an dispuestos en forma de matriz 3 × 5. Se reordenan, leyendo
los numeros ´ por filas y escrbi´endolos por columnas
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
−→
1 4 7 10 13
2 5 8 11 14
3 6 9 12 15
¿Despu´es de cu´antas repeticiones de este proceso la tabla quedar´a como al principio?
El reordenamiento de la tabla no es m´as que una permutaci´on de S15, que descompuesta en
ciclos se escribe como
(1)(2 4 10 14 12 6)(3 7 5 13 9 11)(8)(15)
Por lo tanto como los ciclos son de longitud 1 o´ 6, depu´es de 6 repeticiones la tabla quedar´a
como estaba.
2.4.1 Numeros ´ de Stirling de primera clase
Planteemos la siguiente pregunta: ¿Cu´antas permutaciones de Sn se descomponen en k ciclos? Denotemos
a este numero ´ por [
n
k
], que denominaremos numer ´ o de Stirling de primera clase.
Algunos de estos numeros ´ son f´aciles de calcular. Por ejemplo,
n
n
representa el total de permutaciones
que se descomponen en n ciclos. En este caso, cada elemento forma un ciclo de forma unica ´ y por tanto
n
n
= 1.
Tambi´en es f´acil calcular n
1
. Ahora se trata de ver cu´antas permutaciones se descomponen en un s´olo
ciclo. Para ello, observemos que los siguientes ciclos son equivalentes
(A B C D) ≡ (B C D A) ≡ (C D A B) ≡ (D A B C).
De alguna manera, el primer elemento del ciclo lo podemos fijar y s´olo es necesario cambiar los siguientes
elementos de orden para obtener ciclos distintos. Por lo tanto
n
1
= (n − 1)!
Supongamos que conocemos los numeros ´ de Stirling de primera clase para el caso de las permutaciones
de n − 1 elementos y queremos calcular n
k
. Distinguiremos dos situaciones:
17
n
n
1
n
2
n
3
n
4
n
5
n
6
n
7
1 1
2 1 1
&
×2
↓
3 2 3 1
&
×3
↓ &
×3
↓
4 6 11 6 1
&
×4
↓ &
×4
↓ &
×4
↓
5 24 50 35 10 1
&
×5
↓ &
×5
↓ &
×5
↓ &
×5
↓
6 120 274 225 85 15 1
&
×6
↓ &
×6
↓ &
×6
↓ &
×6
↓ &
×6
↓
7 720 1754 1624 735 175 21 1
Table 2: Numeros ´ de Stirling de primera clase.
En la primera supondremos que el elemento n forma un ciclo de longitud 1. Entonces, los n−1 elementos
restantes est´an en k − 1 ciclos, lo que aporta un total de n−1
k−1
posibles descomposiciones.
En la segunda supondremos que n no es un ciclo de longitud 1. Por tanto ahora los n − 1 elementos
restantes est´an en k ciclos, mientras que n puede ser introducido en cualquiera de ellos de todas las formas
posibles. Por ejemplo, si tenemos la descomposici´on
(A B C)(D E)
y queremos insertar un sexto elemento F, lo podemos hacer de las 5 maneras siguientes
(A F B C)(D E),
(A B F C)(D E),
(A B C F)(D E),
(A B C)(D F E),
(A B C)(D E F).
Generalizando, n puede introducirse de n−1 formas diferentes y esto nos da (n−1)n−1
k
nuevas descomposiciones. Por lo tanto
n
k
=
n − 1
k − 1
+ (n − 1)
n − 1
k
. (8)
En la tabla 2 se dan los numeros ´ de Stirling hasta n = 7. Observar que si se suman todos los numeros ´
de Stirling en una misma fila (fila k-´esima por ejemplo) se obtiene el factorial de k.
La relaci´on de recurrencia (8) permite construir una funci´on generadora de los numeros ´ de Stirling. En
efecto, si denotamos por x
n al siguiente producto
x
n =
n factores
z }| {
x(x + 1)(x + 2). . .(x + n − 1),
entonces, aplicando (8) y utilizando el principio de inducci´on matem´atica, resulta