jueves, 10 de mayo de 2012

Permutaciones y combinaciones

Los siguientes problemas pueden resolverse empleando la regla de multiplicación del producto:
1.-Veinte pilotos participan en una carrera de automovilismo. Los primeros seis lugares acumulan puntos para el campeonato.
¿De cuántas maneras posibles pueden los pilotos ocupar los seis primeros lugares?
 Veamos cómo aplicar la regla del producto. Hay que hacer un total de seis elecciones (una para cada lugar), de modo que k=6. Si la primera elección es para el primer lugar, éste puede ser ocupado por cualquiera de los veinte pilotos  entonces n1 =20. El segundo lugar puede ser ocupado por cualquiera de los diecinueve pilotos restantes, por lo que n2 =19. El tercer lugar puede ser ocupado por cualquiera de los dieciocho pilotos restantes, por lo que n3 = 18. De esta forma , n4 =17, n5 =16 y n6 =15. Por la regla del producto, el total de maneras que los pilotos pueden ocupar los seis primeros lugares es 20 ∙19∙18∙17∙16∙15=27 907 200.

2.Un grupo de 60 alumnos que va a graduarse debe elegir a un comité de graduación formado por un presidente, un vicepresidente, un secretario y un tesorero.
 ¿Cuántas posibles comités se pueden formar?
 El presidente puede ser electo de un total de 60 maneras, el vicepresidente de un total de 59 maneras, el secretario de un total de 58 maneras y el tesorero de un total de 57 maneras. Por la regla del producto, el total de comités posibles es de 60 ∙59∙58∙57 = 11 703 240.

 ¿Qué tienen en común estos dos problemas que su solución resulta muy semejante? En ambos casos estamos eligiendo de un conjunto de objetos algunos de ellos en un orden determinado. En el caso de la carrera de automovilismo estamos eligiendo un piloto para cada uno de los primeros seis lugares de un conjunto de pilotos y en el caso del comité estamos eligiendo un estudiante para cada uno de los cuatro puestos de un conjunto de sesenta estudiantes. En general, a cada elección de r objetos ordenados de un conjunto de n objetos distintos se le llama una permutación de r objetos seleccionados de un conjunto de n objetos. El número de permutaciones de r objetos seleccionados de un conjunto de n objetos se denota por





Es claro que si aplicamos la regla del producto para calcularlo debemos multiplicar los n objetos posibles por los (n-1) objetos restantes, y luego por los (n-2) objetos restantes, etc. En total debemos multiplicar r factores, y como el primer factor es n, el segundo es n-1, el tercero es n-2, etc., entonces el último factor es n-r+1. Por lo tanto
Esta expresión es muy útil para determinar el número de situaciones posibles de muchos problemas donde el orden es relevante. A continuación analizaremos algunos ejemplos.
El entrenador de la selección mexicana de fútbol debe decidir cómo se deben tirar los cinco primeros penales obligatorios en caso de un empate ¿Cuántas elecciones posibles debe considerar?

En este caso se deben escoger cinco jugadores de un total de once que hay en la cancha. Hay entonces

elecciones posibles para determinar  cómo se tirarán los cinco penales obligatorios.


2.- El manager de un equipo de beisbol debe determinar el orden al bat de sus jugadores ¿Cuántos órdenes posibles hay?
Ahora debemos elegir a todos los nueve jugadores que abren el juego y hay por tanto



Órdenes posibles al bat.
Si se tiene un conjunto de n objetos y se elige el total de los n objetos, como en el ejemplo del beisbol, el total de órdenes posibles es n∙(n-1)∙(n-2)∙ ∙∙∙ ∙2∙1. Como con frecuencia debemos emplear estos productos es conveniente usar una notción para ellos. Si n es un número entero y positivo, el producto de todos los enteros menores o iguales es llamado n factorial y lo denotamos por n!. Por ejemplo,

6! = 6∙5∙4∙3∙2∙1 = 720
Y
13! = 13∙12∙11∙10∙9∙8∙7∙6∙5∙4∙3∙2∙1 = 6227020800.
Observemos que el factorial de un número aumenta muy rápido. De hecho 13! Es casi el doble que el número de segundos en un siglo. Para hacer posible que muchas fórmulas que involucran factoriales trabajen correctamente es conveniente tomar  cero factorial como uno, es decir, 0! =1.
En particular,



Esto significa que el número de formas en que se pueden ordenar n objetos es precisamente n! Por ejemplo, arriba analizamos que hay 9!= 362 880 formas de ordenar nueve jugadores de beisbol en su orden al bat.
Las permutaciones de r objetos tomados de un conjunto de n objetos pueden también expresarse por medio de factoriales, ya que
Por lo tanto hemos obtenido el siguiente resultado

