Combinatoria

De MateWiki
Saltar a: navegación, buscar

La combinatoria se usa para enumerar, construir y razonar sobre la existencia de conjuntos de elementos, que satisfacen una serie de propiedades. En este artículo vamos a estudiar tres tipos de conjuntos: permutaciones, variaciones y combinaciones. En las permutaciones, tomaremos un conjunto de elementos, para formar conjuntos del mismo tamaño con un orden diferente de los elementos. Con las variaciones, el resultado será similar al de las permutaciones, pero formaremos conjuntos de tamaño menor al inicial. Tanto en las variaciones como en las permutaciones, el orden importa (dos conjuntos con los mismos elementos pero en diferente orden, serán dos conjuntos diferentes). Por último, las combinaciones son similares a las variaciones, pero no importa el orden. Es decir, dos conjuntos con los mismos elementos en diferente orden serán contados como un único conjunto.

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]V_{m,n} = \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]

Se suele emplear la notación [math]\begin{pmatrix}m \\ n\end{pmatrix}[/math] para ese cociente, y se denomina número combinatorio. Los números combinatorios se disponen a veces en un triángulo (de Pascal o de Tartaglia[1]) con numerosas propiedades interesantes y curiosas.

Veamos un ejemplo:

  • Cuando jugamos al mus, nos dan 4 cartas de una baraja de 40, ¿cuántas manos diferentes pueden resular?: Tendremos [math]\begin{pmatrix}40\\ 4\end{pmatrix}=91390[/math] manos diferentes, ya que el orden de las cartas no importa.
  • Al elegir 3 nombres al azar para un jurado (entre 50), ¿cuántos jurados diferentes se pueden formar? De nuevo, no importa el orden, y tendremos [math]\begin{pmatrix}50\\ 3\end{pmatrix}=19600[/math] posibles jurados diferentes.

El número combinatorio tiene las dos propiedades siguientes:

  • [math]\begin{pmatrix}m \\ 0\end{pmatrix} = \begin{pmatrix}m \\ m\end{pmatrix} = 1[/math]
  • [math]\begin{pmatrix}m+1\\ n\end{pmatrix} = \begin{pmatrix}m \\ n\end{pmatrix} + \begin{pmatrix}m\\ n-1\end{pmatrix}[/math]


Lapiz.png Tarea: Demuestre estas dos propiedades del número combinatorio


El número combinatorio aparece en el binomio de Newton[2], cuyo resultado es la suma de [math]m+1[/math] términos, cada uno de los cuales es de la forma [math]\begin{pmatrix}m\\ n\end{pmatrix}x^k y^{m-k}[/math].

4 Referencias

  1. Triángulo de Pascal (Wikipedia ES)
  2. Binomio de Newton (Wikipedia ES)