PLAN DE CLASE
LOS NUMEROS
COMBINATORIOS
Elaborado por
Mximo Miranda Vera
NUMEROS COMBINATORIOS
Se recuerda que el factorial del nmero
natural n es el producto de los nmeros
naturales de 1 a n, esto es,
n!=12 3 n
y que por convenio
0!=1
NUMEROS COMBINATORIOS
Se llama permutacin de n elementos
a
1
, a
2
, a
3
, , a
n
a cualquier ordenacin de los mismos. Por
ejemplo: Las permutaciones de las 3 letras
pqr son pqr, qrp, rpq, qpr,rqp,prq.
Teorema:El nmero de permutaciones de n
elementos vale n!
En el ejemplo 3!=6
NUMEROS COMBINATORIOS
En lugar de ordenaciones de los n elementos
podramos pensar en ordenaciones de k
elementos extrados de los n dados. Por
ejemplo: las permutaciones de las tres letras
pqr tomadas de dos en dos cada vez son
pq, pr, qr, qp, rp, rq
Teorema: El nmero de permutaciones de n
elementos tomados de k en k cada vez vale
n!/(n-k)!.
NUMEROS COMBINATORIOS
En nuestro ejemplo 3!/(3-2)!=6/1=6
Nota: Si en las permutaciones de n
elementos tomados de k en k cada vez se
admitiera repeticiones el nmero de tales
permutaciones sera n
k
En nuestro ejemplo 3
2
=9:
pp, pq, pr, qp, qq, qr, rp, rq, rr
NUMEROS COMBINATORIOS
Se llama combinacin a una permutacin en
la que el orden no tiene relevancia y slo
qu elementos la forman
Por ejemplo: Slo hay una combinacin de
las tres letras pqr, precisamente pqr. Las
combinaciones de pqr tomadas de dos en
dos son pq, pr, qr y tomadas de uno en uno
p, q, r
NUMEROS COMBINATORIOS
Teorema: El nmero de combinaciones de
n elementos tomados de k en k viene dado
por la expresin
El primer miembro de la expresin es la
notacin del nmero combinatorio n sobre k
definido por el segundo miembro.
! )! (
!
k k n
n
k
n
=
|
|
.
|
\
|
NUMEROS COMBINATORIOS
Nota: Si en las combinaciones de n
elementos tomados de k en k cada vez se
admiten repeticiones, el nmero de tales
combinaciones viene dado por
|
|
.
|
\
|
+
k
1 k n
NUMEROS COMBINATORIOS
Ejemplo: El nmero de combinaciones de
las tres letras pqr tomadas de dos en dos
cada vez es
y si se admite repeticiones de letras
3
2 . 1
6
! 2 )! 2 3 (
! 3
2
3
= =
=
|
|
.
|
\
|
6 ...
2
4
2
1 2 3
= =
|
|
.
|
\
|
=
|
|
.
|
\
|
+
NUMEROS COMBINATORIOS
El nmero combinatorio
se puede calcular tambin de la forma
! )! (
!
k k n
n
k
n
=
|
|
.
|
\
|
k
k n n n n
k
n
3 2 1
) 1 ( ) 2 )( 1 (
+
=
|
|
.
|
\
|
NUMEROS COMBINATORIOS
Se justifica lo anterior mediante
| | | |
| |
1 2 3
) 1 ( ) 2 )( 1 (
) 1 2 3 ( 1 2 3 ) 1 )( (
1 2 3 ) 1 )( ( ) 1 ( ) 2 )( 1 (
! )! (
!
+
=
+
=
=
|
|
.
|
\
|
k
k n n n n
k k n k n
k n k n k n n n n
k k n
n
k
n
NUMEROS COMBINATORIOS
Se tienen las siguientes propiedades:
|
|
.
|
\
|
+
|
|
.
|
\
|
=
|
|
.
|
\
|
+
|
|
.
|
\
|
=
|
|
.
|
\
|
=
|
|
.
|
\
|
=
|
|
.
|
\
|
1 k
n
k
n
k
1 n
) 4
k
n
k - n
n
) 3
n
1
n
) 2 1
0
n
) 1
NUMEROS COMBINATORIOS
La ltima propiedad permite obtener los
nmeros combinatorios de forma recursiva,
dando origen al llamado tringulo de
Pascal o de Tartaglia:
1
5 10 10 5 1 5
1 4 6 4 1 4
1 3 3 1 3
1 2 1 2
1 1 1
1 0
n
NUMEROS COMBINATORIOS
Los nmeros combinatorios aparecen como
coeficientes del binomio de Newton:
|
|
.
|
\
|
=
=
|
|
.
|
\
|
+ +
|
|
.
|
\
|
+
|
|
.
|
\
|
+
|
|
.
|
\
|
= +
n
k
k k n
n n n n n
b a
k
n
b
n
n
b a
n
b a
n
a
n
b a
0
2 2 1
...
2 1 0
) (
NUMEROS COMBINATORIOS
Utilizando la anterior expresin se puede
probar inmediatamente:
=
=
=
|
|
.
|
\
|
=
|
|
.
|
\
|
n
0 k
k
n
0 k
n
0
k
n
) 1 ( ) 2
2
k
n
) 1