Calculemos, por ejemplo



Veamos ahora un problema de naturaleza un poco diferente. Una empresa ofrece tres plazas para profesionales técnicos en computación. Las tres personas que se contraten ocuparan puestos idénticos. Después de una entrevista, el departamento de personal selecciona a cuatro candidatos posibles para el puesto. Si la decisión final de cuáles tres de estos cuatro aspirantes son seleccionados la toma el gerente general ¿cuántas elecciones posibles puede hacer el gerente general? ahora no se trata de un problema de permutaciones, pues aun cuando se deben seleccionar a tres personas de un conjunto de cuatro personas, el orden en que se haga esta selección resulta irrelevante. Digamos que los cuatro finalistas son Alba, Bueno, Cantú y Dávila. Sabemos que hay




A,B,C   A,C,B   B,A,C   B,C,A   C,A,B   C,B,A
A,B,D   A,D,B   B,A,D   B,D,A  D,A,B   D,B,A
A,C,D   A,D,C   C,A,D   C,D,A   D,A,C   D,C,A
B,C,D   B,D,C   C,B,D   C,D,B   D,B,C   D,C,B
En todas las permutaciones del primer renglón aparecen Alba, Bueno y Cantú en diferente orden y como los tres puestos son iguales, estas seis permutaciones corresponden a contratar a Alba, Bueno y Cantú. De la misma forma, las permutaciones del segundo renglón corresponden a contratar a Alba, Bueno y Dávila; las permutaciones  del tercer renglón corresponden a  contratar a Alba, Cantú, Dávila; y finalmente, las permutaciones del último renglón corresponden a contratar a Bueno, Cantú y Dávila. El gerente tiene por lo tanto cuatro selecciones posibles: A, B, C; A, B, D; A, C, D; o B, C, D, que son las elecciones de la primera columna. Cada renglón contiene 6 diferentes permutaciones de las iniciales de la primera columna.
En general, a cada una de las selecciones de r objetos (sin importar el orden) tomadas de un conjunto de n objetos distintos le llamamos una combinación de n o objetos tomados de r en r. El número de combinaciones de n objetos tomados de r en r se denota por

Podemos obtener una fórmula para este número de la misma manera que lo hicimos para las selecciones del gerente. Sabemos que hay
selecciones donde si importa el orden. Podemos agrupar estas permutaciones en

grupos de los mismos objetos, pero con diferente orden. Para cada uno de estos grupos hay   

  Permutaciones diferentes. Tenemos por tanto
Grupos diferentes. Así,
El número en que r objetos pueden seleccionarse sin importar el orden de un conjunto de n objetos es
Veamos algunos ejemplos de combinaciones.



1. Con parte de su primer salario un chavo decide comprar 3 de los siete discos compactos que le faltan del grupo el tri. ¿Cuántas posibilidades tiene?

Hay que elegir 3 objetos (sin importar el orden) de un conjunto de siete. Hay entonces
Combinaciones de tres discos compactos.
2.-En un examen de Historia se requiere contestar cuatro de doce preguntas. ¿Cuántas maneras diferentes hay de contestar este examen?


Se requiere ahora escoger cuatro objetos de un conjunto de doce. Observemos que se nuevo el orden en que se escogen las ocho preguntas resulta irrelevante, puesto que, por ejemplo , da lo mismo seleccionar las preguntas 4,5,8 y 11 que las preguntas 11,4,5 y 8. El estudiante puede responder este examen de

Maneras distintas.
Debido a que los factoriales crecen muy rápido, la fórmula que tenemos para calcular

tiene el inconveniente de que es ocasiones es difícil de emplear. Por ejemplo algunas calculadoras no son capaces de manejar números de 9 dígitos como 479 001 600 , que aparece arriba como numerador.


Existen otras maneras de calcular .
 Sabemos que

12! = (12∙11∙10∙9)∙8∙7∙6∙5∙4∙3∙2∙1

        = (12∙11∙10∙9)∙8!

Y por lo tanto,

En general,



 Por lo que se tiene la siguiente fórmula


 3.- El sorteo Melate consiste en adivinar seis de cuarenta y cuatro números posibles. ¿De cúantas maneras se pueden elegir estos 6 números entre el 1 y el 44? De nuevo, no es relevante el orden en que se eligen los seis números, por lo que se tienen

formas en que el sorteo se puede llevar a cabo. Como 44! es demasiado grande es conveniente calcular este número utilizanso la fórmula de arriba. Las maneras en que se puede llevar a cabo el sorteo de Melate son entonces




