|
Definiciones:
email: marodgar@telefonica.net |
En este tema vamos a desarrollar los conceptos reseñados en la Introducción En síntesis: Lo que se ha pretendido en la introducción es conseguir ordenar y contar las distintas agrupaciones que puedan hacerse con los elementos de un conjunto, abstracción hecha de su naturaleza. Desde un punto de vista general, los diccionarios y la enciclopedia nos han ayudado poco para saber de qué trataba la combinatoria o análisis combinatorio. En ese proceso buscador y con la ayuda del libro de matemáticas nos hemos encontrado con la clasificación:
NOTA: Obsérvese que el proceso para el estudio de las distintos conceptos es el mismo consistente en distinguir en cada uno: Concepto, Símbolos, Ordenación, Recuento, Fórmulas, Ejemplos y aplicaciones. Sistematizar es una operación sumamente rentable en el estudio Como puede apreciarse los distintos tipos de ordenaciones que podemos aplicar a un conjunto son las mismas tanto en la combinatoria ordinaria como con repetición; la diferencia esencial de un tipo u otro consiste en que en la primera, los elementos que forman la ordenación son distintos entre ellos y en la segunda los elementos pueden repetirse. La estrategia a seguir consistirá en ir desgranando cada tipo de ordenación considerando uno u otro caso; esto es: que sus elementos sean distintos o se repitan. En un caso tendremos la Combinatoria ordinaria y en el otro caso la Combinatoria con repetición. Los tres tipos de ordenaciones que vamos a estudiar son: * Permutaciones de forma general y como caso particular de las variaciones.
De todas ellas intentaremos conocer: - Concepto - Ordenación - Recuento - Fórmulas usuales - Campo de aplicación - Ejemplos y aplicaciones
Seguimos con el esquema adoptado en el estudio de la matemática elemental. Para penetrar en el concepto “Permutaciones” y seguir después en su desarrollo conceptual, propiedades y aplicaciones, nos introduciremos en el tema a partir de lo que dicen los diccionarios: DRAE, CIRLEC, DIMAT y un libro de matemáticas. (Recordemos: DRAE es el diccionario de la Real Academia; CIRLEC es una enciclopedia y DIMAT un diccionario de Matemáticas). Analizaremos sus contenidos, lo semejante, lo distinto, lo olvidado y sus imprecisiones. Adquirido el concepto de variación lo que viene después es consecuencia de ello y por tanto generable por cualquier lector perspicaz.
No aparece tal concepto en el DRAE. Sí aparece: Permutación: f. Acción y efecto de permutar. Permutar: 3. Variar la disposición u orden en que estaban dos o más cosas. Las acepciones 1 y 2 del Diccionario no guardan relación con el sentido matemático del término. La primera se refiere a la permuta de cosas y la segunda, de cargos equivalentes entre funcionarios, por ello solo he trascrito la acepción 3,.
Probemos con la enciclopedia CIRLEC: Permutacion: MAT. Intercambio de los elementos de una serie.| Dado un conjunto de m elementos, se llama _ a cada uno de los distintos grupos de m elementos que pueden formarse ordenando éstos de todas las maneras posibles. Si los m elementos son distintos entre sí, el número de sus _, Pm, es igual al producto de los m primeros números naturales: Pm = 1.2.3....(m-1)m = m! (léase m factorial o factorial de m). Ej.: las _ de 3 elementos distintos son P3 = 3! = 3.2.1 = 6 ( si los elementos son letras a, b, c, se tendrá: abc, acb, bac, bca, cab, cba). Si entre los m elementos, uno está r veces repetido, otro s veces ..... y otro t veces, el número de _ llamadas _ con repetición es igual a n!/r! + s! +....+t! siendo r + s + .....+ t = m Sin entrar en el fondo de la definición, que se hará más adelante parece conveniente hacer unas precisiones: a) No simboliza las permutaciones con repetición. Sí lo hace con las permutaciones sin repetición u ordinarias ¿Por qué no simboliza las permutaciones con repetición? Pregunta que cada cual puede responderse a su satisfacción. b) Al expresar la fórmula por la que calcula el nº de permutaciones Pm, lo hace como producto de números naturales crecientes. Sin embargo, al aplicar la fórmula para el cálculo, lo hace en orden decreciente. Es cierto que el producto de números naturales es conmutativo y que, el factorial de un número, puede expresarse y calcularse en orden creciente o decreciente, pero sería más pedagógico mantener el esquema contenido en la definición. c) En el ejemplo, da a entender que el cálculo del número de permutaciones solo se puede hacer con números y no con las letras que hay que ordenarlas para contarlas. Se ve que el número de permutaciones de las letras es 6 = 3! por ser 3 el número de letras que se permutan. Lo mismo manera que se permutan las tres letras a, b, c, se pueden permutar los números 1, 2 , 3. d) Dice: "Intercambio de los elementos de una serie" ¿Si no forman parte de una serie no se pueden permutar?. Es curioso que en la definición arranca de un conjunto y no de una serie. ¿Qué dice sobre el asunto el diccionario especializado DICMAT? Permutación: Cambio del orden de los elementos de una sucesión entre sí. Tal definición no parece muy modélica tratándose de un diccionario de matemáticas.
¿Qué dice un libro de matemáticas al respecto? Permutaciones: Definición y número: Permutaciones n-arias son las variaciones de orden n formadas con n objetos; luego designando su número por Pn se tiene: Pn = Vn,n = n(n - 1)(n - 2).....3.2.1 = n!
Reunamos todo lo dicho en la siguiente matriz:
¿Qué conceptos se barajan en lo que dice el DRAE? : Las permutaciones guardan relación con la disposición u orden en que están dos o más cosas.
¿Qué conceptos se barajan en lo que dice CIRLEC?: - Intercambio entre los elementos de una serie - Disponer de un conjunto de n elementos. (Nada se dice acerca de su naturaleza) - Formar grupos distintos con esos n elementos de todas las maneras posibles. - Distingue entre permutaciones y permutaciones con repetición - Da fórmulas de cálculo y expone unos ejemplos
NOTA: Como queda dicho más arriba, no usa en la definición el concepto de serie y sí el de conjunto. Hubiera quedado, a nuestro parecer, más coherente decir: "Intercambio entre los elementos de un conjunto"
¿Qué conceptos se barajan en lo que dice el DIMAT? : Las permutaciones guardan relación con el cambio del orden de los elementos de una sucesión entre sí.
¿Qué conceptos se barajan en lo que dice el libro de matemáticas? Las permutaciones las considera como variaciones cuando entran en cada ordenación todos los elementos del conjunto ordenado. De acuerdo con eso, mutatis mutandis, se puede decir: - Llama permutación de orden n a todo conjunto ordenado formado por los n elementos del conjunto. - Se conviene en considerar distintas las permutaciones si difieren en el orden de colocación.
Como síntesis de todo los expresado podemos definir Así: Se denominan Permutaciones de un conjunto de n elementos al conjunto de todas las ordenaciones que podemos formar con todos los elementos dados de modo que, entrando todos los elementos del conjunto en cada ordenación, se diferencie una de otra en el orden de colocación de sus elementos. También se pueden definir como las variaciones de orden n de un conjunto de n elementos. (Enlace) Se pueden clasificar en: Permutaciones ordinarias si los elementos de toda ordenación son distintos Permutaciones con repetición si alguno de los elementos de toda ordenación pueden repetirse o no.
¿Cómo se simbolizan las permutaciones? El símbolo Pn expresa las permutaciones ordinarias de un conjunto con n elementos. El símbolo PRna,b,c,...r,s,t expresa las permutaciones con repetición de un conjunto de n elementos, de los cuales uno de ellos se repite a veces, otro, b veces....... con la condición de que a + b + c + .......+ r + s + t = n OBSERVACIÖN: Cuando escribimos: Pn ó PRna,b,c,...r,s,t expresamos indistintamente las Permutaciones como su número.
¿Cómo se ordenan y cómo se cuentan las permutaciones ordinarias? Al ser las permutaciones un caso particular de las variaciones, los criterios señalados para ordenar éstas sirven para las permutaciones. Se trata, por tanto, de aplicar a las permutaciones de orden n, los procesos seguidos para ordenar las variaciones de n elementos tomados de n en en n. Combinatoria variaciones Como alternativa vamos a seguir para el recuento y ordenación un proceso intuitivo que nos servirá para nuestro propósito. Supongamos que tenemos n casillas o recipientes y n bolas de colores distintos. Existe por tanto una correspondencia entre el número de bolas y el de casillas. Tomemos una cualquiera de las n bolas. Todas las n casillas están desocupadas ¿Cuantas casillas tengo disponibles para colocar la bola elegida? n. Luego tengo n sitios para colocar la bola. Elijo una cualquiera ¿Cuantas bolas me quedan por colocar? (n -1). ¿Cuantas casillas me quedan disponibles? (n -1) Tomemos una cualquiera de las (n - 1) bolas sin colocar. Nos quedan (n -1) casillas vacías. Elijo una cualquiera y la coloco ¿De cuantas maneras posibles puedo colocar esa bola? De (n -1) formas. ¿De cuantas maneras posibles puedo colocar las dos bolas elegidas? el número que resulte del producto n(n -1). Hemos colocado dos bolas en dos casillas ¿Cuantas bolas me quedan por colocar y cuantas casillas disponibles? (n -2). Tomemos una cualquiera de las (n - 2) bolas sin colocar. Nos quedan (n -2) casillas vacías. Elijo una cualquiera y la coloco ¿De cuantas maneras posibles puedo colocaresa bola? De (n - 2) formas. ¿De cuantas maneras posibles puedo colocar las tres bolas elegidas? El producto de n(n -1)(n - 2). Siguiendo el mismo procedimiento llegaremos al final donde solo nos queda una casilla y una bola por colocar ¿De cuantas maneras posibles puedo colocar la última bola que me queda por colocar en el sitio que queda vacío 1. Luego: ¿De cuantas maneras posibles puedo colocar las n bolas del conjunto? El producto de n(n -1)(n - 2).......3.2.1 = n! Recordamos que el producto de n números naturales consecutivos desde el 1 hasta n o de n hasta 1 recibe el nombre de factorial de n y se simboliza así: Factorial de n = n!
Un ejemplo concreto, dentro de lo abstracto del tema. Ejemplo 1º: Se trata de distribuir de todas las formas posibles en cuatro casillas, cuatro bolas distintas Que simbolizaremos así:
Seguiré el proceso diseñado: Tomemos una cualquiera de las 4 bolas. Las 4 casillas están desocupadas ¿Cuantas casillas tengo disponibles para colocar la bola elegida? 4. Luego tengo 4 sitios para colocar la bola. Elijo una cualquiera por ejemplo la roja y la coloco en un sitio cualquiera quedando así:
¿Cuantas bolas me quedan por colocar? 3. ¿Cuantas casillas me quedan disponibles? 3 Tomemos una cualquiera de las 3 bolas sin colocar. Por ejemplo la verde. Nos quedan 3 sitios para poder colocarlas ¿De cuantas maneras posibles puedo colocar la bola verde? En 3 sitios. Elijo una de las situaciones posibles quedando las bolas así:
¿De cuantas maneras posibles puedo colocar las dos bolas elegidas? Si la roja podía colocarse en 4 sitios y la verde en 3 las dos bolas podrán colocarse de 4 x 3 formas distintas.
¿Cuantas bolas me quedan por colocar? 2. ¿Cuantas casillas me quedan disponibles? 2 Tomemos una cualquiera de las 2 bolas sin colocar. Por ejemplo la azul. Nos quedan 2 sitios para poder colocarla ¿De cuantas maneras posibles puedo colocar la bola azul? de 2 formas que son los huecos que quedan libres. Elijo una de las situaciones posibles quedando las bolas así:
¿De cuantas maneras posibles puedo colocar las tres bolas elegidas? Si la roja podía colocarse en 4 sitios, la verde en 3 y la azul en 2, las tres bolas podrán colocarse de 4 x 3 x 2 formas distintas. Tomemos la bola marrón sin colocar. Nos queda 1 sitio para poder colocarla ¿De cuantas maneras posibles puedo colocar la bola que me queda? 1, el único hueco libre que ya no puedo elegir, pues estoy obligado. La situación así:
¿De cuantas maneras posibles puedo colocar las cuatro bolas elegidas? Si la roja podía colocarse en 4 sitios, la verde en 3, la azul en 2 y la marrón en 1, las cuatro bolas podrán colocarse de 4 x 3 x 2 x 1 formas distintas. Por tanto: El nº total de posiciones posibles sería: P4 = 4! = 1.2.3.4 = 24 Procedamos a escribirlas. Para mayor comodidad los colores los he sustituido por los números 1, 2, 3, 4 Para ordenarla partimos de la permutación principal 1234.
Permutación principal: Definición . Se llama permutación principal aquella cuyos elementos están dispuestos en el orden natural. En nuestro caso 1234. A continuación se escriben en una fila todas las permutaciones cuyo primer elemento sea el uno. En la segunda fila es escriben todas las permutaciones cuyo primer elementos sea el 2. Y así sucesivamente. En nuestro caso se conformaría una matriz de 4 filas y 6 columnas El número total de permutaciones sería igual al número de filas por el número de columnas. En este caso:
Número de permutaciones = Número de filas x Número de columnas = 24 x 1 = 24 Tal como se había calculado. Permanencia: Se dice que dos elementos de una permutación están en permanencia si están dispuestos en su orden natural así 12; ab. En la permutación 1243. El 2, 3 y 4, están en permanencia don el 1; el 3 y 4, están en permanencia con el 2 Inversión: Se dice que dos elementos de una permutación están en inversión si no están dispuestos en su orden natural así 21; ba. En la permutación 1243. El 4 y el 3 están en inversión. ¿Cómo se cuenta el número de inversiones de una permutación?: Se compara con cada uno de los elementos de la permutación con los que tiene a la izquierda y se cuentan el número de inversiones. Así: Sea la permutación 2413. El 4 con el 2 están en permanencia. El 1 con el 2 en inversión; el 1 con el 4 en inversión; el 3 con el 2 en permanencia; el 3 con el 4 en inversión; el 3 con el 1 en permanencia. El número de inversiones es 3. (12); (14); (34). Las permanencias no se tienen en cuenta. Permutación par: Se dice que una permutación es de orden par si tiene un número par de inversiones. La permutación principal es de orden par. La permutación 2431 es una permutación de orden par. En efecto: El 4 con el 2 está en permanencia el 3 con el 2 está en permanencia el 3 con el 4 está en inversión; El 1 con el 2 está en inversión; El 1 con el 4 está en inversión; El 1 con el 3 está en inversión. Como el número de inversiones es 4, la permutación 2431 es de orden par. Las permanencias no se tienen en cuenta. Permutación impar: Se dice que una permutación es de orden impar si tiene un número impar de inversiones. La permutación 2413 es impar por tener tres inversiones.
NOTA: En el conjunto de todas las permutaciones de orden n, la mitad son de orden impar y la otra mitad de orden par.
Se desarrolla en página aparte (Enlace)
Permutaciones con repetición: Recordemos las definiciones y simbolización de las permutaciones con repetición: Permutaciones con repetición si alguno de los elementos de toda ordenación pueden repetirse o no. ¿Cómo se simbolizan las permutaciones con repetición? El símbolo PRna,b,c,...r,s,t expresa las permutaciones con repetición de un conjunto con n elementos, de los cuales uno de ellos se repite a veces, otro, b veces....... con la condición de que a + b + c + .......+ r + s + t = n Definidas y simbolizadas las permutaciones con repetición procede establecer los procedimientos de recuento y cálculo.
¿Cómo se ordenan y cómo se cuentan las permutaciones con repetición? Los criterios señalados en el recuento y cálculo del número de las permutaciones ordinarias. mutatis mutandis es de aplicación a las permutaciones con repetición. Supongamos que tenemos un conjunto de n elementos, de los cuales uno de ellos se repite a veces, otro, b veces....... con la condición de que a + b + c + .......+ r + s + t = n El nº total de permutaciones ordinarias de orden n, como sabemos, será : Pn = n! En esas n! permutaciones, habrá a! permutaciones iguales correspondientes a los a elementos que se repiten. b! permutaciones iguales correspondientes a los b elementos que se repiten y así con todos los demás elementos que se repiten. Por tal motivo, Pn =a!b!c!....r!s!t! PRna,b,c,...r,s,t Pn de donde. PRna,b,c,...r,s,t = ----------------- = a!b!c!....r!s!t! Un ejemplo concreto, dentro de lo abstracto del tema.
Ejemplo 1º: ¿Cuántos números distintos podré formar con los dígitos 1, 2, 3, de modo que el 1 se repita dos veces, el 2 tres veces y el 3 cuatro veces. El nº 112223333, será uno de los posibles. El número total de dígitos de cada número será n = 9. El 1 se repite dos veces, luego a = 2 El 2 se repite tres veces, luego b = 3 El 3 se repite cuatro veces, luego c = 4 Obsérvese que 2 + 3 + 4 = 9 Aplicando la fórmula y sustituyendo valores se tendrá: n! 9! PRna,b,c,...r,s,t = ----------------- = PR92,3,4 = ---------= a!b!c!....r!s!t! 2!3!4!
362880 = ----------- = 1260 2 x 3 x 4 Con las calculadoras electrónicas el cálculo es inmediato, Sin embargo, parece aconsejable ejercitarse en la simplificación de fracciones con factoriales, para lo cual el factorial del mayor número de un término se expresa como factorial del mayor número del otro término y luego se simplifica; así: 4! x 5 x 6 x 7 x 8 x 9 -------------------------- = 5 x 7 x 4 x 9 = 1260 2! 3! 4!
1º Calcular y escribir las permutaciones ordinarias que se pueden formarse con las vocales a, e, i, o y comprobar que la mitad es de orden par y la otra mitad de orden impar Calculo: Aplicando la fórmula Pn = n! Como n = 4 P4 = 4! = 1x2x3x4 = 24 Escribirlas: aeio aeoi aieo aioe aoei aoie eaio eaoi eiao eioa eoai eoia oaei oaie oeai oeia oiae oiea iaeo iaoe ieao ieoa ioae ioea
Comprobar la paridad e imparidad
Total permutaciones: 24 = 4! Nº de permutaciones pares = 12 Nº de permutaciones impares = 12
2º Tenemos dos consonantes y tres vocales distintas. Se pide determinar cuantas palabras de cinco letras se pueden formar con la condición de que no entren dos consonantes seguidas ni tres vocales seguidas. Solución: Llamemos a: las consonantes C1 y C2; a las vocales V1 , V2 y V3 Los tipos de palabras que se pueden formar son las siguientes: Que empiece por consonante: C1 V1 C2 V2 V3 C1 V1 V2 C2 V3 Que empiece por vocal V1 C1 V2 C2 V3 V1 V2 C1 V3 C2 V1 C1 V2 V3 C2 En cada uno de las cinco agrupaciones anteriores, supongamos que dejamos fijas las consonantes y permutamos las vocales. Como el número de vocales son tres, se podrán formar las permutaciones P3 = 3! Si dejamos las vocales fijas y permutamos las consonantes. Como el número de consonantes son dos, se podrán formar las permutaciones P2 = 2! El número total de palabras en cada grupo será igual al producto: P3 P2 = 3! 2! = 6 x 2 = 12 Como son cinco grupos distintos que siguen la misma ley de formación el total de palabras que pueden formarse con las dos consonantes y las tres vocales distintas, será igual a: 5 x 12 = 60
3º Con los dígitos 3, 5, 7, 8, 0 se forman todos los números posibles, determinar cuantos de ellos son mayores de 6500 y cuantos menores. Solución: El nº de elementos del conjunto es 5. El total de números que se pueden formar con estos dígitos serán las permutaciones ordinarias con esos cinco dígitos que son: P5 = 5! = 120 De estos 120 números ¿Cuantos habrá que empiezan con 0? Del conjunto anterior apartamos el cero con lo cual me quedan 3, 5, 7, 8 con estos cuatro dígitos se pueden formar las permutaciones de ellos que son P4 = 4! = 24 24, son los números que empiezan con cero que no es significativa. De esos 24 números los que empiezan por 7 y 8 son mayores de 6500 y los que empiezan con 3 y 5 son menores de 6500. Por tanto son: Menores de 6500 = 12 Mayores de 6500 = 120 - 12 = 108
4º Con los dígitos 0, 0, 0, 2, 3 se forman todos los números posibles con cinco cifras significativas ¿Cuantos son? Solución: Para que los números tengan cinco cifras significativas, el primer dígito ha de ser 2 ó 3. Apartemos el 2, por ejemplo. Como quedan cuatro dígitos de los cuales el 0 se repite tres veces el total de números de cuatro dígitos será 4! 4 x 3! PR43,1 = ------ = ------- = 4 3! 1! 3! 1! Son por tanto 4 los números de 5 dígitos con cinco cifras significativas que empiezan por el 2 De modo semejante serán 4 los números de 5 dígitos con cinco cifras significativas que empiezan por el 3 Por tanto La solución será: 8 son los números de 5 dígitos con cinco cifras significativas que se pueden formar con los dígitos dados.
5º Con los dígitos 1, 1, 1, 1, 1, 2, 3, 3, 3, 4, 4 determinar el número de permutaciones que se pueden formar con esos dígitos. Solución: El número de elementos que han de permutarse son 11 por tanto n = 11, de los cuales hay 5 unos luego a = 5; un dos luego b = 1; Tres 3 luego c = 3 y dos 4, luego d = 2, por tanto se trata de permutaciones con repetición de 11 elementos de los cuales uno se repite 5 veces, otro, una vez; otro tres veces y otro 2 veces. Apliquemos la fórmula y sustituyendo valores, tendremos: n! 11! PRna,b,c,d = --------- = PR115,1,3,2 = ---------= a!b!c!d! 5!1!3!2! con la condición de que a + b + c + d = n En efecto 5 + 1 + 3 + 2 = 11 Resolviendo: 11! 11 x 10 x 9 x 8 x 7 x 6 x 5! PR115,1,3,2 = ---------=-------------------------------- 5!1!3!2! 5!1!3!2! Simplificando resultaría: PR115,1,3,2 = 11 x 10 x 9 x 4 x 7 = 27.720
email: marodgar@telefonica.net
|