Teoria

Combinatoria elemental
Los elementos principales de la Combinatoria son las variaciones, las
permutaciones y las combinaciones. Los nombres entre estos conceptos se suelen
olvidar (al menos a mí),así que conviene insistir en las ideas: con ellas se llega más
lejos. Sea el conjunto de elementos A = {a1, a2, ..., an}:
Variaciones
Queremos formar, con algunos elementos del grupo, todos losposibles vectores
(la posición tiene significado) de k elementos distintos. Para la primera posición
podemos elegir entre los n elementos; por cada una de estas elecciones, para la
segunda posiciónpodemos elegir entre n-1 elementos; así hasta que para la posición k
podemos elegir entre los n-(k-1) elementos del conjunto que quedan sin colocar. Cada
uno de los vectores que formamos así se llamavariación, aunque frecuentemente
estamos interesados sólo en cuántos vectores se pueden forma, no en cuáles son. El
número de variaciones totales es:
Vn k =n⋅n−1⋅n−2⋯n−[k−1]= n !
n−k! .Si los elementos no tuviesen que ser distintos, es decir, pudiesen repetirse
(porque lo copiemos en el vector y lo devolvamos al conjunto inicial), razonando igual
tendríamos que para cada posicióndel vector podemos elegir entre los k elementos de
conjunto. Cada variación así formada se llama variación con repetición, y el número
total de todas ellas es:
VRn k =n⋅n⋅⋯n=nk
Nótese que si puedehaber repetición, tiene sentido que k≥n , es decir, que el vector
tenga más elementos que el conjunto inicial.
Permutaciones
Si ahora queremos colocar todos los elementos (distintos) del conjuntoen un
vector (la posición importa) de tamaño n, hay que utilizar todos. Cada colocación se
llama permutación, y el número de posibles permutaciones, razonando exactamente
como antes, es:Pn=n⋅n−1⋅n−2⋯1=n! .
Vemos, pues, que Pn=Vn n .
También existen las permutaciones con repetición. Para entenderlas podemos
hacer la floritura (truco) de imaginar que los elementos que queremos ordenar...