Diferencia entre revisiones de «Combinatoria»

Revisión del 18:40 15 oct 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.

Permutaciones

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]

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

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