Combinatoria

De Wikipedia

Tabla de contenidos

Permutaciones

Se llama permutaciones de n elementos, y se representa P_n\;, a las distintas agrupaciones de n elementos ordenadas obtenidas a partir de esos n elementos.

ejercicio

Proposición

El número de permutaciones de n elementos se pueden calcular con la siguiente fórmula:

P_n=n!\;
Demostración:

Demostración:

Si quiero formar ordenar n elementos, el primer elemento del grupo lo puedo escoger de n maneras distintas (puesto que dispongo de n elementos), el 2º de (n-1) maneras, el 3º de (n-2) maneras, ..., y el n-ésimo, de 1 sola manera. Multiplicando todas las posibilidades obtengo la fórmula.

video
Ejercicios: Permutaciones
Ejercicio 1 (0'48")     Sinopsis:

Calcula las permutaciones de 4 elementos sin repetición: P_{4}\;

Ejercicio 2 (0'55")     Sinopsis:

Calcula las permutaciones de 7 elementos sin repetición: P_{7}\;

Problema 1 (1'16")     Sinopsis:

Calcula cuántos números de cuatro cifras diferentes (sin repetir la misma cifra) pueden formarse con los dígitos 3,5,7 y 9.

Problema 2 (1'29")     Sinopsis:

Di el número de posibles clasificaciones de los 9 nadadores que participan en una prueba de 100 m mariposa.

Problema 3 (6'43")     Sinopsis:

¿Cuántos números de 5 cifras se pueden formar con 5 dígitos distintos si no se pueden repetir las cifras? (Permutaciones sin repetición)

Permutaciones con repetición

Se llama permutaciones con repetición de n elementos, donde el primer elemento se repite "a" veces , el segundo "b" veces , el tercero "c" veces, ..., con n=a+b+c+..., y se representa PR_n^{a,b,c,...}\;, a las distintas agrupaciones ordenadas de n elementos formadas con esos n elementos, teniendo en cuenta que los elementos repetidos son indistinguibles.

ejercicio

Proposición

El número de permutaciones con repetición de n elementos, donde el primer elemento se repite "a" veces , el segundo "b" veces , el tercero "c" veces, ..., con n=a+b+c+..., se pueden calcular con la siguiente fórmula:

PR_n^{a,b,c,...}=\cfrac{n!}{a!b!c!...}\;
Demostración:

Demostración:

Las permutaciones ordinarias con n elementos son n!. Pero cada elemento repetido "a" veces se puede colocar de a! formas distintas, de manera que debo dividir n! por a! para quedarme solo con las formaciones no repetidas. Lo mismo se hace con los "b", "c", ... elementos repetidos, por lo que habrá que dividir también por b!, c!, ...

video
Ejercicios: Permutaciones con repetición
Ejercicio 1 (1'28")     Sinopsis:

Calcula las permutaciones de 12 elementos con repetición de 7,3 y 2: PR^{7,3,2}_{12}\;

Ejercicio 2 (2'02")     Sinopsis:

Calcula las permutaciones de 7 elementos con repetición de 3,2 y 2: PR^{3,2,2}_{7}\;

Problema 1 (1'40")     Sinopsis:

Una pareja ha tenido 3 niñas y 1 niño. ¿En cuántos órdenes diferentes los ha podido tener?

Problema 2 (2'13")     Sinopsis:

¿Cuántas palabras distintas, tengan o no sentido, podemos forma con las letras de la palabra ORDENADOR?

Problema 3 (1'40")     Sinopsis:

¿De cuántas maneras distintas podemos ordenar 3 bolas verdes, 2 rojas y 1 azul?

Combinaciones

Se llaman combinaciones de n elementos tomados de k en k (n ≥ k), y lo representaremos por C^k_n \, o C_{n,k} \,, a los distintos subconjuntos de k elementos que pueden formarse con los n elementos dados. Nótese que al tratarse de subconjuntos no importa el orden y no pueden repetirse los elementos.

ejercicio

Proposición

El número de combinaciones de n elementos tomados de k en k (n ≥ k) puede calcularse con la siguiente fórmula:

C^k_n = {n\choose k} = \frac{n!}{k! (n-k)!}
Demostración:

Demostración:

Si se tiene un conjunto con n elementos, de los cuales se van a escoger k de ellos, la selección (ordenada) puede hacerse de

n \cdot (n-1) \cdot (n-2) \dots \cdot (n-k+1)

formas, ya que en el primer paso se tienen n opciones, en el segundo se tienen n-1, en el tercero n-2, y así sucesivamente, terminando en el paso k que tendrá n-k+1 opciones.

Ahora, para eleiminar los conjuntos repetidos, hay que dividir el producto anterior entre el número de selecciones "equivalentes" (conjuntos con los mismos elementos en distinto orden). Pero si se tiene k objetos, hay k! formas de permutarlos, es decir, k! formas de listarlos en distinto orden.

Concluimos que el número de subconjuntos con k elementos, escogidos de un conjunto con n elementos es

{n\choose k} = \frac{ n \cdot (n-1) \cdot (n-2) \dots (n-k+1)}{k!}

Multiplicando el numerador y el denominador por 1 \cdot 2 \cdot 3 \cdots (n-k) \;

{n\choose k} = \frac{ 1\cdot 2\cdot 3\cdots (n-k)\cdot (n-k+1)\cdots (n-2)\cdot (n-1)\cdot n}{1\cdot 2 \cdot 3\cdots (n-k) \cdot k!}

o lo que es lo mismo, expresado con factoriales:

{n\choose k} = \frac{n!}{k! (n-k)!}
c.q.d.

Ver: Números combinatorios

video
Combinaciones ordinarias (o sin repetición)
Tutorial 1 (11'27")     Sinopsis:

Combinaciones (sin repetición). Ejemplos.

Tutorial 2 (9'03")     Sinopsis:

Combinaciones (sin repetición). Ejemplos.

Tutorial 3 (6'45")     Sinopsis:

Combinaciones (sin repetición). Ejemplos.

Ejercicio 1 (1'15")     Sinopsis:

Calcula C_{6,5}\;

Ejercicio 2 (1'29")     Sinopsis:

Calcula C_{8,5}\;

Problema 1 (1'48")     Sinopsis:

Calcula cuántos zumos de cuatro frutas distintos se pueden hacer con siete clases de fruta.

Problema 2 (1'20")     Sinopsis:

Vicente tiene 5 amigos y quiere salir cada sábado con 3 amigos diferentes. ¿Cuántos sábados podrá salir sin repetir?

Problema 3 (1'04")     Sinopsis:

Tenemos cuatro colores (verde, rojo, azul y amarillo). ¿Cuántas mezclas diferentes podemos hacer si los mezclamos dos a dos?

Problema 4 (1'04")     Sinopsis:

Tu profesora de Lengua Castellana te dice que, cuando acabes el curso, tienes que haber leído 3 libros de una lista de 5. ¿Cuántas posibles elecciones puedes hacer?

Problema 5 (2'18")     Sinopsis:

En un colegio una comisión consta de 2 profesores y 4 alumnos. ¿Cuántas comisiones distintas se pueden formar con 7 profesores y 10 alumnos?

Combinaciones con repetición

Se llaman combinaciones con repetición de n elementos tomados de k en k, y lo representaremos por CR^k_n \, o CR_{n,k} \,, a las distintas agrupaciones de k elementos que pueden formarse con los n elementos dados, de manera que pueden repetirse los elementos y no importa el orden de los mismos.

Nota: n no tiene por qué ser mayor o igual que k.

ejercicio

Proposición

El número de combinaciones con repetición de n elementos tomados de k en k (n ≥ k) puede calcularse con la siguiente fórmula:

CR^k_n = {n+k-1\choose k} = \frac{(n+k-1)!}{k! (n-1)!}

Variaciones con repetición

Se llama variaciones con repetición de n elementos tomados de k en k (n ≥ k), y se representa VR_n^k\;, o bien VR_{n,k}\;, a las distintas agrupaciones ordenadas de n elementos que se pueden formar a partir de m elementos dados en las que se pueden repetir los elementos.

ejercicio

Proposición

El número de variaciones con repetición de n elementos tomados de k en k (n ≥ k) se pueden calcular con la siguiente fórmula:

VR_{n,k}=n^k\;
Demostración:

Demostración:

Si quiero formar grupos de n elementos en los que importa el orden, el primer elemento del grupo lo puedo escoger de n maneras distintas (puesto que dispongo de n elementos), el 2º también de n maneras (pues puedo repetirlo), el 3º también de n maneras, ..., y el k-ésimo, de n maneras distintas. Multiplicando todas las posibilidades obtengo la fórmula.

video
Ejemplos: Variaciones con repetición
Ejercicio 1 (0'44")     Sinopsis:

Calcula VR_{3,2}\;

Ejercicio 2 (0'37")     Sinopsis:

Calcula VR_{5,2}\;

Problema 1 (1'15")     Sinopsis:

¿Cuántos números de dos cifras pueden formarse con los dígitos 1, 2 y 3, si se pueden repetir las cifras

Problema 2 (3'39")     Sinopsis:

Con las cifras 0, 1, 3, 5 y 7, ¿cuántos números de 4 cifras podemos escribir?

Variaciones ordinarias

Se llama variaciones ordinarias (o sin repetición) de n elementos tomados de k en k (n ≥ k), y se representa V_n^k\;, o bien V_{n,k}\;, a las distintas agrupaciones ordenadas de n elementos que se pueden formar a partir de m elementos dados en las que no se pueden repetir los elementos.

ejercicio

Proposición

El número de variaciones ordinarias de n elementos tomados de k en k (n ≥ k) se pueden calcular con la siguiente fórmula:

V_{n,k}=\cfrac{n!}{(n-k)!}=n(n-1)(n-2)(n-3) \cdots (n-k+1)
Demostración:

Demostración:

Si quiero formar grupos de n elementos en los que importa el orden, el primer elemento del grupo lo puedo escoger de n maneras distintas (puesto que dispongo de n elementos), el 2º de (n-1) maneras distintas (pues no puedo repetir el anterior), el 3º de (n-2), ..., y el k-ésimo, de (n-k+1) maneras distintas. Multiplicando todas las posibilidades obtengo la fórmula.

video
Ejemplos: Variaciones ordinarias
Ejercicio 1 (1'12")     Sinopsis:

Calcula V_{6,2}\;

Ejercicio 2 (1'26")     Sinopsis:

Calcula V_{9,4}\;

Problema 1 (1'15")     Sinopsis:

¿Cuántos números de dos cifras pueden formarse con los dígitos 1, 2 y 3, si no se pueden repetir las cifras.

Problema 2 (4'24")     Sinopsis:

Cuántos números de tres cifras no repetidas se pueden formar con los dígitos 2, 3, 4, 5 y 6? ¿Cuántos son pares?¿Cuántos terminan en 45?

Problema 3 (1'53")     Sinopsis:

En una competición participan 6 corredores pero sólo hay 3 premios distintos (1º, 2º y 3º). ¿De cuántas formas distintas pueden asignarse 3 los premios entre los 6 atletas?

Ejercicios y Problemas

Ejercicios y problemas resueltos: Permutaciones     Descripción:

Ejercicios y problemas resueltos sobre permutaciones.

Ejercicios y problemas resueltos: Combinaciones     Descripción:

Ejercicios y problemas resueltos sobre combinaciones.

Ejercicios y problemas resueltos: Variaciones     Descripción:

Ejercicios y problemas resueltos sobre variaciones.

Problemas resueltos: Combinatoria     Descripción:

Problemas resueltos sobre combinatoria.

Ejercicios y problemas resueltos: Combinatoria     Descripción:

Problemas resueltos sobre combinatoria.

Ejercicios resueltos: Ecuaciones combinatorias     Descripción:

Ejercicios resueltos sobre ecuaciones con expresiones combinatorias.

Autoevaluación: Ejercicios de combinatoria     Descripción:

Ejercicios de autoevaluación sobre combinatoria.

Autoevaluación: Problemas de combinatoria I     Descripción:

Autoevaluación sobre problemas de combinatoria.

Autoevaluación: Problemas de combinatoria II     Descripción:

Autoevaluación sobre problemas de combinatoria.

Obtenido de "http://maralboran.org/wikipedia/index.php/Combinatoria"
Herramientas personales
* AVISO: Para que te funcionen los applets de Java debes usar Internet Explorer y seguir las instrucciones de la Ayuda del menu de la izquierda