Combinaciones

3. Combinaciones

A diferencia de una permutación, en la cual el orden es importante, en una combinación el orden de los elementos no es importante. Una $r -$ combinación sobre un conjunto $A$ con $n$ elementos es un subconjunto de $A$ con $r$ elementos.

Existe un relación directa entre permutaciones y combinaciones, de hecho cada $r -$ combinación da lugar a $r!$ $r -$ permutaciones. Como conocemos el número de $r$ -permutaciones, teorema 2, entonces se tiene el siguiente teorema.

Teorema 5.

El número de r-combinaciones sobre un conjunto de $r$ elementos es

(\binom{n}{r}) = \frac{n!}{r! (n - r)!} .

Este último valor se conoce cono coeficiente binomial pues con alguna cantidad de esfuerzo es posible demostrar que:

\begin{array}{rcl} {(a + b)}^{n} = ∑_{i = 0}^{n} (\binom{n}{i}) a^{n - i} b^{i} . & (2.3) \end{array}

Muchos problemas de conteo, aunque en principio parezcan distintos, pueden resolverse recurriendo a la misma idea.

Por ejemplo considere una estructura que solo tiene 2 elementos repetidos uno $k$ veces y el otro $n - k$ veces. El número de permutaciones de los elementos en esta estructura es $\frac{n!}{k! (n - k)!}$ que es exactamente $(\binom{n}{k})$ . Esto en realidad es lo esperado, pues hacer las permutaciones indicadas es equivalente al siguiente problema, dado el conjunto ${1, 2, \dots, n}$ elegir subconjuntos de tamaño $k$ que correspondan a las posiciones en donde se van a ubicar los $k$ elementos.

Una última forma se discutirá en estas notas, no sin advertir que con las herramientas discutidas es posible abordar problemas diversos que no se han discutido en estas notas.