Igualmente nombradas Ordenaciones sin Repetición. Vamos a interpretarlas:
Vemos que es similar a las permutaciones. Tenemos
objetos, hagamos listas de tamaño tal que : Para
, hay objetos posibles.
Para 2, hay.
Para, hay Es decir,
Def. (Ordenaciones)
Sea
un conjunto finito con . Las ordenaciones de los elementos de tomados de en son las funciones tales que es inyectiva. Denotamos al número de ordenaciones,
Observación.
¿Si
? Se tiene . Y por convicción , por lo que .
De esta forma, las ordenaciones son casos especiales de las ordenaciones con repetición^[Ordenaciones con Repeticion]. Importante, consideramos un ejemplo para ilustrar el resultado general.
Ejemplo 1.
Las “palabras” de dos letras distintas que pueden formar con las letras
y son: Podemos ver a estas palabras como funciones de
en : Observe que como formamos palabras con letras distintas, estas funciones son inyectivas.
Ejemplo para el lema.
Sea
. Las funciones inyectivas de en son Entonces
. Ahora, tomemos una en particular , ¿cuántas funciones inyectivas hay de en que extiendan a ? Esta extensión tiene la forma , donde x es cualquier elemento de que no sea para que esta extensión siga siendo inyectiva. Hay posibles elementos de que pueden ser , por lo que por cada función inyectiva en , hay funciones inyectivas que la extienden de en . Así, hay funciones inyectivas de en .
Ahora sí, veamos el siguiente lema.
Lema.
Sean
tales que . Entonces
Proof.
pag. 245 Algebra Sup. I
Teorema.
Si
y , entonces Otra manera es
Proof.
Por inducción sobre
.
Paso Base: Si, entonces . Dado que hay funciones inyectivas distintas de en un conjunto , . Por otro lado, como . Así, en este caso, efectivamente, . Hip. de Inducción: Supongamos que
.
Entonces por el lema anterior,. Usando la Hip. de Inducción, tenemos que Entonces
Por lo tanto,
siempre que y . $$
\tag*{}
Un caso especial de las ordenaciones son las permutaciones.^[Permutaciones]