|
Para volver al menú principal pulse sobre la palabra |
|---|
1.Variaciones Ordinarias
2. Permutaciones de m elementos.
3. Combinaciones de m elementos tomados de n en n
El desarrollo comienza con las variaciones ordinarias de m elementos tomados de n en n, que se define como el número de agrupaciones distintas que se pueden formar con n elementos distintos elegidos de entre los m, de manera que dos variaciones se consideran distintas si:
1. Tienen al menos un elemento distinto.
2. Si teniendo los mismos elementos, están ordenados de manera diferente.
Un ejemplo de variaciones sería el de distribuir entre un conjunto de 8 corredores los tres primeros puestos de una carrera.
Consideremos un conjunto de m objetos diferentes cualesquiera, que en lo sucesivo vamos a designar con las letras a1, a2, a3, …, a m para distinguirlos unos de otros. La formación de las variaciones de primer orden se haría considerando los m elementos a1, a2, a3…, a m; las de segundo orden añadiendo a cada una de las de primer orden los elementos que le faltan, es decir a cada una de las m les añadiríamos m-1 elementos. Por lo tanto tendríamos m x (m-1). Para las de tercer orden, de manera análoga, añadimos a cada una de las de segundo orden, los m-2 elementos restantes; y así, procediendo sucesivamente con las restantes, llegaríamos a las de orden n-1. Finalmente, para las variaciones de orden n, consideraríamos las de orden n-1 y añadiríamos a cada una de estas, los elementos que le faltan, es decir m-n+1 elementos. Tendríamos, por tanto m x (m-1) x … x (m-n+1) variaciones de m elementos tomados de n en n.
Para ser rigurosos hay que comprobar que con esta manera de proceder formamos todas las variaciones sin que falte ninguna, y también que no hay ninguna repetida.
En efecto:
1. Están todas las variaciones de orden n.
Si una variación de orden n no estuviese entre las calculadas, separando el último termino, la correspondiente variación de orden n-1 que resulta, tampoco estaría entre las calculadas; pues si estuviera, al añadirle todos los términos que no contienen, necesariamente tendríamos que añadirle éste otro y sería una de ellas. Procediendo de la misma manera, separamos el último elemento de la variación de orden n-1, resultando una de orden n-2 que necesariamente, por la misma razón, no estaría entre las calculadas. Llegaríamos, al final, a una variación de orden 1, formado por un solo elemento, que necesariamente no sería uno de los a1, a2, a3, …, a m; lo cual resultaría absurdo.
2. No hay ninguna repetida.
En efecto, las m variaciones de orden 1 son todas distintas, pues los elementos a1, a2, a3,…, a m; lo son. Las de orden 2 se obtienen añadiendo a cada de estas los m-1 elementos que no contienen. En consecuencia, estas variaciones de orden 2, si proceden de la misma variación de orden 1 tienen el último elemento distinto, y si proceden de distinta variación de orden 1, tienen, al menos, el primero. En cualquiera de los dos casos dan lugar a variaciones diferentes. Reiterando el razonamiento llegamos a que las variaciones de orden n, si proceden de la misma variación de orden n-1, tienen distinto el último elemento, y si proceden de distinta variación de orden n-1, alguno, por lo menos, de estos n-1 primeros elementos es diferente. Por tanto, en cualesquiera de los casos dan lugar siempre a variaciones diferentes y en consecuencia no puede haber, mediante este método empleado para construirlas ninguna repetida.
Ejemplo
Formación de las variaciones de 4 elementos
. Podemos, sin riesgo de equivocación, identificar a cada uno de estos
elementos por sus índices respectivos. Así las variaciones de orden uno serían:
1, 2, 3, 4.
Las de orden dos, añadimos a la de orden uno, cada uno de los restantes elementos que le faltan, empezando por los más pequeños.
12, 13, 14
21, 23, 24
31, 32, 34
41, 42, 43.
Las de orden 3, las obtenemos añadiendo a cada una de las variaciones de orden 2 cada uno de los elementos que le faltan, empezando por los más pequeños.
123, 124
132, 134
142, 143
213, 214
231, 234
241, 243
312, 314
321, 324
341, 342
412, 413
421, 423
431, 432.
Las de orden 4, la obtenemos añadiendo a las de orden tres el elemento que les falta.
1234, 1243
1324, 1342
1423, 1432
2134, 2143
2314, 2341
2413, 2431
3124, 3142
3214, 3241
3412, 3421
4123, 4132
4213, 4231
4312, 4321.
Observando
atentamente el resultado obtenido en cada una de estas variaciones vemos que se
constituyen en una serie siempre
creciente. Este resultado nos inspira un método de construcción de las
variaciones, el más rápido en la práctica pues no necesita del cálculo de
las variaciones de ordenes inferiores, que consiste en ir colocando los
elementos de manera que el número resultante sea cada vez mayor. Por ejemplo
las variaciones de orden 5 formadas con los elementos
12345 12346 12347 13245 13246 13247
12354 12356 12357 13254 13256 13257
12364 12365 12367 13264 13265 13267
12374 12375 12378 13274 13275 13276
12435 12436 12437 13425 13426 13427
12453 12456 12457 etc., etc., etc.,
12463 12465 12467
12473 12475 12476
12534 12536 12537
12543 12546 12547
12563 12564 12567
12573 12574 12576
12634 12635 12637
12643 12645 12647
12653 12654 12657
12673 12674 12675
12734 12735 12736
12743 12745 12746
12753 12754 12756
12763 12764 12765
Se podrían definir como las variaciones ordinarias de m elementos tomados de m en m; aunque, dada su importancia, conviene utilizar una definición propia que resalte ciertas características de las permutaciones. Así, pues, definimos las permutaciones de m elementos como las distintas ordenaciones que se pueden hacer con esos m elementos ordenándolos de todas las maneras posibles. Obviamente su número coincidirá con el de las variaciones de m elementos tomados de m en m. Por tanto:
Pm
= m.(m-1). … .1 = m!
Para la formación de las permutaciones valen las mismas reglas que para la formación de las variaciones.
Dados los elementos distintos
adoptaremos una de las permutaciones, por ejemplo
como principal. En cualquier otra permutación diremos que dos elementos presentan una inversión cuando, prescindiendo del resto de los elementos, se suceden en orden contrario al principal. Si están en el mismo orden que en la permutación principal diremos que forman una permanencia.
Dada una permutación cualquiera, llamaremos índice de la permutación al número de inversiones que presenta. Para calcular el índice de una permutación, procedemos de la manera siguiente:
Hallamos el número de inversiones del primer elemento con cada uno de los elementos que le siguen, a continuación del segundo con cada uno de los que vienen a continuación, así hasta el penúltimo que compararíamos con el último. Sumando el total de las inversiones tendríamos el índice.
Diremos que la permutación es de clase par o impar si el índice es un número par o impar.
Cuando en una permutación se cambian entre sí dos elementos cualesquiera diremos que se ha efectuado una trasposición.
Teorema. La clase de una permutación cambia cuando se efectué una trasposición.
Para demostrarlo distinguiremos dos casos:
a) Que los elementos que se trasponen sean consecutivos.
En este caso, la situación relativa de los restantes elementos respecto de estos dos no varía, ni tampoco la situación relativa del resto de los elementos entre sí. La única que cambia es la posición recíproca de estos dos elementos entre sí, lo que hace aumentar o disminuir en una unidad, según sean los índices de estos dos elementos, el número de inversiones. En consecuencia, si la permutación era par, ahora es impar; y al revés.
b) Que entre los elementos que se trasponen a i y a j haya h elementos intermedios.
En este caso, trasponemos aj con sus inmediatos predecesores h veces y una más con ai para colocarlo delante; y ai lo trasponemos h veces con sus inmediatos seguidores, hasta la posición dónde estaba aj. Resultando en total 2h + 1 trasposiciones. Como en cada una de estas trasposiciones cambia la clase de la permutación, y aquí se han realizado un total de 2h + 1 trasposiciones, que es un número impar, la permutación ha cambiado de clase.
Teorema Hay tantas permutaciones de clase par como de clase impar.
Para demostrarlo basta considerar el conjunto de todas las permutaciones de m elementos y fijémonos en dos elementos predeterminados cualesquiera, hagamos una trasposición de esos dos elementos en cada una de las permutaciones. Las permutaciones que antes eran de clase par, al hacer la trasposición son ahora de clase impar y recíprocamente, las que eran de clase impar son ahora de clase par. En consecuencia, por cada permutación par hay una impar, y por cada permutación impar hay una par y por tanto el número de una y otra son el mismo.
En la demostración implícitamente se está suponiendo que al trasponer dos elementos fijados de antemano en todas las permutaciones, obtenemos, otra vez, el conjunto de todas las permutaciones, es decir que al hacer esta operación no vamos a obtener ninguna repetida. En efecto, si hubiera alguna repetida, al deshacer las trasposiciones de las que proceden, ambas darían lugar a la misma permutación, lo que es absurdo.
Se definen como las agrupaciones distintas que podemos hacer con n elementos escogidos de entre los m, de manera que dos agrupaciones las consideramos como diferentes si, y solamente si, tienen, al menos, un elemento distinto. Por consiguiente, dos agrupaciones que tengan los mismo elementos, sea en el orden que sea, se considerarán iguales y por tanto la misma combinación.
Formación y cálculo. Para formar las combinaciones de orden n de m elementos, procedemos progresivamente, partiendo de las de orden 1 y formando a partir de ellas las de orden 2, con estas formamos las de orden 3; y así, sucesivamente, vamos formando las de orden superior, hasta llegar al orden deseado.
Las combinaciones de orden 1 de m elementos serían:
,
, ,….,
.
Para formar las de orden 2, añadimos a las de orden 1 cada uno de los elementos que tienen índice estrictamente mayor que el anterior de orden 1. Así pues, serían:
,
, ,…,
,
, ,…,
….
.
Análogamente, para formar las de orden 3, partiendo de las de orden 2, añadimos,. A cada una de ellas, cada uno de los elementos que tienen índice mayor que el último. De esta forma, tendríamos:
,
,
,…,
,
,
,…,
…
.
Para formar las de orden n, partiríamos de las de orden n-1 y a cada una de ellas añadiríamos, cada uno de los elementos que tienen índice estrictamente superior al último, si es que existen. Quedando, pues:
,
,
,…,
,
,
,…,
…
.
De esta manera hemos construido todas las combinaciones de orden n sin que falte ninguna y también sin que ninguna de ellas se repita. En efecto. Supongamos que una combinación de n elementos formada con los m dados no se encuentra entre las construidas. Ordenemos los elementos de esa combinación de menor a mayor; y separemos el último elemento, nos quedaríamos con una combinación de n-1 elementos que tampoco figuraría entre las de partida, pues si estuviera al tener el último elemento índice superior al penúltimo, también ésta se encontraría entre las de orden n, en contra de lo supuesto. Repitamos el razonamiento para las combinaciones de orden n-1 y separemos el último elemento, nos quedaríamos con una combinación de orden n-2 que tampoco estaría entre las de partida. Al final del proceso, llegaríamos a una combinación de orden 1, es decir un elemento, que no estaría entre los m dados, lo que es un absurdo.
Que no se repiten es inmediato: si proceden de la misma combinación de orden n-1, diferirán en el último elemento y, si proceden de distintas combinaciones de orden n-1, diferirán en al menos uno de los n-1 primeros elementos.
Y en consecuencia, el número de combinaciones de m elementos de orden n es igual a:
.