Puesto que al seleccionar r objetos de un conjunto de n objetos, partimos al conjunto en dos partes, uno con los r objetos seleccionados y otro con los n-r objetos no seleccionados. Esto significa que hay el mismo número de maneras de seleccionar r objetos de un conjunto de n objetos, que de seleccionar n-r objetos del mismo conjunto de n objetos. Por lo tanto


Supongamos que la selección nacional de futbol que va a representar a México en un mundial es de 22 jugadores. Si el entrenador nacional tiene concentrados a 27 jugadores antes del mundial, ¿cuántos equipos posibles puede escoger el entrenador?


El técnico debe escoger 22 de los 27 jugadores originalmente convocados. Hay entonces






Equipos posibles. Podemos obtener este número de varias maneras. De acuerdo con nuestra forma original
Que resulta difícil de calcular por los tamaños de 27! Y 22! Si empleamos ahora la fórmula
Se tiene

Que también es muy complicada. Finalmente, como

La identidad

Resulta muy útil cuando r es mayor que n/2. Por ejemplo,

A los números
Se les acostumbra llamar coeficientes binomiales pues aparecen como coeficientes en el desarrollo de la fórmula del binomio de Newton:


Observemos que la suma de los exponentes de x y y es siempre n, y que mientras disminuyen los exponentes de x aumentan los de y . Por ejemplo,
Como los valores de



 Se usan con mucha frecuencia es conveniente tenerlos a la mano fácilmente


Para n menor o igual a 20 aparecen en la siguiente tabla.
En el renglón que corresponde a n =6 aparecen los números 1,6, 15, 20, 15,6 y 1. Estos son los coeficientes de (x +y) 6 , esto es, (x +y) 6 =x6 + 6x5y +15x4y2 + 20x3y3 + 15x2y4 + 6xy5 + y6.


Cuando emplearemos la anterior tabla a veces es necesario usar la identidad


 

Digamos que necesitamos el coeficiente


Este coeficiente no aparece en la tabla, pero como
Existe un método sencillo de construir una tabla de coeficientes binomiales. El siguiente arreglo de números es conocido como el triángulo de Pascal.                                  
En este arregla cada fila empieza y termina en 1, y cada elemento es la suma de los dos elementos más cercanos arriba de él. Por ejemplo, arriba del 6 están el 1 y el 5, arriba del 15 el 5 y el 10, etc.


En ocasiones es necesario emplear varias fórmulas para resolver problemas de conteo complicados. A continuación analizamos algunos ejemplos.

1. Una cadena hotelera desea contratar a cuatro técnicos en hotelería y a tres técnicos en gastronomía para su nuevo hotel en Puerto Vallarta. Si la empresa recibió 9 solicitudes para los puestos de técnico en hotelería y 8 solicitudes para los puestos de técnico en gastronomía, ¿de cuántas maneras  pueden hacer la contratación? La empresa puede elegir de

Maneras posibles. Los valores 126 y 56 de los coeficientes binomiales también los podríamos haber obtenido directamente de la Tabla mostrada más arriba.
2.- ¿De cuántas maneras es posible formar los grupos del torneo de liga de futbol de primera división? Recordemos que en la primera división de futbol en México participan 18 equipos, y para el torneo de liga se forman dos grupos de cinco equipos y dos grupos de cuatro equipos.


Analicemos primero de cuántas maneras se puede formar el primer grupo. En este caso hay que elegir cinco equipos (sin importar el orden) de un conjunto de 18 equipos. Hay entonces

Una vez que se constituyo el primer grupo, ¿de cuántas maneras se puede formar el segundo grupo? De nuevo hay que elegir cinco equipos, pero ahora de un total de 13 equipos restantes. Una  vez que el primer grupo se integro, hay

 Una  vez que se han integrado los dos primeros grupos ¿de cuantas maneras se puede formar el tercer grupo? Ahora debemos elegir 4 equipos de un total de 8 equipos que no han sido considerados. Así, una vez que ya se han integrado los dos primeros grupos, hay

Finalmente, una vez que se han elegido los primeros tres grupos, es claro que entonces el cuarto grupo queda forzado, esto es, sólo hay una manera de formar el cuarto grupo si los tres primeros ya se constituyeron.

 Si aplicamos ahora la regla del producto vemos que hay
maneras posibles de formar  los grupos de la primera división de futbol. Utilizando la tabla  de coeficientes binomiales mostrada arriba es fácil ver que este número es precisamente el producto (8568)(1287)(70) = 771 891 120.