PROGRAMA SÉNIOR
UNIVERSIDAD DE CANTABRIA
Es lógico
Beatriz Porras
3- Algunas maneras de contar
 Combinatoria: Adrián Paenza
http://youtu.be/rQ84z40YYVk
 Supongamos que tenemos un conjunto de 10 elementos distintos.
Para concretar ideas, podemos pensar en el caso de una baraja de
40 cartas, de las que se reparten 10 a cada jugador.
El problema que nos planteamos es de cuántas formas distintas
podemos ordenar esas 10 cartas.
 El problema es bastante habitual:
 Si tenemos un grupo de 20 niños, ¿de cuantas maneras distintas
podemos colocarlos a todos en una fila?, por ejemplo, con el objetivo
de que todos estén en algún momento en cada una de las posiciones
posibles.
 De cuántas formas distintas podríamos ordenar los 8 cuadros de una
exposición, a lo lago de un pasillo?
 En todos los casos, hablamos de las formas posibles de
ordenar un conjunto de n elementos distintos.
 La respuesta es bastante "lógica". Si lo hacemos con un
conjunto pequeño, por ejemplo de 3 elementos, lo
podemos resolver a mano:
 Tenemos tres elementos A, B y C. Para ordenarlos,
podemos colocar en el primer lugar a cualquiera de los tres
Primero
A
B
C
Segundo
Tercero
 Una vez colocado el primer elemento, nos quedan dos
para escoger el que irá en segundo lugar
Primero
Segundo
A
B
A
C
B
A
B
C
C
A
C
B
Tercero
 Y una vez escogidos los dos primeros elementos, solo
queda uno que necesariamente irá el ultimo
Primero
Segundo
Tercero
A
B
C
A
C
B
B
A
C
B
C
A
C
A
B
C
B
A
 Otra forma, mas gráfica, plantear este tipo de problemas son los
diagramas de árbol:
 construimos un árbol haciendo una ramificación cada vez que tenemos
que escoger entre varias opciones para resolver el problema. El numero
total de ramas nos indica el numero de soluciones posibles.
 Para la primera posición puedo elegir cualquiera de los n elementos
que tengo.
 Por cada una de las n elecciones de primer elemento, puedo escoger
uno entre los (n -1) que me quedan para la segunda posición. En total
tengo n(n - 1) formas posibles de escoger los dos primeros elementos,
y me quedan (n - 2) posibilidades para la tercera posición.
 Así que tengo n(n -1)(n-2) formas posibles de escoger los tres primeros
elementos.
 Sigo con este procedimiento hasta que solo me quede un elemento
suelto, que necesariamente quedara en la última posición.
En total tengo
n! = n(n-1)(n-2)(n-3)...3 x 2 x 1
formas posibles de ordenar un conjunto de n elementos distintos.
 Un detalle importante: el numero n! nos indica cuantas
soluciones hay, no cuales son.
 Todas las soluciones forman lo que llamamos
"permutaciones de n", cada forma de ordenar los n
elementos es una permutación, y el numero total de
permutaciones posibles es n!.
P n  n!
 Un caso especial: permutaciones circulares
¿De cuantas formas distintas podemos sentar a 8 personas
alrededor de una mesa redonda?
A
H
B
G
C
F
D
E
E
D
A
H
C
B
G
G
B
C
F
F
H
A
D
F
E
B
D
G
C
H
A
E
 En general, al contar el número de ordenaciones
circulares de n elementos tenemos que mantener uno
fijo, y ordenar el resto a partir de él, con lo que el número
total de es “Permutaciones circulares de n elementos”
PCn= (n-1)!
Consideremos ahora este ejemplo:
 ¿Cuántos números de tres cifras distintas podemos formar con los dígitos
del 1 al 9?
Pongamos otro ejemplo con personas:
 Tengo una clase con 9 alumnos, y cada da tenemos que hacer tres trabajos
distintos para empezar la clase: subir las persianas, limpiar la pizarra, y
encender el ordenador. Quiero escoger cada da a tres alumnos para que
vayan haciendo este trabajo antes de que yo llegue a clase. Y preferiría que
todos participasen en todos los trabajos.
 ¿De cuantas formas puedo escoger tres niños para que hagan esos tres
trabajos?
 ¿En un curso habremos rotado entre todas las opciones distintas posibles?.
 El problema es claramente diferente del anterior en el
sentido de que no tengo que escoger y ordenar a todos
los alumnos, sino que tengo que seleccionar a tres de
ellos. Y es importante en que orden los seleccione, ya que
el trabajo que van a tener que hacer es distinto: por
ejemplo, el primero que nombre siempre será el que suba
las persianas, el segundo limpiara la pizarra, y el tercero
preparara el ordenador.
Respuesta:
 En primer lugar, podre escoger uno de los nueve alumnos,
cualquiera. Tengo nueve posibilidades.
 En segundo lugar, podre escoger a uno de los ocho que
quedan. Por cada una de las nueve posibilidades tengo ocho
para escoger al segundo alumno.
 Y por cada pareja que haya escogido para los dos primeros
