Combinatoria - Permutaciones (3°)

En estas semanas estuvimos aprendiendo conceptos muy útiles para el conteo de situaciones que pueden ocurrir en cualquier ámbito.
Comenzamos analizando el juego del "Sudoku" básico. El mismo es una matriz de tres por tres en el que se colocan los números del 1 al 9 y cada fila, cada columna y cada diagonal deben sumar 15.
Por consiguiente se propuso armar ternas que sumaran 15 con el conjunto dado. Así, ustedes armaron todas las ternas que puedieron, respetando las condiciones que no se repitan números y que estén ordenadas de menor a mayor.

Conjunto A={1, 2, 3, 4, 5, 6, 7, 8, 9}

Ternas de A que comienzan con 1 y suman 15: {1; 5; 9}, {1; 6; 8}
Ternas de A que comienzan con 2 y suman 15: {2; 4; 9}, {2; 5; 8}, {2; 6; 7}
Ternas de A que comienzan con 3 y suman 15: {3; 4; 8}, {3; 5; 7}
Ternas de A que comienzan con 4 y suman 15: {4; 5; 6}

Con las condiciones dadas, no hay más ternas. Y esas condiciones son necesarias para evitar confundirse.
A continuación, con cada terna queremos saber de cuántas maneras las podemos utilizar. Es decir, que con la terna {1; 5; 9} podemos hacer otras: {1; 9; 5}, {5; 1; 9} y otras (completar). ¿Cuántas son? En este caso, por ser pocos números, haciendo una lista se deduce fácilmente. Pero si fueran muchos se complicaría un poco. Entonces analicemos.

Los números {1; 5; 9} se deben ubicar en los lugares correspondiente a unidad, decena y centena. Veamos: para la centena podemos elegir el 1, el 5 o el 9. Para la decena podemos elegir entre dos de ellos(porque ya utilizamos el primero en la centena), y para la unidad queda uno solo. Así 3 posibilidades para el primer lugar, 2 para el segundo y 1 para el tercero... son 3 * 2 * 1 = 6. Entonces podemos organizar los tres números de seis maneras distintas.

-------------------------------------------

A esta multiplicación (3 * 2 * 1)  se la llama factorial de un número (en este caso factorial de 3) y se escribe n! (en este caso 3!). Por convención se define que el factorial de 0 es 1. Es decir 0! = 1.
Conceptualmente es la permutación de n elementos. Es decir que:

P_n = n! = n * (n-1) * (n-2) * (n-3) * ... * (n-n+1)

-------------------------------------------

Ejemplo 1:
¿De cuántas maneras distintas pueden sentarse 4 personas en 4 lugares libres?

Esto es la permutación de 4 elementos.

P₄ = 4! = 4 * 3 * 2 *1 = 24

Rta: Pueden sentarse de 24 maneras diferentes.

-------------------------------------------

Ejemplo 2:
Si en un cd hay 10 canciones grabadas y quisiera escucharlas en distinto orden cada día. ¿Cuántos dias pasarán hasta que vuelva a repetirse la serie de canciones?

Esto es la permutación de 10 elementos.

P₁₀ = 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 *1 = 3628800

Rta: Pasarán 3628800 días antes de repetir una serie.

-------------------------------------------

Luego, habrá 8 ternas con 6 posibles permutaciones cada una, Por lo tanto habrá 48 ternas utilizables para armar el "Sudoku" básico. Un ejemplo:

Ejercicio: Armar dos Sudoku para completar, colocando sólo 3 datos en la matriz.