Combinatoria I (Permutaciones)

El primer contacto, de la mayoría de nosotros con las matemáticas se da a través de los números y la primer actividad que realizamos es contar, pero ¿qué significa esto? En matemáticas, contar es poner en correspondencia uno a uno los elementos de un conjunto con los números naturales (enteros positivos). A la acción de contar tambien se le conoce como "encontrar la cardinalidad". En principio esto no presenta gran dificultad: al primer elemento le asociamos el uno; al segundo, el dos y así sucesivamente; el número natural que corresponda al último elemento es la cardinalidad. 

En mayor o menor medida, todos sabemos contar cuando tenemos claro cuáles son los objetos a los que queremos asociar una cardinalidad. Sin embargo, existen situaciones un poco más interesantes, por ejemplo cuando no sabemos cuáles elementos pertenecen al conjunto de interés, es decir, cuando sólo tenemos información sobre cierta propiedad que cumplen, ya sea que se trate de formas de elegir, ordenar, etc.

La rama de las matemáticas que se encarga de establecer técnicas para contar se llama Combinatoria, y de ella obtenemos el Principio fundamental del Conteo, que dice lo siguiente:

Si un evento $A$ se puede realizar de $n$ formas y una vez realizado, otro evento $B$ puede realizarse de $m$ maneras distintas, entonce ambos eventos pueden ocurrir de $nm$ ($n$ por $m$) formas diferentes.

Esto se puede extender al número de eventos que queramos y nos permite resolver problemas de diversos grados de complejidad, por ejemplo:

Un edificio de departamentos tiene cinco lugares en el estacionamiento, si sólo hay tres coches, ¿de cuántas formas diferentes se pueden acomodar? La respuesta es sencilla, si asociamos los  evento con la acción de acomodar los coches, vemos que el primer evento (acomodar el primer coche), se puede realizar de cinco formas, pues hay cinco espacios. El segundo evento (acomodar el segundo coche) se puede hacer de cuatro maneras ( ya se ocupó un espacio), esto quiere decir que para acomodar el tercer coche hay tres alternativas; por lo tanto en total tenemos $(5)(4)(3)=60$ maneras de estacionar estos vehículos.

Al contar encontramos los siguientes casos de utilidad:

Permutaciones

Cuando el evento consiste en reordenar (o elegir) todos los elementos de un conjunto. Aquí podemos distinguir una característica primordial, el orden es importante y deben estar todos los elementos sin repetir ninguno. Si tenemos $n$ objetos y queremos ordenarlos, para elegir el primero tenemos $n$ posibilidades, para el segundo $n-1$, para el tercero $n-2$ y así sucesivamente hasta llegar al último para el cual tendremos sólo una opción. Por lo tanto por el principio fundamental del contéo tendremos: $n(n-1)(n-2)\cdot \cdot \cdot 1$ formas distintas de hacerlo.
Este producto, de un número por todos los enteros positivos que lo preceden, se llama factorial de ese número y se representa de la siguiente manera $n!$ (se lee n factorial).
El factorial de 5 es:
$$5!=(5)(4)(3)(2)(1)=120$$
Si a la permutación de $n$ objetos la denotamos con $P_{n}$ tenemos que:
$$P_{n}=n!$$

Permutaciones con repetición 

Ahora se trata de hacer arreglos con los $n$ elementos de un conjunto con la particularidad de que cualquiera de ellos se puede repetir las veces que queramos. Primero analizaremos un ejemplo, comenzamos con un conjunto de tres pelotas, una amarilla, otra roja y la tercera azul.

Figura 1

Queremos saber de cuántas maneras podemos hacer arreglos  con la condición de que  se pueda repetir tres veces la amarilla y dos veces las de los otros colores. Por lo tanto vamos a permutar los siete elementos del siguiente conjunto:

Figura 2

Sabemos que en total hay $P_{7}=7!=5040$ formas. Enfocaremos nuestra atención en una de ellas, por ejemplo:

Figura 3

Y prestaremos atención a las amarillas, que pueden cambiar de lugar sin que podamos distinguir cada uno de los casos, A continuación se muestran los cambios posibles etiquetando con los números del uno al tres:

Figura 4

Dado que són tres amarillas estas pueden reacomodarse (permutarse) de $3!$ formas. Y por cada una de estas, las rojas y las azules tambien se pueden permutar de $2!$ maneras. Por el principio fundamental del contéo cada configuración se repite $3!\cdot2!\cdot2!$. Por lo tanto para encontrar el número de opciones distintas, dividimos el total de opciones entre la cantidad de veces que se repite cada configuración:

$$\frac{7!}{3!\cdot 2!\cdot 2!}= \frac{7\cdot 6\cdot5\cdot 4\cdot 3! }{3!\cdot 2!\cdot 2!}=7\cdot 6\cdot 5=210 $$