trabajos, quedaran otros siete alumnos entre los que escogeré
al tercero. Siete posibilidades por cada una de las posibles
elecciones anteriores.
9x8x7=504 posibilidades
 Este tipo de operación: seleccionar k elementos de un
grupo de n elementos distintos, en el que los resultados
se diferencian tanto por que elementos escogemos como
por en que orden lo hacemos, se denomina “Variaciones
de n elementos tomados de k en k”
 El numero de variaciones posibles es
Vn,k = n(n -1)(n -2) x...x(n - k + 1)
 Que se puede escribir también
Vn ,k 
n!
(n  k)!
Un tercer tipo de problema
 Para una liga de futbol con ocho equipos, si todos juegan
con todos una vez, ¿cuantos partidos distintos se jugaran?
¿Es decir, cuántos emparejamientos distintos se pueden
hacer?
 En un tele-pizza tienen una oferta de 10 ingredientes, de
los cuales puedes escoger los tres que prefieras para
hacer una combinación. ¿Cuantas pizzas distintas puede
hacer?
 Ahora tenemos un modelo de problema claramente
distinto de los dos anteriores por dos motivos:
 Tenemos que hacer una selección, en la que no aparecen
todos los elementos disponibles en el conjunto,
 y además el grupo que formamos es el mismo aunque
escojamos sus elementos en un orden distinto.
 En el ejemplo de las pizzas:
 Primer paso: Para hacer una combinación podemos escoger en primer
lugar uno cualquiera de los 10 ingredientes. Una vez escogido el
primero, podemos escoger otro de los 9 que nos quedan, y finalmente
escoger uno de los 8 restantes. 10x9x8 soluciones
 Segundo paso: Si hacemos una lista con todas esas soluciones, hay
muchos resultados iguales, con los mismos ingredientes, sólo que
escogidos en ordenes distintos. Todas las formas de ordenar esos tres
ingredientes, 3! Iguales por cada elección de tres ingredientes
 Total: Agrupamos como una única solución las que son iguales, y
quedan
10  9  8
3!
Soluciones distintas

10!
3! 7!
 En este tipo de problema hemos tenido que seleccionar k
elementos en un grupo de n, sin importar el orden en
que se escogen. Los resultados se diferencian por los
elementos que contienen, pero no por el orden en que
aparecen. El número de soluciones se denomina
“Combinaciones de n elementos tomados de k en k” y se
calcula mediante la fórmula
C n ,k
La expresión
n
 
k 
n
n!
 
 k  k !(n  k)!
se lee “n sobre k”, y se llama número combinatorio
Un ejemplo: La selección nacional de futbol.
 En estos tiempos de crisis la necesidad de distraernos y disfrutar de
un tiempo de ocio se hace mas acuciante, y algunos deportes
masivos como el futbol vuelven a convertirse en vías de escape. A
cada todo el mundo le gustaría diseñar el equipo titular de la
selección española, pero eso es imposible, ¿o no?
 Simplificamos un poco la situación:
 el seleccionador tiene que formar un equipo con un portero, cuatro
defensas, cuatro medios y dos delanteros.
 Y pongamos que puede elegir entre los jugadores titulares de los cuatro
mejores equipos de la liga, que tienen esta misma estructura.
 Así que tenemos cuatro equipos, A, B, C y D. En cada uno hay una distribución similar de
jugadores, por lo que tenemos
 4 porteros
 16 defensas
 16 mediocampistas
 8 delanteros
 Para formar un equipo podemos escoger uno cualquiera de los cuatro porteros.
 Después podemos escoger cuatro defensas de entre los 16 que tenemos. Suponemos que
pueden jugar en cualquier posición (derecha, izquierda, centro,…)
Hay
 16 


 4 
formas distintas de seleccionar a cuatro defensas.
 A continuación tenemos que escoger cuatro medio campistas entre los 16 que tenemos, por
lo que tenemos el mismo numero de posibilidades.
 Y finalmente tenemos que escoger 2 delanteros, entre los 8 disponibles. Hay
formas distintas de hacer esto.
8
 
2
 Multiplicamos: por cada elección de portero, el numero
de posibles elecciones de defensas, y por cada una de
estas opciones, el numero de posibles elecciones de
medios, y finalmente por el numero de posibles
elecciones de delanteros.

 16 
16!
 1820 
 

 4  4 !(16  4)!

8
 
8!



28
 

 2  2!(8  2)!

4  1820  1820  28  370988800
Selecciones distintas
 Tres modelos combinatorios simples:
 Permutaciones: ordenar un conjunto de n elementos
 Variaciones: seleccionar de forma ordenada un subconjunto
de k elementos de entre un conjunto de n elementos
distintos
 Combinaciones: Seleccionar un subconjunto de k
elementos de entre un conjunto de n elementos (sin
importar el orden)
Cuando las cosas se complican,…
 Todos los modelos de problemas anteriores tienen una
versión más complicada, cuando aparecen elemento
repetidos
…¡Permutaciones, variaciones y combinaciones con
repetición!
Descargar

Diapositiva 1 - Universidad de Cantabria