8. 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

( n r) = n! r!(n−r)!.

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

(a+ b)n = ∑i=0n(n i) an−ibi. (1.9)

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 n!k!(n−k)! que es exactamente (nk). Esto en realidad es lo esperado, pues hacer las permutaciones indicadas es equivalente al siguiente problema, dado el conjunto {1, 2, …, 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.

[Siguiente][Anterior][Inicio]