El caso general es el siguiente, tenemos $n$ objetos y queremos hacer arreglos donde el primero se debe repetir $h_{1}$ veces, el segundo $h_{2}$ y así hasta llegar al enésimo que debe aparecer $h_{n}$ veces. Es importante que cada uno de los $n$ elementos aparezcan por lo menos una vez. Hacer esto es equivalente a permutar $N$ elementos donde $N=h_{1}+h_{2}+\cdot \cdot \cdot+h_{n}$. Sabemos que existen $P_{N}=N!$ formas, pero mucha de ellas son iguales dado que hay elementos repetidos que presentan reacomodos indistinguibles unos de otros. Como ya vimos en el caso particular, cada configuración se repite $h_{1}! h_{2}!\cdot \cdot \cdot h_{n}!$ veces. Por lo tanto, las permutaciones con repetición de estos $N$ elementos (denotada como $P_{N}^{h_{1}h_{2}\cdot \cdot \cdot h_{n} }$) se calcula dividiendo todos las posibles configuraciones, entre las veces que se repite cada una de ellas:
$$P_{N}^{h_{1}h_{2}\cdot \cdot \cdot h_{n} }=\frac{N!}{h_{1}! h_{2}!\cdot \cdot \cdot h_{n}!}$$

Permutaciones Circulares

Una variante interesante es la siguiente: ¿de cuántas maneras diferentes se pueden acomodar $n$ objetos en una configuración circular? Analizaremos un caso concreto, comenzamos con el siguiente conjunto:

Figura 5

Queremos organizarlo de la siguiente manera:

Figura 6

¿Cuántas formas distintas existen? Un análisis con poco rigor nos puede sugerir que el resultado se puede obtener aplicando una permutación básica y que en total tenemos $P_{5}=5!$ formas. Pero de estos 120 reacomodos, existen algunos que en la configuración circular son indistinguibles, les llamaremos permutaciones cíclicas y se obtienen a partir de cualquiera de ellos desplazando cada elemento hacia la derecha (o hacia la izquierda) y colocando el último en la primer posición (o el primero, en la posición final). Si en la figura 5 desplazamos los elementos hacia la derecha obtenemos:

Figura 7

Pero si en la misma figura desplazamos hacia la izquierda, nos queda:

Figura 8

 

Ambas representan el mismo esquema en la representación circular:

 

Figura 9

Figura 10

En las dos, cada letra se encuentra siempre entre las mismas (la B entre la A y la C, por ejemplo). 

Por lo tanto, la cantidad de formas en las que $n$ objetos se pueden reordenar en una esquema como el deseado es $n!$ menos todas las permutaciones que por ser cíclicas representan la misma configuración circular. Para contar estas últimas dejamos fijo el primer elemento y permutamos los elementos restantes lo que nos da $(n-1)!$ formas no cíclicas, dado que el primer elemento no cambia de posición. Pero ¿serán todas? para responder a esta pregunta observamos que cada uno de estos $(n-1)!$ reordenamientos tiene $n-1$ permutaciones cíclicas pues son las veces que cada elemento se puede desplazar hacia la derecha (o hacia la izquierda) antes de volver a su posición inicial. Por lo tanto existen $(n-1)(n-1)!$ permutaciones que no aportan nada a las configuraciones circulares. Esto significa que las maneras de acomodar $n$ elementos en un círculo son:

$$n!-(n-1)(n-1)!$$

Descomponemos $n!$:

$$ n(n-1)!-(n-1)(n-1)!$$

Agrupamos el factor común $(n-1)!$ y desarrollamos:

$$(n-1)![n-(n-1)]=(n-1)![n-n+1]= (n-1)!(1)=(n-1)!$$

Nos quedan únicamente $(n-1)!$. Por lo cual, si denotamos a las permutaciones circulares de $n$ elementos con $PC_{n}$ tenenmos:

$$PC_{n}=(n-1)!$$

Hemos terminado las permutaciones, tenemos las fórmulas, sin embargo nada nos garantiza que podamos resolver un problema, en principio porque un buen problema no da pistas fáciles para saber que técnica de conteo aplicar, tenemos que ser muy creativos, aplicar la experiencia (mucha o poca), pero sobre todo tener arrojo y animarnos a intentar algo por descabellado que parezca. Como ejemplo tenemos el siguiente problema:

Si sólo se permite avanzar hacia arriba y la derecha, ¿cuántos caminos diferentes existen para llegar de A a B en la siguiente figura?

Si llamanos paso a cada vez que recorremos un lado de los pequeños rectángulos, podemos observar que sin importar el camino que elijamos, tenemos que dar ocho pasos hacia la derecha y seis pasos hacia arriba, si indicamos con D el paso a la derecha y con A un paso hacia arriba, un posible camino es: ADDADAAADDDDAD (puedes checar dando los pasos como se indica). El total de caminos es igual al resultado de tomar el conjunto {A, D} y hacer arreglos de tal manera que la A se repita 6 veces y la D, ocho. Es decir, al final lo que tenemos es una permutación con repetición y el resultado es:

$$P_{14}^{6\cdot 8 }=\frac{14!}{6! \cdot 8!}=3003$$  

Existen 3003 caminos diferentes.