Para volver al menú principal pulse sobre la palabra

Esquema del capítulo

1.Variaciones Ordinarias

2. Permutaciones de m elementos.

3. Combinaciones de m elementos tomados de n en n

Variaciones Ordinarias

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.

Formación y cálculo.

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) xx (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

[Volver al principio]

Permutaciones de m elementos.

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.

 

Clase de una permutación.

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.

[Volver al principio]

Combinaciones de m elementos tomados de n en n.

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.

Cálculo. Para calcular el número de combinaciones de m elementos tomados de n en n hagamos lo siguiente: en cada combinación de orden n permutemos entre sí sus elementos, cada combinación dará lugar a n! permutaciones, el conjunto total de agrupaciones así obtenido es el  número de variaciones de m elementos tomados de n en n. Por tanto:

Y en consecuencia, el número de combinaciones de m elementos de orden n es igual a:

  .

[Volver al principio]