2 - Listas Ordenadas y Permutaciones Opciones

[S. E. Puelma Moy...]

Listas (muestras) ordenadas con reposición

Comenzamos dando una definición, con la cual trabajaremos de aquí en adelante:

Si es un conjunto, usualmente con una cantidad finita de elementos, una lista de largo es una ordenación de los objetos o elementos del conjunto : se indica qué objeto ocupa el primer lugar, qué objeto ocupa el segundo lugar, etc. hasta completar los lugares o posiciones de la lista.

Otro nombre usual para este concepto, es muestra ordenada (o variación) con reposición

Dos detalles deben quedar muy claros en esta definición: el orden es relevante, y los objetos pueden repetirse, o sea aparecer más de una vez en la lista (a menos que se diga explícitamente lo contrario)

Planteamos un ejemplo explicativo de todo lo que se ha mencionado:

Lanzamos diez veces un dado, y anotamos ordenadamente los resultados obtenidos. Los resultados son elementos del conjunto {1, 2, 3, 4, 5, 6}, y tres ejemplos de listas (de largo 10) son:

(5, 4, 4, 6, 1, 3, 6, 5, 1, 3)
(5, 4, 6, 4, 1, 3, 6, 5, 3, 1)
(1, 1, 3, 3, 4, 4, 5, 5, 6, 6)

Observamos que ellas contienen los mismos resultados, pero no en igual orden. Entonces son diferentes.

¿Cuántas listas diferentes podemos construir en este ejemplo?

Si aplicamos la regla del producto, vemos que tenemos que llenar diez posiciones, y cada una puede hacerse de seis formas distintas. El resultado es:

En un contexto más general, podemos decir lo siguiente (se explica de la misma forma que en el ejemplo):

Si un conjunto tiene elementos, el número de listas de largo que podemos construir, es igual a

Permutaciones

Un problema bastante parecido es cuando nuestra lista o muestra ordenada, no admite repeticiones. Si mantenemos la definición de lista ordenada, excepto en el importante detalle de no admitir repeticiones, hablamos de una permutación de largo , de los elementos de (un conjunto con elementos). Obviamente, debe ser . En el caso especial en que , cada elemento es usado exactamente una vez, y hablamos de una permutación (a secas, sin especificar el largo)

El número de permutaciones de este tipo, se encuentra con la misma idea. Veamos un ejemplo:

Una persona tiene diez camisas distintas. Luego de usar una camisa por un día, ésta se ensucia, y no puede volver a usarla sin lavarla, Él lava su ropa cada Domingo. ¿Cuántas formas tiene de planificar, qué camisas usará de Lunes a Sábado? El orden es relevante

Para el día Lunes tiene 10 opciones de camisa. Una vez que ocupó esa camisa, el Martes tiene 9 opciones. Después el Miércoles le quedan 8 opciones, y así sucesivamente hasta el Sábado, que tiene 5 opciones de camisa. Por la regla del producto, tiene formas de planificar qué camisas ocupará, y en qué orden, esos días.

Observamos con un poco más de cuidado, para apreciar que:

Esta manera de expresar el producto, nos motiva a estudiar el concepto de factorial, a continuación

Factorial de un número: definición y propiedades

Dado un número entero positivo , se define el factorial de como el producto de todos los números enteros positivos, menores o iguales que . Este número se denota por

Algunos valores:

De esta tabla de valores, podemos observar que se cumple la siguiente propiedad, para cualquier valor entero positivo que tome :

Convenio: . Más adelante quedará claro por qué se toma esta decisión.

¿Cuantas permutaciones tiene un conjunto?

Volviendo al problema del ejemplo, podemos escribir lo siguiente

Y en un contexto más general, podemos escribir el siguiente resultado (como es de esperar, su justificación es del mismo tipo que en el ejemplo reciente).

Si es un conjunto con elementos, y , entonces el número de permutaciones de largo , que podemos construir con los elementos de , es igual a

Escrito de esta manera, es mejor para hacer demostraciones, y también para recordarlo. Sin embargo, cuando tengan que hacer cálculos, lo más seguro suele ser hacer todas simplificaciones al comienzo

Para que la fórmula sea válida, aún en casos extremos, como o bien , se entiende que 0!=1, como mencionamos antes