Combinatoria
Página 2: factorial y permutaciones
❗ Factorial
El factorial de n (denotado \(n!\)) es el producto de todos los enteros de 1 hasta n:
\(n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1\)
📋 Ejemplos:
| n | n! | Cálculo |
|---|---|---|
| 0 | 1 | por definición |
| 1 | 1 | 1 |
| 2 | 2 | 2 × 1 |
| 3 | 6 | 3 × 2 × 1 |
| 4 | 24 | 4 × 3 × 2 × 1 |
| 5 | 120 | 5 × 4 × 3 × 2 × 1 |
| 6 | 720 | 6 × 5! |
| 10 | 3,628,800 | 10 × 9 × ... × 1 |
💡 Propiedad importante:
\(n! = n \times (n-1)!\)
Ejemplo: 5! = 5 × 4! = 5 × 24 = 120
✏️ Cálculos con factoriales:
\(\frac{8!}{6!} = \frac{8 \times 7 \times 6!}{6!} = 8 \times 7 = 56\)
\(\frac{10!}{8! \times 2!} = \frac{10 \times 9 \times 8!}{8! \times 2} = \frac{90}{2} = 45\)
🔄 Permutación (Permutation)
Una permutación = ordenación de todos los elementos en un orden determinado
En una permutación, el orden importa y se usan todos los elementos
Número de permutaciones de n elementos = \(n!\)
✏️ Ejemplo 1: ordenar personas en una fila
¿De cuántas formas se pueden ordenar 4 personas en una fila?
Primer lugar: 4 opciones
Segundo lugar: 3 opciones
Tercer lugar: 2 opciones
Cuarto lugar: 1 opción
Total: 4! = 4 × 3 × 2 × 1 = 24 formas
✏️ Ejemplo 2: colocar libros en una estantería
¿De cuántas formas se pueden colocar 6 libros distintos en una estantería?
6! = 720 formas
Diagrama: todas las permutaciones de {A, B, C}
🎯 Permutaciones con condiciones
✏️ Ejemplo 3: elemento determinado en un extremo
5 personas en fila. Carlos debe estar en el primer lugar. ¿Cuántas ordenaciones?
Carlos fijo en el primer lugar
Quedan 4 personas para 4 lugares
Total: 4! = 24 formas
✏️ Ejemplo 4: elemento en cualquier extremo
5 personas en fila. Carlos debe estar en un extremo (primero o último). ¿Cuántas ordenaciones?
Carlos puede estar en el lugar 1 o el lugar 5: 2 opciones
Las otras 4 personas: 4! = 24 ordenaciones
Total: 2 × 4! = 2 × 24 = 48 formas
✏️ Ejemplo 5: dos elementos adyacentes
5 personas en fila. Carlos y Pablo deben estar adyacentes. ¿Cuántas ordenaciones?
Método: tratar Carlos+Pablo como "una sola unidad"
Tenemos 4 "unidades" que ordenar: 4! = 24
Dentro de la unidad, Carlos y Pablo pueden intercambiarse: 2! = 2
Total: 4! × 2! = 24 × 2 = 48 formas
✏️ Ejemplo 6: dos elementos no adyacentes
5 personas en fila. Carlos y Pablo no pueden estar adyacentes. ¿Cuántas ordenaciones?
Método: complemento
Total de ordenaciones: 5! = 120
Ordenaciones adyacentes: 48 (del ejemplo 5)
Total: 120 - 48 = 72 formas
🔁 Permutaciones con repetición
Cuando hay elementos iguales (repetidos), el número de permutaciones disminuye:
\(\frac{n!}{n_1! \times n_2! \times ... \times n_k!}\)
donde \(n_1, n_2, ...\) son el número de repeticiones de cada elemento
✏️ Ejemplo 7: permutaciones con letras repetidas
¿Cuántas palabras distintas (con o sin significado) se pueden formar con las letras de ABBA?
4 letras: A aparece 2 veces, B aparece 2 veces
\(\frac{4!}{2! \times 2!} = \frac{24}{2 \times 2} = \frac{24}{4} = 6\)
6 palabras: AABB, ABAB, ABBA, BAAB, BABA, BBAA
✏️ Ejemplo 8: permutaciones de la palabra MISSISSIPPI
11 letras: M(1), I(4), S(4), P(2)
\(\frac{11!}{1! \times 4! \times 4! \times 2!} = \frac{39916800}{1 \times 24 \times 24 \times 2} = \frac{39916800}{1152} = 34650\)
💡 ¿Por qué dividimos?
Porque intercambiar elementos iguales no produce una nueva ordenación.
En ABBA, las dos A son iguales - intercambiarlas no cambia nada.
⭕ Permutaciones circulares
En una permutación circular (alrededor de una mesa redonda), no hay "principio" ni "fin".
Número de ordenaciones = \((n-1)!\)
✏️ Ejemplo 9: 5 personas se sientan alrededor de una mesa redonda. ¿Cuántas ordenaciones?
\((5-1)! = 4! = 24\) ordenaciones
💡 ¿Por qué (n-1)! y no n!?
En un círculo, si todos se desplazan una posición se obtiene la misma ordenación.
Por eso se "fija" un elemento y se ordenan los n-1 restantes.
💡 Consejos para el examen
0! = 1 (por definición)
Adyacentes: tratar como una sola unidad
No adyacentes: complemento
Repeticiones: dividir por factoriales
📝 Resumen de la página 2
Factorial: \(n! = n \times (n-1) \times ... \times 1\)
Permutación (todos los elementos): \(n!\)
Con repetición: \(\frac{n!}{n_1! \times n_2! \times ...}\)
Circular: \((n-1)!\)