Diferencia entre revisiones de «Combinatoria»

Revisión del 22:00 29 dic 2013

Este artículo está en versión beta. El autor de este artículo no lo ha terminado todavía, por favor no lo edites hasta que elimine este mensaje.

1 Permutaciones

Crecimiento de la función factorial, comparado con la función exponencial (nótese que el gráfico está en log-log)

Permutar (del latín mutare, que significa cambiar, y el prefijo per-, que indica que algo se realiza en grado máximo) unos objetos es tanto como reordenarlos. En el lenguaje preciso de las Matemáticas, una permutación de un conjunto [math]A[/math] es una biyección de [math]A[/math] en [math]A[/math]. Si el cardinal de [math]A[/math] es [math]m[/math], hablamos de una permutación de [math]m[/math] elementos. Así, una permutación de [math]x_1, \dots, x_m[/math] es una reordenación [math]x_{\sigma 1},\dots,x_{\sigma m}[/math].

Importa contar: ¿cuántas permutaciones diferentes se pueden formar con [math]m[/math] elementos? La respuesta la da el producto [math]m\cdot(m-1)\cdots(m-2)\cdots 2\cdot 1[/math], que abreviamos como [math]m![/math] (léase factorial de m, o m factorial). Es fácil comprender la razón: para elegir qué elemento colocamos en el primer lugar tenemos [math]m[/math] posibilidades, para el segundo nos quedan [math]m-1[/math] posibilidades, [math]m-2[/math] para el tercero, y así sucesivamente.

Veamos algunos ejemplos:

• ¿De cuántas maneras se pueden repartir las tareas domésticas 7 hermanos (a razón de uno cada día)? La respuesta es [math]7! = 5040[/math].
• ¿Cuántas claves de 8 letras se pueden formar reordenando la palabra PERDIGÓN? La respuesta es [math]8! = 40320[/math], porque contiene 8 letras.
• ¿De cuántas maneras se puede ordenar un mazo de cartas de la baraja española (contiene 40 cartas)? La respuesta es [math]40! \approx 8.159\cdot 10^{47}[/math]

Dos observaciones:

1. [math]0!=1[/math]. Así es válida la ley de recurrencia [math](m+1)! = (m+1)\cdot m![/math]
2. Los valores de [math]m![/math] crecen muy deprisa al aumentar [math]m[/math]. En la gráfica de la derecha, se muestra cómo crece comparado con la función exponencial, de crecimiento muy rápido. El gráfico está en escala logarítmica, y muestra que al incrementar un orden de magnitud el valor de [math]m[/math], el valor de [math]m![/math] crece en varios órdenes de magnitud.

2 Variaciones

2.1 Variaciones ordinarias

Dados [math]m[/math] elementos [math]a_1,\dots,a_m[/math], si seleccionamos [math]n[/math] de ellos prestando atención al orden en que los elegimos, decimos que tenemos una variación de esos [math]m[/math] elementos tomados de [math]n[/math] en [math]n[/math]. Si queremos darle más precisión, podemos decir que una variación es una aplicación inyectiva del conjunto [math]{1,2,\dots,n}[/math] en el conjunto [math]A={a_1,\dots,a_m}[/math].

El número de tales variaciones se expresa mediante un producto de [math]n[/math] factores, empezando por [math]m[/math] y decreciendo hasta llegar a [math]m-(n-1)[/math]. Es decir, [math]V_{m,n} = m\cdot (m-1) \cdots (m-n+1)[/math], que podemos abreviar como [math]\displaystyle \frac{m!}{(m-n)!}[/math]

Nótese que si [math]m=n[/math], entonces tenemos permutaciones, y que si [math]n\gtm[/math], entonces [math]V_{m,n} = 0[/math].

Veamos algunos ejemplos:

• Elegir junta directiva (presidente, vicepresidente y secretario) entre 20 personas: como tenemos 20 personas y la junta son 3, y además, tres mismas personas pueden formar juntas directivas diferentes (con diferentes cargos cada persona), tenemos que es posible formar [math]V_{20,3} = 6840[/math] juntas directivas diferentes.
• Formar un equipo de baloncesto (5 posiciones) con 8 jugadores: tenemos [math]V_{8,5}=6720[/math] alineaciones posibles.

2.2 Variaciones con repetición

Si en la definición de variación de m elementos tomandos de n en n tachamos la palabra inyectiva, obtenemos las variaciones con repetición. Estamos hablando así de aplicaciones de un conjunto de n elementos en uno de m.

¿Cuántas hay? Claramente, el número total es un producto de n factores, que empieza en m pero ahora no va disminuyendo [math]m\cdot m\cdot m \cdots m = m^n[/math].

Veamos algunos ejemplos:

• ¿Cuántas quinielas diferentes se pueden rellenar? [math]3^15[/math]
• ¿Cuántos números hay de cinco cifras? [math]10^5-10^4[/math] (hay que descontar los que empiezan por 0)
• ¿Cuántas claves de 4 letras se pueden formar con la palabra CAMINOS? [math]7^4 = 2401[/math]
  • ¿Y si no se pueden repetir letras? En este caso, son variaciones [math]V_{7,4} = 840[/math].

3 Combinaciones

En un conjunto de m elementos, una combinación es un subconjunto. Hablamos de combinaciones de m elementos tomados de n en n para referirnos a subconjuntos de n elementos en un conjunto de m. Suponen, pues, una selección de n objetos de una muestra de m (como las variaciones), pero sin que importe el orden: los conjuntos [math]\{a,b\}[/math] y [math]\{b,a\}[/math] son el mismo.

Para contar el número de combinaciones nos fijamos en las variaciones: cada combinación [math]\{a_1,\dots,a_n\}[/math] se puede ordenar de [math]n![/math] formas diferentes, de suerte que hay [math]n![/math] variaciones por cada combinación. Es decir, [math]n! \cdot C_{m,n}=V_{m,n}[/math], de donde despejamos y resulta: [math]C_{m,n} = \frac{m!}{n!(m-n)!}[/math]