Combinatoria de permutaciones

UNIVERSIDAD DE SEVILLA FACULTAD DE MATEM´ ATICAS DEPARTAMENTO DE ESTAD´ ISTICA E INVESTIGACI´ ON OPERATIVA TRABAJO FIN DE GRADO COMBINATORIA DE PERMUTACIONES Presentado por: Roc´ıo Rodr´ıguez Huertas Dirigido por: Fernando L´opez Blazquez Sevilla, Junio de 2016 3 ´ Indice general Introducci´on 4 Abstract 4 Agradecimientos 4 1. N´umeros Eulerianos y de Stirling 11 1.1. N´umeros Eulerianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2. N´umeros de Stirling de segunda clase . . . . . . . . . . . . . . . . . . 22 2. Inversiones 29 2.1. La funci´on generatriz del n´umero de inversiones para permutaciones . 29 2.2. ´ Indicemayor ............................... 34 2.3. Una aplicaci´on. Determinantes y grafos . . . . . . . . . . . . . . . . . 38 2.3.1. La definici´on expl´ıcita de los determinantes . . . . . . . . . . . 38 2.3.2. Matchings perfectos en grafos bipartitos . . . . . . . . . . . . 39 3. Permutaciones como producto de ciclos 47 3.1. Descomposici´on de una permutaci´on en ciclos . . . . . . . . . . . . . 47 3.1.1. Una aplicaci´on. Signo y determinantes . . . . . . . . . . . . . 52 3.2. Permutaciones pares e impares . . . . . . . . . . . . . . . . . . . . . . 53 3.3. Tipos de permutaciones . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3.1. El tipo de una permutaci´on . . . . . . . . . . . . . . . . . . . 56 3.3.2. Una aplicaci´on. Permutaciones conjugadas . . . . . . . . . . . 57 3.4. N´umeros de Stirling de primera clase . . . . . . . . . . . . . . . . . . 59 4. Aplicaciones 65 4.1. Test de rachas ascendentes y descendentes . . . . . . . . . . . . . . . 65 4.1.1. Introducci´on............................ 65 4.1.2. Test de rachas ascendentes y descendentes . . . . . . . . . . . 66 4.2. Aplicaciones de los n´umeros de Stirling al c´alculo de momentos . . . . 72 4.2.1. Momentos ordinarios en funci´on de los momentos factoriales . 72 4.2.2. Momentos factoriales en funci´on de los momentos ordinarios . 73 4.3. Conexi´on con los momentos centrales . . . . . . . . . . . . . . . . . . 73 4.4. Distribuciones............................... 74 4.4.1. Distribuci´on de Poisson . . . . . . . . . . . . . . . . . . . . . . 74 4.4.2. Distribuci´on Binomial . . . . . . . . . . . . . . . . . . . . . . 75 4.4.3. Distribuci´on Hipergeom´etrica . . . . . . . . . . . . . . . . . . 76 4.4.4. Distribuci´on Binomial Negativa . . . . . . . . . . . . . . . . . 77 Bibliograf´ıa 79 Introducci´on El nacimiento y desarrollo de la combinatoria ha sido paralelo al desarrollo de otras ramas de las Matem´aticas, tales como el ´algebra, la teor´ıa de n´umeros, y la probabilidad. Desde tiempos muy remotos ha habido problemas de combinatoria que han llamado la atenci´on de los matem´aticos: El problema de los cuadrados m´agicos, que son matrices de n´umeros con la propiedad de que la suma de los elementos de cualquier columna, fila o diagonal es el mismo n´umero. Aparece en un viejo libro chino fechado 2200 a.C. Los cuadrados m´agicos de orden 3 fueron estudiados con fines m´ısticos. Los coeficientes binominales, que son los coeficientes enteros del desarrollo de (a+b)n. Fueron conocidos en el siglo XII. El tri´angulo de Pascal, que es una disposici´on triangular de los coeficientes binominales. Fue desarrollado en el siglo XIII. La combinatoria se desarrolla en occidente en el siglo XVII debido a los intereses de Blaise Pascal (1623 −1662) y Pierre Fermat (1601 −1655) por los aspectos matem´aticos de los juegos de azar. Comenzaron a recoger muestras de experimentos que realizaban en las mesas de juegos y a registrarlas estad´ısticamente para estudiar las leyes y regularidades bajo las cuales se reg´ıan. Uno de ellos fue el siguiente: el juego consist´ıa en el lanzamiento de una moneda sucesivas veces. El ganador es el jugador que alcanza primero 6 ´exitos (6 caras ´o 6 n´umeros). Pero el juego se detiene si tras el noveno lanzamiento un jugador tiene 5 ´exitos y el otro 4. ¿C´omo se puede repartir entonces la apuesta? No era justo hacerlo con la raz´on 5 : 4. Pascal resolvi´o el problema aplicando algunos m´etodos combinatorios y adem´as propuso un m´etodo de soluci´on para el caso general, cuando a un jugador le quedaran “r” partidas hasta ganar y al otro jugador le quedaran “s” partidas. Una soluci´on similar a este problema fue dada por Fermat. La combinatoria se desarrolla de forma m´as completa con los trabajos de Jacob Bernoulli (1654 −1705) y Gottfried Wilhelm Leibnitz (1646 −1716) que definieron los conceptos b´asicos de la combinatoria. El matem´atico suizo Leonard Euler fue quien desarroll´o a principios del siglo XVIII una aut´entica escuela de matem´atica combinatoria. En sus art´ıculos sobre la partici´on y descomposici´on de enteros positivos en sumandos, estableci´o las bases de uno de los m´etodos fundamentales para el c´alculo de configuraciones combinatorias, el m´etodo de las funciones generatrices. Tambi´en se le considera el padre de la teor´ıa de grafos por el planteamiento y soluci´on de los problemas de los Puentes de Konigsberg usando por primera vez conceptos y m´etodos de teor´ıa de grafos. Los primeros problemas de teor´ıa de grafos surgieron de la b´usqueda de soluci´on a algunos problemas cotidianos y tambi´en en el planteamiento de algunos acertijos matem´aticos tales como el problema de los Puentes de Konigsberg, la colocaci´on de reinas en un tablero de ajedrez con alguna restricci´on, problemas de transporte y el problema del viajero, entre otros. Hoy en d´ıa la combinatoria constituye una amplia rama de las Matem´aticas con numerosas aplicaciones pr´acticas a otras ciencias tales como la Biolog´ıa, la Inform´atica, las Comunicaciones, etc. Se han descrito numerosas estructuras combinatorias. Es este trabajo nos centraremos en una de las m´as simples pero no por ello menos importante: las permutaciones. Una permutaci´on puede ser interpretada de muchas maneras. En el Cap´ıtulo 1, se consideran las permutaciones como ´ordenes lineales y el inter´es se centra en los ascensos en dichas ordenaciones. El n´umero de permutaciones de tama˜no n con un n´umero fijo de ascensos se conoce como n´umero Euleriano. Se estudian las propiedades b´asicas de estos n´umeros, diversas funciones generatrices y su relaci´on con los n´umeros de Stirling de segunda clase. En el Cap´ıtulo 2 se estudian las inversiones y otros estad´ısticos con igual distribuci´on como el ´ındice mayor. Se presentan algunas relaciones de estos conceptos con los determinantes y los matching perfectos en grafos bipartitos. El Cap´ıtulo 3 est´a dedicado a la descomposici´on de permutaciones como producto de ciclos. La descomposici´on en ciclos de longitud dos es b´asica para la clasificaci´on de permutaciones en par e impar. Si se considera la descomposici´on en ciclos disjuntos, el n´umero de permutaciones de longitud ncon kciclos es descrito por los n´umeros de Stirling de primera clase (sin signo). Para estos n´umeros presentamos f´ormulas recurrentes y diversas funciones generatrices asociadas. Finalmente, en el Cap´ıtulo 4 presentamos algunas aplicaciones de los conceptos estudiados en cap´ıtulos anteriores. Destacamos la aplicaci´on a los contrastes de aleatoriedad y la conexi´on entre momentos factoriales y ordinarios. Abstract Permutations are perhaps one of the most basic and important combinatorial structures. They appear in Mathematics and other fields of Science and Technology under many different appearances, for instance as linear orders, elements of the symmetric group, or associated to certain matrices and graphs. There are also many interesting statistics associated to permutations. Among others, in this work, we explore the number of ascents, the number of inversions and the number of cycles. In connection with theses statistics there are many interesting results and concepts like recurrence formulas, generating functions and a collection of important numbers not only in combinatorics but in some other fields as Eulerian numbers, Stirling numbers of first and second kind, etc. Finally, in the last chapter we present some aplications to run tests based on the length of ascents and descents and also the connection between central and factorial moments. Agradecimientos Puesto que no hubiese podido terminar el grado si no hubiese contado con el apoyo, el cari˜no, la energ´ıa y el tiempo de muchas personas, quer´ıa incluir este apartado para poder agradecerles todo lo que me han ayudado en estos cuatro a˜nos. Le dedico este trabajo a mi familia, en especial a mis padres, por el esfuerzo que han tenido que realizar para que hoy pudiera estar escribiendo esto, por su apoyo incondicional y desinteresado en cada momento que cre´ıa que no lo conseguir´ıa y por celebrar conmigo cada triunfo ganado. Si hoy estoy aqu´ı es por ellos. Adem´as, agradecer a mis amigos por permanecer a mi lado d´ıa tras d´ıa, por aquellas ma˜nanas, tardes y casi noches en la biblioteca y en esas salas del CRAI, donde adem´as de agobios, hemos crecido como personas y como matem´aticos. Muchas han sido las horas que hemos empleado en llegar hasta aqu´ı y ahora estamos al borde de conseguirlo. Y para acabar, agradecer a mi tutor Fernando L´opez Blazquez, por su entrega y dedicaci´on, pues siempre ha estado a disposici´on cuando lo he necesitado. Me ha ayudado a que esta recta final de la carrera haya sido mas llevadera y con el menor n´umero de complicaciones posibles. Sin su ayuda y conocimientos no hubiese sido posible realizar este proyecto. En general, le dedico este trabajo a todo aquel que haya aportado un granito de arena para que consiguiera mi sue˜no. 16 CAP´ ITULO 1. Introducci´on Demostraci´on Distinguiremos dos casos: Suponemos que xes un entero positivo. El lado izquierdo cuenta las secuencias de nelementos en las que cada d´ıgito proviene del conjunto [x]. Vamos a demostrar que el lado derecho cuenta esas mismas secuencias. Sea a=a1a2· · · anuna secuencia. Reordenamos aen orden no decreciente, es decir, de la forma a0=ai1≤ai2≤ · · · ≤ aincon la condici´on extra de que los d´ıgitos id´enticos aparecen en a0en orden creciente de sus ´ındices. Entonces i=i1i2· · · ines una n-permutaci´on que est´a ´unicamente determinada por a. Oberservamos que i1 nos dice la posici´on en ade la primera entrada de i,i2nos dice la posici´on en ade la segunda entrada de iy as´ı sucesivamente. Por ejemplo, si a= 421132, primero tenemos que reordenar en orden no decreciente, dando lugar a a0= 112234, por lo que i= 342651. Por ´ultimo, vamos a demostrar que cada permutaci´on itiene k−1 descensos, obteniendo exactamente x+n−ksecuencias de a. Debemos tener en cuenta que si aij=aij+1 , entonces ij< ij+1. Tomando la implicaci´on contraria, si jes un descenso de p(a) = i1i2· · · in, entonces aij< aij+1 . Esto quiere decir, que la secuencia a0tiene que ser estrictamente creciente cada vez que jsea un descenso de p(a). En nuestro ejemplo, i= 342651 tiene descenso en 2 y 4 y a0= 112234 es estrictamente creciente en dichas posiciones. ¿Cu´antas secuencias de apueden llevar a la permutaci´on i= 342651?. Se tiene por el argumento anterior que en secuencias con esa propiedad, nosotros deber´ıamos tener 1≤a3≤a4< a2≤a6< a5≤a1≤x con desigualdad estricta en la tercera y quinta posici´on. La cadena de desigualdades anterior es obviamente equivalente a 1≤a3< a4+ 1 < a2+ 1 < a6+ 2 < a5+ 2 < a1+ 3 ≤x+ 3 y por consiguiente, el n´umero de secuencias es claramente x+ 3 6. Por eso, este es el n´umero de secuencias en apara cada i= 342651. Generalizando este argumento para todo ny para permutaciones icon k−1 descensos, podemos 1.1. N´umeros Eulerianos 17 conseguir que cada n-permutaci´on con k−1 descensos provenga de x+ (n−1) −(k−1) n=x+n−k n secuencias. Supongamos que xno es un entero positivo. Tenemos en cuenta que los dos lados de la ecuaci´on pueden ser vistos como polinomios en la variable x. Ya que coinciden para un n´umero infinito de valores (enteros positivos), ´estos deben ser id´enticos.  Ejemplo 1.1.12 Fijamos n= 3, usando los n´umeros Eulerianos calculados en el Ejemplo 1.1.8 tenemos: x3= 3 X k=0 A(3, k)x+n−k 3 =A(3,0)x+ 3 −0 3+A(3,1)x+ 3 −1 3+A(3,2)x+ 3 −2 3 +A(3,3)x+ 3 −3 3=x+ 2 3+ 4x+ 1 3+x 3.  Corolario 1.1.13 Para todos los enteros positivos n, se tiene que xn= n X k=0 A(n, k)x+k−1 n. Demostraci´on Cambiamos xpor −xen la expresi´on (1.2) y conseguimos xn(−1)n= n X k=0 A(n, k)−x+n−k n.(1.3) 18 CAP´ ITULO 1. Introducci´on Ahora calculamos −x+n−k n. −x+n−k n=(−x+n−k)! n!(−x+n−k−n)! =(−x+n−k)! n!(−x−k)! =(−x+n−k)· · · (−x+n−k−(n−1))(−x+n−k−n) n!(−x−k)! =(−x+n−k)(−x+n−k−1) · · · (−x−k+ 1)(−x−k)! n!(−x−k)! =(−x+n−k)(−x+n−k−1) · · · (−x−k+ 1) n!= (−1)nx+k−1 n Sustituyendo este valor en (1.3) xn(−1)n= n X k=0 A(n, k)(−1)nx+k−1 n. De esta forma obtenemos el resultado xn= n X k=0 A(n, k)x+k−1 n.  Lema 1.1.14: F´ormula de Convoluci´on de Cauchy Sean xeyn´umeros reales y sea zun entero positivo. Entonces x+y z= z X d=0 x d y z−d. Teorema 1.1.15 Para todos los enteros no negativos nyk, con k≤n, se tiene que A(n, k) = k X r=0 (−1)rn+ 1 r(k−r)n.(1.4) Demostraci´on Tomamos la expresi´on xn= n X k=0 A(n, k)x+n−k n, n = 0,1, . . . 1.1. N´umeros Eulerianos 19 reemplazamos la variable kpor jy tomamos x=k−rcon r= 0,1, . . . , k, deduciendo la expresi´on (k−r)n= k−r X j=0 A(n, j)k−r+n−j n, r = 0,1, . . . , k que usando la relaci´on n+k−r−j n=n+k−r−j k−r−j= (−1)k−r−j−n−1 k−r−j puede escribirse como (k−r)n= k−r X j=0 A(n, j)(−1)k−r−j−n−1 k−r−j, r = 0,1, . . . , k Multiplicando a ambos lados de la expresi´on por (−1)rn+ 1 ry sumando para r= 0,1, . . . , k, conseguimos que k X r=0 (−1)rn+ 1 r(k−r)n= k X r=0 k−r X j=0 (−1)rn+ 1 rA(n, j)−n−1 k−r−j(−1)k−r−j= = k X j=0 A(n, j)(−1)k−j k−j X r=0 n+ 1 r−n−1 k−r−j y por la f´ormula de Cauchy k−j X r=0 n+ 1 r−n−1 k−r−j=0 k−j=δk,j y as´ı obtenemos la expresi´on que quer´ıamos.  Definici´on 1.1.16 Los polinomios eulerianos se definen como An(t) = n X k=0 A(n, k)tk, n = 0,1, . . . (1.5) Lema 1.1.17 Una alternativa para expresar los polinomios eulerianos An(t) es An(x) = (1 −x)n+1 ∞ X j=0 jnxj, n = 0,1, . . . (1.6) 20 CAP´ ITULO 1. Introducci´on Demostraci´on Sustituyendo en la expresi´on (1.5) el valor de A(n, k), obtenido en la expresi´on (1.4), deducimos que An(x) = n X k=0 k X r=0 (−1)rn+ 1 r(k−r)nxk. Nos fijamos en la suma interior y observamos que A(n, k) = 0, k > n se anula para k=n+1, n+2, . . ., lo que hace posible extender la suma de fuera hasta el infinito. Por tanto, An(x) = n X k=0 k X r=0 (−1)rn+ 1 r(k−r)nxk = ∞ X r=0 (−1)rn+ 1 rxr ∞ X k=r (k−r)nxk−r. Teniendo en cuenta que ∞ X r=0 (−1)rn+ 1 rxr= (1 −x)n+1 y tomando j=k−r, llegamos a An(x) = (1 −x)n+1 ∞ X j=0 jnxj.  Ejemplo 1.1.18 Vamos a usar la serie geom´etrica real de t´ermino inicial a∈Ry de raz´on r∈R ∞ X n=0 arn=a 1−r Para n= 1 tenemos A1(x) = (1 −x)2 ∞ X j=0 jxj= (1 −x)2x (1 −x)2=x, y para n= 2 A2(x) = (1 −x)2 ∞ X j=0 j2xj= (1 −x)3 2x3 (1 −x)3+x (1 −x)2!=x+x2.  1.2. N´umeros de Stirling de segunda clase 21 Teorema 1.1.19 La funci´on generatriz bivariante de los n´umeros Eulerianos A(n, k), k= 0,1, . . . , n, n = 0,1, . . . viene dada por g(x, u) = ∞ X n=0 n X k=0 A(n, k)xkun n!=1−x 1−xeu(1−x). Demostraci´on Usando la expresi´on (1.5) obtenemos g(x, u) = ∞ X n=0 An(x)un n! y sustituy´endo la expresi´on (1.6) en la anterior llegamos a g(x, u) = ∞ X n=0 (1 −x)n+1 ∞ X j=0 jnxjun n!= (1 −x) ∞ X j=0 xj ∞ X n=0 [ju(1 −x)]n n!. Por otro lado, teniendo en cuenta el desarrollo de la funci´on exponencial ∞ X n=0 xn n!=ex, se tiene que [ju(1 −x)]n n!=eju(1−x)por lo que (1 −x) ∞ X j=0 xj ∞ X n=0 [ju(1 −x)]n n!= (1 −x) ∞ X j=0 xjeju(1−x)= (1 −x) ∞ X j=0 [xeu(1−x)]j y el desarrollo de la serie geom´etrica ∞ X n=0 axn=a 1−x obteniendo ∞ X j=0 [xeu(1−x)]j=1 1−xeu(1−t). Por tanto, g(x, u) = 1 1−xeu(1−x).  22 CAP´ ITULO 1. Introducci´on 1.2. N´umeros de Stirling de segunda clase Una partici´on de un conjunto [n] en kbloques es una distribuci´on de los elementos de [n] en ksubconjuntos no vac´ıos B1, B2, . . . , Bkde modo que cada elemento se coloca exactamente en un bloque, es decir, B1∪· · ·∪Bk= [n] y Bi∩Bj=∅,i6=j. Definici´on 1.2.20 El n´umero de particiones de [n] en kbloques se denota por S(n, k) y se llama n´umero de Stirling de segunda clase. Viene dado por S(n, k) = 1 k! k X i=0 (−1)ik i(k−i)n, con nykenteros positivos. Por convenio, definimos S(n, 0) = 0 si n > 0 y S(0,0) = 1. Los primeros valores de los n´umeros de Stirling de segunda clase S(n, k) los recogemos en la siguiente tabla: n k k= 1 k= 2 k= 3 k= 4 k= 5 k= 6 k= 7 k= 8 k= 9 n= 1 1 n= 2 1 1 n= 3 1 3 1 n= 4 1 7 6 1 n= 5 1 15 25 10 1 n= 6 1 31 90 65 15 1 n= 7 1 63 301 350 140 21 1 n= 8 1 127 966 1701 1050 266 28 1 n= 9 1 255 3025 7770 6951 2646 462 36 1 Tabla 1.2: N´umeros de Stirling de segunda clase S(n, k) Ejemplo 1.2.21 El conjunto [4] tiene seis particiones en tres partes, consistiendo cada una de un bloque y dos simples. Las seis particiones son: 1.2. N´umeros de Stirling de segunda clase 23 {1} {2} {3,4} {1} {3} {2,4} {1} {4} {2,3} {2} {3} {1,4} {2} {4} {1,3} {3} {4} {1,2} Por lo tanto, S(4,3) = 6.  Notaci´on 1.2.22 Definimos el factorial descendente de xde grado ncomo (x)n=x(x−1) · · · (x−n+ 1), n = 1,2, . . . Expresando la n-´esima potencia de xen funci´on de los factoriales de los polinomios de xde grado n, conseguimos xn= n X k=0 S(n, k)(x)k, n = 0,1, . . . (1.7) Proposici´on 1.2.23 Definimos la funci´on generatriz doble para los n´umeros de Stirling de segunda clase como f(x, u) = ∞ X n=0 n X k=0 S(n, k)(x)k un n!=exu. Lema 1.2.24 Para todo kfijo, la funci´on generatriz exponencial de los n´umeros de Stirling de segunda clase viene dada por fk(u) = ∞ X n=k S(n, k)un n!=(eu−1)k k!, k = 0,1, . . . 24 CAP´ ITULO 1. Introducci´on Demostraci´on Cambiando el orden de sumaci´on en f(x, u), conseguimos f(x, u) = n X k=0 ∞ X n=k S(n, k)un n!(x)k= ∞ X k=0 fk(u)(x)k. Por otro lado, tenemos f(x, u) = exu = [1 + (eu−1)]x. Usando el desarrollo del Binomio de Newton (x+y)r= ∞ X k=0 r kxr−kyk, deducimos lo siguiente [1 + (eu−1)]x= ∞ X k=0 x k(eu−1)k= ∞ X k=0 (eu−1)k k!(x)k. Por tanto, comparando ambos coeficientes de xk, obtenemos el resultado fk(u) = (eu−1)k k!.  Los n´umeros de Stirling de segunda clase y los n´umeros Eulerianos est´an muy relacionados, como muestran los siguientes teoremas. Teorema 1.2.25 Para todos los enteros positivos nyr, se tiene S(n, r) = 1 r! r X k=0 A(n, k)n−k r−k.(1.8) Demostraci´on Si multiplicamos a ambos lados por r!, llegamos a que r!S(n, r) = r X k=0 A(n, k)n−k r−k. El lado izquierdo representa el n´umero ordenado de particiones, es decir, las particiones cuyo conjunto de bloques est´a totalmente ordenado, de [n] en rbloques. 1.2. N´umeros de Stirling de segunda clase 25 Demostraremos ahora que el lado derecho cuenta el mismo n´umero de objetos. Para ello tomamos una partici´on pcontada por A(n, k). Las krachas ascendentes de pdefinen una particı´on ordenada de [n] en kpartes. Si k=r, entonces no hay nada que probar. Si k < r, entonces separaremos algunas de las rachas ascendentes en varios bloques de elementos consecutivos, en orden, para conseguir una partici´on ordenada de rbloques. Ya que actualmente tiene kbloques, aumentamos el n´umero de bloques en r−k. Esto se puede conseguir eligiendo r−kde n−k “posiciones huecas”(huecos entre dos entradas consecutivas dentro del mismo bloque). Esto demuestra que podemos obtener r X k=0 A(n, k)n−k r−kparticiones ordenadas de [n] en rbloques por el procedimiento anterior. Adem´as cada partici´on puede ser obtenida exactamente una vez. De hecho, si escribimos los elementos dentro de cada bloque de la partici´on creciente, s´olo podemos leer las entradas de la partici´on ordenada de izquierda a derecha y conseguir una ´unica permutaci´on teniendo al menos rrachas ascendentes. Esto hace que podamos recuperar los huecos de las posiciones usadas.  Corolario 1.2.26 Para todos los enteros positivos nyk, se tiene A(n, k) = k X r=1 S(n, r)r!n−r k−r(−1)k−r.(1.9) Demostraci´on Consideramos la f´ormula (1.8) para cada r≤ky multiplicamos por r!, entonces r!S(n, r) = r X k=0 A(n, k)n−k r−k Si r= 1 1!·S(n, 1) = 1 X k=0 A(n, k)n−k 1−k=A(n, 1)n−1 0 32 CAP´ ITULO 2. Inversiones Demostraci´on Sea p=p1p2· · · pn+1 una (n+ 1)-permutaci´on con kinversiones donde k≤n. Si pn+1 =n+ 1, entonces podemos omitir n+ 1 desde el final de py conseguir una n-permutaci´on con kinversiones, lo que explica el segundo sumando del lado derecho de (2.2). Si pi=n+ 1 para i≤n, entonces intercambiamos n+ 1 y la entrada inmediatamente siguiente. Este resultado es una (n+ 1)-permutaci´on con k−1 inversiones en las cuales la entrada n+ 1 no es la primera posici´on. Sin embargo, toda (n+ 1)- permutaci´on con k−1 inversiones tiene esta propiedad (que n+ 1 no es la primera posici´on). Esto explica el primer sumando del lado derecho de (2.2). Por tanto, queda completa la demostraci´on y tambi´en el porqu´e la condici´on n≥kes necesaria.  Adem´as (2.2) no se verifica en general si k > n −1, pues si k > n 2 2entonces b(n+1, k)< b(n+1, k−1) lo que hace imposible b(n+1, k) = b(n+1, k−1)+b(n, k). La b´usqueda de una f´ormula expl´ıcita para los n´umeros b(n, k) es m´as dif´ıcil incluso si asumimos n≥k. Examinando el polinomio In(x) = (n 2) X k=0 b(n, k)xkpodemos deducir que: b(n, 0) = 1 = n 0 b(n, 1) = n−1 = n 1−n 0n≥1 b(n, 2) = n 2−n 0n≥2 b(n, 3) = n+ 1 3−n 1n≥3 b(n, 4) = n+ 2 4−n+ 1 2n≥4 Definici´on 2.1.8 Una composici´on de nen kpartes es una soluci´on de la ecuaci´on a1+a2+· · · +ak=ncon ai∈N+. 2.1. La funci´on generatriz del n´umero de inversiones para permutaciones 33 Definici´on 2.1.9 Sea nun entero positivo. Si a1+a2+· · · +ak=ny los aison todos enteros positivos, entonces decimos que la k-tupla (a1, a2, . . . , ak) es una composici´on d´ebil de nen kpartes. Observaci´on 2.1.10 El n´umero de composiciones de nen kpartes es n−1 k−1, mientras que el n´umero de composiciones d´ebiles de nen kpartes es n+k−1 k−1. Definici´on 2.1.11 Sea a1≥a2≥ · · · am≥1, enteros tales que a1+a2+· · · +am=n. Entonces el vector a= (a1, a2, . . . , am) se llama partici´on del entero ny los n´umeros aison las partes de la partici´on a. El n´umero total de particiones se denota por p(n). Ejemplo 2.1.12 Consideramos el entero 6. Las particiones de 6 son (6),(5,1),(4,2),(3,3),(4,1,1),(3,2,1),(2,2,2), (3,1,1,1),(2,2,1,1),(2,1,1,1,1),(1,1,1,1,1,1). Por tanto, p(6) = 11.  Definici´on 2.1.13 Se define el diagrama de Ferrers odiagrama de Young de una partici´on a= (a1, . . . , ak) de ncomo un arreglo de cajas cuadradas ordenadas en kfilas horizontales (justificadas a la izquierda) de tama˜nos a1, . . . , akrespectivamente ordenadas verticalmente. Ejemplo 2.1.14 El diagrama de Ferrers de (5,4,3,1) es 34 CAP´ ITULO 2. Inversiones  Definici´on 2.1.15 La partici´on conjugada de aes la partici´on a∗cuyo diagrama de Ferrers es el traspuesto del diagrama de a. Ejemplo 2.1.16 Considerando la partici´on del Ejemplo 2.1.14, vemos que a∗= (4,3,3,3,1) y su diagrama de Ferrers es el siguiente  2.2. ´ Indice mayor Definici´on 2.2.17 Sea p=p1p2· · · pnuna permutaci´on. Definimos D(p) como el conjunto de descensos de p. Ejemplo 2.2.18 Sea p= 4276135, entonces 1, 3 y 4 son los descensos de p, por lo que D(p) = 2.2. ´ Indice mayor 35 {1,3,4}.  Definici´on 2.2.19 Sea p=p1p2· · · pnuna permutaci´on y definimos el ´ındice mayor maj(p) de p como la suma de los descensos de p. Esto es, maj(p) = X i∈D(p) i. Ejemplo 2.2.20 Si p= 415623, entonces el conjunto de descensos D(p) = {1,4}ymaj(p) = 5.  Teorema 2.2.21 Para todos los enteros positivos ny todos los enteros no negativos k, hay tantas n-permutaciones con kinversiones como n-permutaciones con ´ındice mayor k. En otras palabras, el n´umero de inversiones y el ´ındice mayor est´an equidistribuidos en Sn. Un estad´ıstico sdefinido en el conjunto de permutaciones Snque tiene la misma distribuci´on que ise denomina Mahoniano. Demostraci´on Para cualquier permutaci´on p=p1p2· · · pn, decimos que pies una entrada grande si pi> pny llamamos a pientrada peque˜na si pi< pn. Vamos a ir probando el resultado recursivamente, definiendo una biyecci´on φ:Sn−→ Sn∀p∈Sn, donde la igualdad maj(p) = i(φ(p)) se mantiene. Nuestra aplicaci´on φtendr´a la caracter´ıstica adicional de mantener el ´ultimo elemento de pfijo. Lo probamos por inducci´on en n. Definimos φ(1) = 1 para el caso inicial de n= 1 y φ(12) = 12 y φ(21) = 21 para el caso n= 2. Asumimos que hemos definido φpara toda (n−1)-permutaci´on, con el fin de definir φpara todas las n-permutaciones. Sea p=p1p2· · · pncualquier n-permutaci´on. Distinguimos dos casos: 36 CAP´ ITULO 2. Inversiones 1. Primero consideramos el caso cuando pn−1es una entrada peque˜na. En este caso, tomamos wp=φ(p1p2· · · pn−1) = q1q2· · · qn−1. Sea qi1, qi2, . . . , qijlas entradas peque˜nas de pen wp. Fijamos io= 0. Sea Qj=qij−1+1 · · · qijque proporciona la ´unica descomposici´on de wen subpalabras que contienen exactamente una entrada peque˜na y la contiene en el ´ultimo lugar. Por ejemplo, si q1· · · q6= 537914, entonces hay dos entradas peque˜nas, 1 y 2 y por tanto Q1= 53 y Q2= 791. Ahora definimos f(Qj) = Qjsi Qjes a lo sumo de longitud 1 xmx1x2· · · xm−1si Qj=x1x2· · · xm, con m≥2 Finalmente, definimos f(wp) = f(Q1)f(Q2)· · · f(Qk) y φ(p) = f(wp)pn. Por ejemplo, sea n= 5 y p= 54213. Entonces tenemos wp=φ(5421) = 5421 yQ1= 542, Q2= 1. Por lo tanto, f(wp) = 2541, de manera que φ(p) = 25413. 2. Cuando pn−1es una entrada grande, el procedimiento es muy similar. La ´unica diferencia es en la definici´on de las subpalabras Qj. En este caso, Qj proporciona la ´unica descomposici´on de wen subpalabras que contienen exactamente una entrada grande y la contiene en la ´utima posici´on. Por ejemplo, sea n= 5 y p= 13452. Entonces tenemos wp=φ(1345) = 1345 yQ1= 13, Q2= 4, Q3= 5. Por lo tanto, f(wp) = 3145 y φ(p) = 31452. Es f´acil ver que φ:Sn−→ Snes una biyecci´on. De hecho, verificando ambos casos, vemos que la primera regla fue usada para crear φ(p) si y s´olo si el ´ultimo elemento de φ(p) es mayor que el primer elemento de φ(p). Una vez que conocemos la regla que fue usada para crear φ(p) podemos recuperar wpdesde f(wp). De hecho, si la primera (respectivamente segunda) regla fue usada, entonces f(Qi) son las subpalabras que contienen s´olo una entrada peque˜na (respectivamente grande) y contiene la entrada peque˜na (respectivamente grande) en la primera (respectivamente ´ultima) posici´on. Como fes una biyecci´on, 2.3. Una aplicaci´on. Determinantes y grafos 37 es posible recuperar Qidesde f(Qi) y por tanto es posible recuperar wp. Finalmente, φ:Sn−1−→ Sn−1es una biyecci´on por inducci´on, por eso, recuperamos p1p2· · · pn−1desde f(p1p2· · · pn−1) = wp. Todav´ıa, necesitamos probar que φ:Sn−→ Sntiene la propiedad deseada, es decir, transforma una permutaci´on con ´ındice mayor ken una permutaci´on con k inversiones. Probamos esto, considerando, los dos casos de arriba por separado. 1. Cuando pn−1es una entrada peque˜na, entonces maj(p) = maj(p1p2· · · pn−1) = i(φ(p1p2· · · pn−1)) = i(wp)(2.3) ¿C´omo cambia la aplicaci´on fel n´umero de inversiones de wp? No cambia el orden entre las entradas peque˜nas ni entre las entradas grandes. Si una entrada peque˜na pertenece a la subpalabra Qjde longitud t > 1, entonces salta hacia delante y pasa a preceder a t−1 entradas grandes de Qj, decreciendo el n´umero de inversiones por t−1. Como cada entrada grande ser´ıa precedida por una entrada peque˜na, la disminuci´on total en el n´umero de inversiones es igual al n´umero de entradas grandes, es decir, n−pn. Sin embargo, fijando pnal final de f(wp) crearemos precisamente n−pnnuevas inversiones. Por lo tanto i(φ(p)) = i(f(wp)pn) = i(wp) la cual comparada con (2.3) demuestra que maj(p) = i(φ(p)) como quer´ıamos. 2. Cuando pn−1es una entrada grande, entonces maj(p) = maj(p1p2· · · pn−1)+(n−1) (2.4) =i(φ(p1p2· · · pn−1)) + n−1 = i(wp) + n−1(2.5) Cuando fse aplica a wp, cada entrada grande salta perteneciendo a una subpalabra de longitud t > 1, salta hacia delante, pasa todas las t−1 entradas peque˜nas de la subpalabra e incrementa el n´umero de inversiones por t−1. Cada entrada peque˜na es pasada por una entrada grande, por eso, el incremento en total en el n´umero de inversiones es igual al n´umero de entradas peque˜nas, es decir, pn−1. Por otro lado, fijando pnal final de f(wp) crear´a precisamente n−pnnuevas inversiones. Por lo tanto i(φ(p)) = i(f(wp))pn=i(wp)+(pn−1) + (n−pn) = i(wp) + n−1 la cual comparada con (2.4) demuestra que otra vez maj(p) = i(φ(p)) como quer´ıamos.  38 CAP´ ITULO 2. Inversiones 2.3. Una aplicaci´on. Determinantes y grafos 2.3.1. La definici´on expl´ıcita de los determinantes Algunos autores definen el determinante de una matriz cuadrada de dimensi´on nde forma recursiva: Si n= 1, det(a) = a. Si n= 2, deta b c d =ad −bc. Si n > 2, detA= n X j=1 (−1)j−1a1jA1j donde Aij es la matriz de dimensiones (n−1) ×(n−1) y j-´esima columna de A. Veremos que esta definici´on recursiva implica el siguiente resultado. Teorema 2.3.22 Sea A= (aij) una matriz n×n. Entonces tenemos detA=X p∈Sn (−1)i(p)a1p1a2p2· · · anpn.(2.6) Esto es, el determinante de Ase obtiene tomando todas las n! posibles n-tuplas de entradas en cada fila y cada columna y multiplicando los elementos de cada n-tupla juntoS. Finalmente tomamos una suma de estos n! productos, donde el signo es determinado por la paridad de i(p) y pes una permutaci´on determinada por cada n-tupla elegida. En otras palabras, las n-tuplas corresponden a todas las posibles colocaciones de ntorres en un tablero de ajedrez de n×nde manera que no hay dos de ellos pegado con otro. Demostraci´on Probamos el teorema por inducci´on en n. 2.3. Una aplicaci´on. Determinantes y grafos 39 Los casos iniciales n= 1 y n= 2 son obvios. Asumimos que es cierto para matrices de dimensi´on (n−1) ×(n−1), lo que significa que detA1j=X q (−1)i(q)a2q2a3q3· · · anqn(2.7) donde q=q1q2· · · qnes una permutaci´on parcial, eso es, una lista ordenada de enteros 1,2, . . . , j −1, j + 1, . . . , n. Por lo tanto, a1j·det A1jcontribuir´a a los productos de todas las n-tuplas empezando con a1jpara detA. En otras palabras, a1j·det A1jcorresponder´a a todas las colocaciones de torres en posici´on de no ataque en cuales, hay una torre en posici´on jde la primera fila. Este argumento se puede aplicar para cada j. Por eso, el teorema se probar´a si podemos demostrar que los signos de esos productos son los adecuados. Sustituyendo la expresi´on probada por A1jpor la f´ormula (2.7) vemos que el signo de la n-tupla que pertenece a qes (−1)j+i(q). Y de hecho, la permutaci´on p=jq2q3· · · qntiene precisamente j−1 inversiones m´as que la permutaci´on parcial q=q2q3· · · qnpuesto que jes m´as grande que los otros j−1 elementos. Esto demuestra que la n-tupla tiene signo (−1)j−1.  Ejemplo 2.3.23 Sea n= 3. Hay tres 3-permutaciones con un n´umero par de inversiones, 123, 312, 231 y hay tres 3-permutaciones con un n´umero impar de inversiones, 132, 213 y 321. Entonces tenemos que: det A=a11a22a33 +a13a21a32 +a12a23a31 −a11a23a32 −a12a21a33 −a13a22a31.  2.3.2. Matchings perfectos en grafos bipartitos Definici´on 2.3.24 Un grafo es un par G= (V, E), donde Ves un conjunto de v´ertices o nodos (normalmente finito) y Eun conjunto de aristas o arcos que relacionan estos nodos, 40 CAP´ ITULO 2. Inversiones representando relaciones binarias entre los elementos de un conjunto. Definici´on 2.3.25 Se llama orden del grafo G= (V, E) al n´umero de v´ertices de G. Se representa por |V|. Definici´on 2.3.26 Un par no ordenado es un conjunto de la forma {a, b}, de manera que {a, b}= {b, a}. Para los grafos, estos conjuntos pertenecen al conjunto de las partes de V, denotado por P(V). Si el conjunto Vtiene nelementos, entonces su cardinal viene dado por |P(V)|=n 0+n 1+· · · +n k+· · · +n n= 2n= 2|V|. Ejemplo 2.3.27 Sea el conjunto A={1,2,3}. El conjunto de partes de Aes: {∅,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}} y su cardinal |P(A)|= 23= 8.  Definici´on 2.3.28 Decimos que G= (V, E) es un grafo no dirigido o simplemente un grafo si V6=∅yE⊆ {x∈ P(V) : |x|= 2}es un conjunto de pares no ordenados de elementos de V. Un ejemplo de grafo no dirigido es el siguiente: 16 4 5 2 2.3. Una aplicaci´on. Determinantes y grafos 41 Definici´on 2.3.29 Un par ordenado es una pareja de objetos en la que se distingue un elemento de otro. El par ordenado cuyo primer elemento es ay segundo elemento bse denota por (a, b), que es diferente del par (b, a), en cuyo caso, el primer elemento es by el segundo a. Definici´on 2.3.30 Decimos que G= (V, E) es un grafo dirigido si V6=∅yE⊆ {(a, b)∈V×V: a6=b}es un conjunto de pares ordenados de elementos de V. Es decir, una arista (a, b) tiene como nodo inicial a ay como nodo final a b. Un ejemplo de grafo dirigido es el siguiente: 16 4 5 2 Definici´on 2.3.31 La matriz de incidencia de un grafo Ges la matriz C(G) = (cij) en la cual cij =1 si la arista iincide en el v´ertice j 0 en otro caso Luego, la suma de los 1’s en cada fila indica la cantidad de aristas que inciden sobre ese nodo. Ejemplo 2.3.32 Consideremos el grafo siguiente: 48 CAP´ ITULO 3. Introducci´on del conjunto [n]. Ejemplo 3.1.2 Sea 43251 una permutaci´on de longitud cinco. Entonces decimos que la funci´on f: [5] →[5] definida por f(1) = 4, f(2) = 3, f(3) = 2, f(4) = 5 y f(5) = 1 es una permutaci´on de [5].  Definici´on 3.1.3 Sean fygdos permutaciones de [n]. Podemos definir su producto f·gcomo (f·g)(i) = g(f(i)) para i∈[n], es decir, el producto de dos permutaciones se define como la composici´on de ´estas. Ejemplo 3.1.4 Consideramos las permutaciones σ=1 2 3 4 5 6 3 2 5 6 4 1  y τ=1 2 3 4 5 6 4 1 5 3 6 2  Luego; σ◦τ=1 2 3 4 5 6 6 3 4 5 1 2  El conjunto de todas las permutaciones de [n] forman un grupo cuando lo dotamos con esta operaci´on. Por tanto, el conjunto de todas las permutaciones de [n] se denota por Sny se llama grupo sim´etrico de grado n, es decir, Snrepresenta el grupo de las biyecciones del conjunto {1, . . . , n}sobre s´ı mismo. Adem´as cada grupo finito de n elementos es un subgrupo de Sn. Proposici´on 3.1.5 El conjunto de las permutaciones Snverifica las siguientes propiedades: 3.1. Descomposici´on de una permutaci´on en ciclos 49 1. Snes un grupo finito con |Sn|=n!. 2. Si n > 2, entonces Snno es abeliano, por eso, en general fg 6=gf. Una forma de escribir las permutaciones es mediante la notaci´on c´ıclica, por ejemplo, f= (13)(245). Cuando leemos una permutaci´on en esta notaci´on, hacemos una aplicaci´on con cada elemento y el que se une a su derecha, excepto para los elementos finales de cada ciclo, que se asignan al primer elemento de dicho ciclo. Definici´on 3.1.6 Un elemento σ∈Snes un ciclo de longitud m(m≤n) cuando existe I={a1, a2, . . . , am}⊂{1,2, . . . , n} tal que: 1. σ(ai) = ai+1 ∀i= 1,2, . . . , m −1, σ(am) = a1 2. σ(j) = j∀j6∈ I Es decir, el ciclo σlo notaremos simplemente por (a1a2· · · am) y al n´umero mlo llamaremos longitud del ciclo σ. Con este notaci´on se tiene (a1a2· · · am) = (a2· · · ama1) = · · · = (ama1· · · am−1). Definici´on 3.1.7 Diremos que dos ciclos (a1· · · am) y (b1· · · br) son disjuntos si ∀i, j 1≤i≤m, 1≤j≤r, ai6=bj. Luego, si σ, τ ∈Sn, son dos ciclos disjuntos, se tiene que στ =τσ. Definici´on 3.1.8 Sea σ∈Sncon σ=σ1· · · σkla descomposici´on de σen producto de ciclos disjuntos. Entonces, el orden de σse define como o(σ) = mcm(o(σ1), . . . , o(σk)). 50 CAP´ ITULO 3. Introducci´on Ejemplo 3.1.9 En S7, la siguiente permutaci´on se descompone en ciclos disjuntos de la siguiente forma 1234567 3657124= (135)(26)(47)  Ejemplo 3.1.10 La permutaci´on f= 34152 indica que fpermuta c´ıclicamente los elementos 3 y 1 entre ellos y los elementos 2,4,5 entre ellos. Este fen´omeno est´a ilustrado a continuaci´on: 1 4 5 2 3  Ejemplo 3.1.11 Sea g= (12)(356)(4) una permutaci´on, para la cual podemos hacer las siguientes precisiones: Primero, si los ciclos son disjuntos, el orden entre los ciclos no importa, es decir, (12)(356)(4) = (356)(4)(12) = (4)(12)(356) De hecho, la imagen de cada i∈[n] s´olo depende de la posici´on dentro del ciclo y algunos otros elementos en el ciclo. Segundo, si un ciclo tiene al menos tres elementos, entonces el orden de los elementos dentro de cada ciclo importa hasta un cierto punto. De hecho, los ciclos (356), (563) y (635) describen la misma acci´on de gen los elementos 3, 5 y 6.  3.1. Descomposici´on de una permutaci´on en ciclos 51 Nos gustar´ıa tener un ´unico modo de escribir nuestras permutaciones usando la notaci´on de ciclos. Por tanto, escribiremos el elemento m´as grande de cada ciclo primero y organizaremos los ciclos en orden creciente de sus primeros elementos. Este modo de escribir las permutaciones se llama notaci´on c´ıclica can´onica. Ejemplo 3.1.12 La permutaci´on (312)(45)(8)(976) est´a en notaci´on c´ıclica can´onica.  Definici´on 3.1.13 Una trasposici´on es un ciclo de orden dos. Teorema 3.1.14 Toda permutaci´on de Sn, distinta de 1, se puede descomponer como producto de trasposiciones. Demostraci´on Basta probar que todo ciclo de Snpuede ser compuesta en producto de trasposciones. Sea, pues σ= (a1a2· · · am), entonces (a1a2· · · am) = (a1am)· · · (a1a3)(a1a2).  Ejemplo 3.1.15 Haciendo uso del Ejemplo 3.1.9, tenemos que la descomposci´on en trasposiciones es la siguiente: 1234567 3657124= (135)(26)(47) = (15)(13)(26)(47).  Nota 3.1.16 La descomposici´on de una permutaci´on como producto de trasposiciones no es 52 CAP´ ITULO 3. Introducci´on ´unica. Por ejemplo (23) = (13)(23)(12). 3.1.1. Una aplicaci´on. Signo y determinantes La descomposici´on en ciclos de una permutaci´on faporta mucha informaci´on sobre f. Un modo com´un de ajustar las permutaciones en los marcos algebr´aicos es definiendo matrices de permutaci´on es decir, matrices cuadradas cuyas entradas son todas igual a 0 ´o 1 y contienen exactamente un 1 en cada fila y cada columna. Hay dos formas igualmente ´utiles para hacer esto. Sea p=p1p2· · · pnuna n-permutaci´on y sea Apuna matriz de dimensi´on n×n Ap(j, i) = 1 si pi=j 0 en otro caso Adem´as la aplicaci´on f:Sn→Rn×ndefinida por f(p) = Apes un homomorfismo, es decir, Apq =ApAq. Por ejemplo, si p= 3421 = (4132), entonces tenemos Ap=    0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0     . Ahora sea, Bp, una matriz de dimensi´on n×ndefinida por Bp(i, j) = 1 si pi=j 0 en otro caso Entonces Bp=    0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0     . Para cualquier p, la matriz Bpes la traspuesta de Ap. Adem´as, ApBp=BpAp=I as´ı que ApyBpson inversas una de la otra. Por tanto, la inversa de una matriz de permutaci´on es su traspuesta. 3.2. Permutaciones pares e impares 53 Comparando las definiciones de ApyBp, podemos preguntarnos cuando la primera es m´as f´acil de usar y cuando lo es la segunda. La ventaja de la primera definici´on es que la aplicaci´on f:Sn→Rn×ndefinida por f(p) = Apes un homomorfismo. Esto no es verdad para la aplicaci´on g:Sn→Rn×ndefinida por g(p) = Bp. Esta aplicaci´on es un anti-homomorfismo, es decir, Bpq =BqBp. Esto puede ser ´util cuando usamos nuestras matrices para permutar vectores de tama˜no n. Por ejemplo, sea x=    x1 x2 x3 x4     Si la permutaci´on p= 3421 = (4132) act´ua en las coordenadas de estos vectores, lleva el vector xen p(x) =     x3 x4 x2 x1     obtendr´ıamos este vector simplemente tomando el producto Bpx. Si ahora otra permutaci´on qact´ua en el vector p(x), entonces obtenemos la imagen calculando Bq(Bpx) = Bpq(x). Si en lugar del vector columna x, hemos trabajado con el vector fila y= (y1, y2, y3, y4), entonces usaremos las matrices ApyAqpara calcular las im´agenes y yApyyApq =yApAq. 3.2. Permutaciones pares e impares Una permutaci´on de un conjunto finito Wnya sea un ciclo o una descomposici´on en ciclos disjuntos, la descomposici´on es ´unica salvo reordenamiento de ciclos. Adem´as, cada ciclo se puede generar por trasposiciones. De hecho, un ciclo (wi) de longitud 1 se puede generar como (wi) = (wiwj)(wjwi), i 6=j, mientras que un ciclo (wi1wi2· · · wik−1wik) de longitud k≥2 se puede generar por k−1 trasposiciones como (wi1wi2· · · wik−1wik) = (wi1wik)(wi1wik−1)· · · (wi1wi2) Como consecuencia, una permutaci´on de un conjunto finito Wnse puede descomponer en trasposiciones. Pero mientras que la descomposici´on de una permutaci´on en ciclos disjuntos es ´unica salvo reordenamiento de ciclos, la descomposici´on en trasposiciones entre los que tienen dos o m´as elementos en com´un se puede realizar de diferentes formas. Sin embargo, en estas descomposiciones diferentes de una permutaci´on, el n´umero de trasposiciones es en cualquiera de los casos par o impar. 54 CAP´ ITULO 3. Introducci´on Definici´on 3.2.17 Una permutaci´on se llama impar si tiene un n´umero impar de trasposiciones. An´alogamente, una permutaci´on se llama par si tiene un n´umero par de trasposiciones. Ejemplo 3.2.18 Consideramos el conjunto {1,2,3}el cual tiene 6 permutaciones: (12),(13),(23),(123),(231),Id . Entonces (12), (13) y (23) son permutaciones impares, pues son una ´unica trasposici´on; en cambio, (123) = (13)(12), (231) = (21)(23) e Id son permutaciones pares, pues estan formadas por dos trasposiciones.  La siguiente proposici´on demuestra que tenemos que ser cuidadosos con las palabras impar y par, ya que un ciclo es par, (impar) si est´a formado por un n´umero impar, (par) de elementos, respectivamente. Porposici´on 3.2.19 Una permutaci´on que consta de exactamente un ciclo par, (impar) es impar, (par) respectivamente. Demostraci´on Probamos por inducci´on en n, longitud de un ciclo. •Para n= 1 y n= 2, la afirmaci´on es cierta. •Ahora, sea n≥3 y consideramos el ciclo (p1p2· · · pn) de tal forma que (p1p2· · · pn)=(p1p2· · · pn−1)(pn−1pn). La multiplicaci´on por (pn−1pn) al final simplemente intercambia las ´ultimas dos entradas de (p1p2· · · pn−1) y por tanto, se incrementa el n´umero de inversiones en una unidad o decrece en una unidad. En cualquiera de los dos casos, cambia la paridad del n´umero de inversiones. Luego, la prueba se tiene por inducci´on en la hip´otesis.  3.3. Tipos de permutaciones 55 Lema 3.2.20 Sea puna permutaci´on. Entonces las siguientes afirmaciones son equivalentes. (i) pes par. (ii) det Ap= det Bp= 1. (iii) El n´umero de ciclos par de pes par. Demostraci´on (i)⇔(ii). Esto se tiene por la definici´on de determinantes, pues el determinante de una matriz de permutaci´on Bps´olo tiene un t´ermino distinto de cero y este es (−1)i(p) n Y i=1 bip(i). El resultado se tiene con cada t´ermino ya que el signo del producto es igual a 1. (ii)⇔(iii). Puesto que pes el producto de sus ciclos, por la Proposici´on 3.2.19, los ciclos pares corresponden a permutaciones impares, por eso el determinante de sus matrices de permutaci´on es −1. Por tanto, tiene que haber un n´umero par de ellos para que el determinante de su producto sea 1.  En particular, el producto de dos permutaciones pares es par y la inversa de una permutaci´on par es par. Como la permutaci´on identidad es par, el conjunto de todas las permutaciones pares en Snforman un subgrupo. Este subgrupo se llama grupo alternado de grado n, se denota por Any tiene n! 2elementos para n≥2. Sabemos que Anes un grupo simple si n≥5, es decir, s´olo tiene como subgrupos normales al grupo trivial y a s´ı mismo. Adem´as Anes mayor que cualquier subgrupo propio de Sn. De hecho, otro subgrupo propio de Sn es de tama˜no al menos (n−1)!. 56 CAP´ ITULO 3. Introducci´on 3.3. Tipos de permutaciones Es com´un preguntarse cu´antas n-permutaciones tienen una estructura de ciclo dado, por ejemplo, cu´antas 12-permutaciones contienen un 4-ciclo, dos 3-ciclos, un 2-ciclo y cero 1-ciclo. Otra cuesti´on ser´ıa cu´antas n-permutaciones tienen exactamente kciclos. Para facilitar la respuesta de la primera cuesti´on, creamos la siguiente definici´on. 3.3.1. El tipo de una permutaci´on Definici´on 3.3.21 Sea puna n-permutaci´on que tiene exactamente aiciclos de longitud ipara todos los enteros positivos i∈[n]. Entonces decimos que pes de tipo (a1, a2, . . . , an). Ejemplo 3.3.22 La permutaci´on p= (4)(56)(27398) es de tipo (1,1,0,0,1,0,0,0,0).  Proposici´on 3.3.23 Sea (a1, a2, . . . , an) una n-tupla de enteros no negativos tales que n X i=1 aii=n. Entonces el n´umero de n-permutaciones del tipo (a1, a2, . . . , an) es n! a1!a2!· · · an!1a12a2· · · nan. Demostraci´on Escribimos los elementos de [n] en orden lineal en uno de los n! modos posibles. A continuaci´on colocamos par´entesis entre los n´umeros de tal forma que las primeras a1entradas son los a1ciclos de longitud 1, las siguientes 2a2entradas forman los a2 ciclos de longitud 2, etc. 3.3. Tipos de permutaciones 57 Las permutaciones que obtenemos de este modo ser´an del tipo (a1, a2, . . . , an), pero no ser´an todas diferentes. De hecho, los conjuntos de entradas que forman ciclos de la misma longitud pueden ser permutados entre s´ı sin cambiar el resultado de la permutaci´on. Por tanto, obtenemos cada permutaci´on de a1!a2!· · · an! ´ordenes lineales permutando ciclos de la misma longitud. Finalmente, cada i-ciclo se puede obtener de imodos diferentes pues cualquier entrada puede ser la primera posici´on. Por lo que incluso, si fijamos los conjuntos de entradas en cada ciclo, hay 1a12a2· · · nan ´ordenes lineales diferentes que podr´ıan dar lugar a cualquier permutaci´on del tipo (a1, a2, . . . , an). Esto demuestra, en general, que cada permutaci´on se obtiene de a1!a2!· · · an!1a12a2· · · nan ´ordenes lineales lo que prueba el resultado.  Como consecuencia del resultado anterior, sabemos que existen (n−1)! permutaciones de longitud nque constan de un n-ciclo y (2n)! n!2npermutaciones de longitud 2nque constan de nciclos de longitud 2. 3.3.2. Una aplicaci´on. Permutaciones conjugadas Definici´on 3.3.24 En el grupo sim´etrico Sndos permutaciones gyhse dicen conjugadas la una de la otra si existe un elemento f∈Sntalque fgf−1. En otras palabras, dos permutaciones son conjugadas en Snsi y s´olo si se obtienen como composici´on del mismo n´umero de ciclos disjuntos de las mismas longitudes. Observaci´on 3.3.25 La relaci´on “gyhson permutaciones conjugadas” es una relaci´on de equivalencia. 64 CAP´ ITULO 3. Introducci´on Demostraci´on Derivamos nuestra funci´on generatriz fk(u) y despu´es desplazamos los ´ındices por uno, consiguiendo ∞ X n=k s(n+ 1, k + 1)un n!=(1 + u)−1[ln(1 + u)]k k!= = exp(−ln(1 + u))[ln(1 + u)]k k!= = ∞ X m=k (−1)m[ln(1 + u)]m m!·[ln(1 + u)]k k!= = ∞ X m=k (−1)m−k[ln(1 + u)]m (m−k)!k! Notamos que fk(u) es muy similar al ´ultimo miembro de la ´ultima expresi´on, esto indica que reorganiz´andolo conseguimos ∞ X n=k s(n+ 1, k + 1)un n!= ∞ X m=k (−1)m−km k∞ X n=m s(n, m)un n!= = ∞ X n=k"n X m=k (−1)m−km ks(n, m)#un n!, y el resultado se obtiene comparando los coeficientes de un n!.  65 Cap´ıtulo 4 Aplicaciones 4.1. Test de rachas ascendentes y descendentes 4.1.1. Introducci´on Deinici´on 4.1.1 Se definen las secuencias pseudo-aleatorias como aquellas secuencias cuyos elementos disponen de propiedades similares a las secuencias aleatorias. Los generadores de uso m´as frecuentes para estas secuencias son de la forma: xi+1 =kxi+c mod(m), i = 0,1,2, . . . (4.1) donde i, k, c yx0son enteros menores que m; la secuencia {xi/m con i= 1,2, . . .} se considera una secuencia aleatoria procedente de una distribuci´on uniforme (0,1). Un generador de esta forma se llama congruente multiplicativo si c= 0 y congruente mixto si c6= 0. El objetivo est´a en asegurarnos una elecci´on adecuada de k, c ymde tal forma que los elementos de una secuencia no se repitan hasta que se haya generado un n´umero suficiente de elementos y pasen por ciertos test estad´ısticos. Emp´ıricamente, se ha comprobado que si una secuencia pseudo-aleatoria generada por algunos de los algoritmos anteriores no supera alguno de los test de aleatoriedad cl´asica, entonces tampoco supera los test de rachas ascendentes y descendentes, lo cual evidencia que estos test son bastante potentes. 66 CAP´ ITULO 4. Aplicaciones 4.1.2. Test de rachas ascendentes y descendentes Consideramos una secuencia {xi;i= 1,2, . . . , n} generada por un generador de n´umeros pseudo-aleatorio. Hay varios tipos de rachas ascendentes de longitud r: Rachas internas: xi−1> xi< xi+1 <· · · < xi+r> xi+r+1 Rachas iniciales: x1< x2<· · · < xr+1 > xr+2,1≤r < n −2 Rachas finales: xn−r−1> xn−r< xn−r+1 <· · · < xn,1≤r≤n−2 Rachas completas: x1< x2<· · · < xn De forma an´aloga se definen las rachas descendentes. Ejemplo 4.1.2 Consideramos la secuencia S={33,42,5,17,47,12,10,3,9}; si leemos de izquierda a derecha vemos que existen: - Una racha ascendente de longitud 1. - Una racha descendente de longitud 1. - Una racha ascendente de longitud 2. - Una racha descendente de longitud 3. - Una racha ascendente de longitud 1.  4.1.Test de rachas ascendentes y descendentes 67 El test de rachas ascendentes y descendentes se basa es la comparaci´on de los n´umeros esperados y reales entre rachas de varias longitudes. A continuaci´on mostraremos algunos resultados importantes con respecto a las rachas, son las “disposiciones especiales”de las secuencias mon´otonas. Consideramos un secuencia {ui;i= 1,2, . . . , m;ui> uj⇔i>j}(4.2) es decir, una secuencia de minecuaciones en orden ascendente de magnitud. Una secuencia {xi;i= 1,2, . . . , m}, obtenida a partir de permutaciones de la secuencia (4.2) se dice que son “disposiciones especiales”de u1, u2, . . . , umsi x1> x2<· · · < xm−1> xm. Luego, el n´umero de “ disposiciones especiales”viene dado por: Si (x2=u1yxm−1=um) = (m−2)(m−3) ya que tenemos (m−2) posibilidades para elegir el valor de x1y (m−3) para elegir el valor de xm. Si (x1=umyx2=u1)=(m−3) esto obliga a que xm=um−1, por tanto tenemos (m−3) posibilidades de colocar el resto de elementos. Si (xm=u1yxm−1=um) = (m−3) esto obliga a que x1=um, por tanto tenemos (m−3) posibilidades de colocar el resto de elementos. Si (xm=u1yxm−1=um) = 1 pues s´olo tenemos una posibilidad de colocar el resto de elementos. Por tanto, el n´umero total de disposiciones especiales es (m−2)(m−3) + (m−3) + (m−3) + 1 = m2−3m+ 1. Si cada disposici´on es igualmente probable, la probabilidad de que ocurra cualquier disposici´on es 1 m!, por lo que la probabilidad de las disposiciones especiales es (m2−3m+ 1) m!.(4.3) En una secuencia pseudo-aleatoria de longitud nhay (n−r−2) subsecuencias xi−1, xi, . . . , xn−r. Por tanto, si xi−1> xi< xi+1 <· · · < xi+r> xi+r+1 (4.4) 68 CAP´ ITULO 4. Aplicaciones la subsecuencia es una “disposici´on especial”de (r+ 3) n´umeros; pero (4.4) es la condici´on que define las rachas ascendentes de longitud r. Luego, la esperanza de las rachas ascendentes de longitud rse deriva de la expresi´on (4.3) tomando m=r+ 3 ((r+ 3)2−3(r+ 3) + 1)(n−r−2) (r+ 3)! =(r2+ 3r+ 1)(n−r−2) (r+ 3)! , r ≤n−2 (4.5) y por simetr´ıa, esta expresi´on representa tambi´en la esperanza del n´umero de rachas descendentes. Si consideramos las disposiciones de la forma x1< x2<· · · < xm−1> xm. La esperanza de las rachas de longitud res 4 (r+ 1) (r+ 2)! si r < n −1. Como hay n! posibles disposiciones de nn´umeros, la esperanza de la racha completa es 2 n!. Agrupando estos resultados, la esperanza del n´umero de rachas descendentes de longitud rviene dada por E(r) =              2×(r2+ 3r+ 1)(n−r−2) (r+ 3)! + 4 ×(r+ 1) (r+ 2)! = 2n(r2+ 3r+ 1)n−(r3+ 3r2−r−4) (r+ 3)! osi r < n −1 2 n!si r =n−1 (4.6) Entonces el valor esperado del n´umero de rachas descendentes de longitud mayor o igual que res: E1(r) = n−1 X α=r E(α). Ahora, para cualquier (a0, a1, a2, a3) tal que 3 X i=0 ai= 0 se define Sr(a0, a1, a2, a3, . . . , am) = n−2 X α=r m X i=0 ai (α+i−1)!, r ≥1 =a0 (r−1)! +a0+a1 r!+a0+a1+a2 (r+ 1)! +a0+a1+a2+a3 (r+ 2)! +· · · +a0+a1+· · · +am (n−m)! +· · · +am−3+am−2+am−1+am (n−2)! +am−2+am−1+am (n−1)! +am−1+am n!+am (n+ 1)! (4.7) 4.1.Test de rachas ascendentes y descendentes 69 Consideramos ahora E(α), para α < n −1. Observamos los dos t´erminos que constituyen el numerador de (4.6), los cuales pueden ser escritos como α2+ 3α+ 1 = (α+ 3)(α+ 2) −2(α+ 3) + 1 donde a1= 1, a2=−2, a3= 1 y α3+ 3α2−α−4 = (α+ 3)(α+ 2)(α+ 1) −3(α+ 3)(α+ 2) + 3(α+ 3) −1 donde a0= 1, a1=−3, a2= 3, a3=−1 Usando las expresiones (4.6), (4.7) y m= 3, llegamos a E1(r) = 2 ×nSr(0,1,−2,1) −Sr(1,−3,3,−1) + 1 n! = 2 ×"n×n0 (r−1)! +1 r!+0+1−2 (r+ 1)! +0+1−2+1 (r+ 2)! +0+1−2+1 (n−2)! +1−2+1 (n−1)! +−2+1 n!+1 (n+ 1)!o− 1 (r−1)! +1−3 r!+1−3+3 (r+ 1)! +1−3+3−1 (r+ 2)! +1−3+3−1 (n−2)! +−3+3−1 (n−1)! +3−1 n!+−1 (n+ 1)!!+1 n!# = 2 ×"n×n1 r!−−1 (r+ 1)! −−1 n!+1 (n+ 1)!o −1 (r−1)! +2 r!−1 (r+ 1)! +1 (n−1)! −2 n!+1 (n+ 1)! +1 n!# = 2 ×((r+ 1)n−(r2+r−1) (r+ 2)! ),1≤r≤n−1.(4.8) Por otro lado, el n´umero esperado de rachas es E1(1) = 2n−1 3. Usando la epxresi´on (4.6) tenemos 3 2n−1n−1 X r=1 rE(r) = 6 2n−1"n−2 X r=1 (nr(r2+ 3r+ 1) −r(r3+ 3r2+r−4) (r+ 3)! )+n−1 n!# (4.9) Calculando los t´erminos del numerador por separado, obtenemos r(r2+ 3r+ 1) = (r+ 3)(r+ 2)(r+ 1) + a(r+ 3)(r+ 2) + b(r+ 3) + c Si r=−3; −3(9 −9 + 1) = c⇒c=−3 70 CAP´ ITULO 4. Aplicaciones Si r=−2; −2(4 −6 + 1) = b−3⇒b= 5 Si r=−1; −1(1 −3 + 1) = 2a+ 10 −3⇒a=−3 r(r3+3r2+r−4) = (r+3)(r+2)(r+1)r+a(r+3)(r+2)(r+1)+b(r+3)(r+2)+c(r+3)+d Si r=−3; −3(−27 + 27 −3−4) = d⇒d= 21 Si r=−2; −2(−8 + 12 −2−4) = c+ 21 ⇒c=−17 Si r=−1; −1(−1+3−1−4) = 2b−34 + 21 ⇒b= 8 Si r= 0; 0 = 6a+ 48 −51 + 21 ⇒a=−3 y entonces la longitud media de una racha es: 6 2n−1(nS1{1,−3,5,−3} − S1{1,−3,8,−17,21}+n−1 n!). Por tanto, para obtener el test generamos una secuencia de n´umeros N1, N2, . . . donde Nres el n´umero de rachas de longitud ren la secuencia. Levene y Wolfowitz en 1944 demostraron que para un ngrande el estad´ıstico X α (Nα−E[α])2 E[α] sigue un distribuci´on χ2. Sin embargo, en 1954, Cochran sugiri´o que tales aproximaciones son buenas s´olo cuando el 80 % de los valores esperados es mayor que 5. Cuando αaumenta, E[α], se hace r´apidamente menor que 5, por eso n−1 X α=r Nα−E1[α]!2 E1[α]. Por lo tanto, r−1 X α=1 (Nα−E[α])2 E[α]+ n−1 X α=r Nα−E1[r]!2 E1[r](4.10) sigue una distribuci´on χ2con r−1 grados de libertad. 4.2. Aplicaciones de los n´umeros de Stirling al c´alculo de momentos 71 Ejemplo 4.1.3 Consideramos una secuencia de n= 500 n´umeros con N1= 180, N2= 90, N3= 30, N4= 8, N5= 2, N6= 0 y N7= 1. Usando (4.6) obtenemos: E(1) = 2(1 + 3 + 1)500 −(1 + 3 −1−4) 4! = 208,4 E(2) = 2(4 + 6 + 1)500 −(8 + 12 −2−4) 5! = 91,4 E(3) = 2(9 + 9 + 1)500 −(27 + 27 −3−4) 6! = 26,3 E(4) = 2(16 + 12 + 1)500 −(64 + 64 −4−4) 7! = 5,71 E(5) = 2(25 + 15 + 1)500 −(125 + 75 −5−4) 8! = 1,01 Por otro lado, por la expresi´on (4.10) tomando r= 5 tenemos: ((N1−E(1))2 E(1) +((N2−E(2))2 E(2) +((N3−E(3))2 E(3) +((N4−E(4))2 E(4) +((N5−E1(5))2 E1(5) Luego, sustituyendo cada valor: χ2 4=(180 −208,4)2 208,4+(90 −91,4)2 91,4+(30 −26,3)2 26,3+(8 −5,71)2 5,71 +((N5−E1(5))2 E1(5) = 3,87 + 0,02 + 0,52 + 0,92 + ((N5−E1(5))2 E1(5) Ahora calculamos E1(5) usando (4.8): E0(5) = 2(5 + 1)500 −(25 + 5 −1) 7! = 1,18 Por tanto, sustituyendo en la expresi´on anterior: χ2 4= 3,87 + 0,02 + 0,52 + 0,92 + 2,81 = 8,13. Como conclusi´on, vemos que no hay evidencias significativas al nivel de significaci´on del 5 % de rechazar la hip´otesis de que las rachas de una secuencia podr´ıan ocurrir aleatoriamente.  72 CAP´ ITULO 4. Aplicaciones 4.2. Aplicaciones de los n´umeros de Stirling al c´alculo de momentos 4.2.1. Momentos ordinarios en funci´on de los momentos factoriales Dada una variables aleatoria Xcon funci´on de distribuci´on F(x) unidimensional definida en R, el momento ordinario de orden nes: αn=E[Xn] = ZR xndF(x) (4.11) la cual suponemos que es finita. Por otro lado, el momento factorial de orden r, se define como fr=E[X(X−1) · · · (X−r+ 1)] = E(X)r(4.12) Usando (1.7) podemos calcular los momentos ordinarios en funci´on de los momentos factoriales: αn=E[Xn] = E"n X k=1 S(n, r)(X)r#= n X k=1 S(n, r)fr(4.13) Ejemplo 4.2.3 Los primeros 4 momentos ordinarios en funci´on de los primeros 4 momentos factoriales son: α1=f1 α2=f1+f2 α3=f1+ 3f2+f3 α4=f1+ 7f2+ 6f3+f4 Para obtener los coeficientes de los fitenemos que ver la Tabla 1.4.  4.3. Conexi´on con los momentos centrales 73 4.2.2. Momentos factoriales en funci´on de los momentos ordinarios A continuaci´on obtendremos una relaci´on de los momentos factoriales de orden nen funci´on de los momentos ordinarios. Partimos de la descomposici´on dada en (3.1) x(n)= n X r=1 s(n, k)xk y tenemos que fn=E[(X)n] = n X k=1 s(n, k)E[Xk] = n X k=1 s(n, k)αk donde αkes el momento ordinario de orden kde acuerdo con (4.11) y fnrepresenta el momento factorial (4.12). Ejemplo 4.2.4 Los 4 primeros momentos factoriales en funci´on de los 4 primeros momentos ordinarios son: f1=α1 f2=−α1+α2 f3= 2α1−3α2+α3 f4=−6α1+ 11α2−α3+α4 Para obtener los coeficientes de los fitenemos que ver la Tabla 1.3.  4.3. Conexi´on con los momentos centrales El momento central de orden m, en caso de que exista, se define como µm=E[(X−µ)m] donde µ=E[X].