Combinatoria

Recordatorio de las definiciones básicas de combinatoria
Variaciones con repetición

Dado un conjunto E={a1,...., am} con m elementos, se define una
variación con repetición de los m elementos de Etomados de n en n de
la forma siguiente: n elementos de E, dados en un orden, de los
cuales alguno puede estar repetido.
El número de tales variaciones con repetición coinciden obviamenente con elcardinal
(número de elementos) del producto cartesiano de E, n veces, es decir

E
E x 43
...4
xE
1x42
4
n veces

Dicho cardinal es VR nm = mn
Variaciones

Dado un conjunto E={a1,...., am} con m elementos,se define una
variación de los m elementos de E tomados de n en n de la forma
siguiente: n elementos distintos de E, dados en un orden.
El número de tales variaciones es igual al producto de nfactores decrecientes en una
unidad , a partir del m :

Vmn = m(m − 1)( m − 2)...(m − n + 1)
La justificación de tal número es clara si consideramos que hay m
posibilidades para el primer número, entonces(m-1) posibilidades para
el segundo, (m-2) para el tercero ,..., (m-n+1) para el n-ésimo.
Permutaciones
En el caso de que se tome n=m en las variaciones anteriores, surgen las
permutaciones de melementos, ordenaciones diferentes de m elementos. Su número
es obviamente el “factorial de m” :

Pn = m(m − 1)(m − 2)....1 = m!
Combinaciones

Dado un conjunto E={a1,...., am} con m elementos, pretendemoscalcular
cuántos subconjuntos distintos podemos formar con exactamente n
elementos de E. Si consideramos las variaciones de m elementos
tomados n a n, muchas de ellas tienen los mismos elementos conel
orden cambiado. Dado que con los mismos elementos hay n!, basta con
dividir Vmn por n! para obtener el número de las llamadas combinaciones
de los m elementos tomados de n en n :
m!
m
V
m(m −1)...(m − n + 1) (m − n )!
m!
C nm =
=
=
=
=  
n!
n!
n!
n !( m − n)!  n 
n
m

es decir, el número combinatorio de m sobre n.

Permutaciones con repetición

Con k letras distintas l1, l2, ...,lk...