Números Combinatorios: Propiedades y Teoremas Esenciales

Números Combinatorios

Recordemos que el factorial de un número natural n, que denotaremos n!, es el producto de todos los números naturales menores o iguales a n:

n! = 1 · 2 · 3 · ··· · (n-1) · n

Definimos el número combinatorio C(n,m) (se lee n sobre m) como:

(Por razones técnicas, usaremos la notación C(n,m) cuando lo usemos dentro del texto).

Vamos a ver que este número es, de hecho, un número entero.

Para demostrarlo, necesitamos un cierto resultado sobre la parte entera de un número. Recordemos que la parte entera [x] de un número real x es el mayor número entero menor o igual que x, o sea que x - 1 < [x] ≤ x.

Observación: Sea n un número natural y m < n otro número natural. Entonces la parte entera de n/m, [n/m], es igual al número de naturales entre 1, 2, 3, , n que son divisibles exactamente por m.

Lema: Sea n un número natural. Entonces la máxima potencia de un número primo p que divide a n! (llamada la valoración p-ádica de n! y denotada por v_p(n!)) es igual a

vp(n!)	=		[n/pr]
r > 0

donde la suma es finita dado que si p^r >> n entonces [n/p^r] = 0, o sea cuando r > log(n)/log(p).

Demostración: Tenemos que contar la suma de las máximas potencias de p que dividen a m para todos los números m entre 1 y n. La cantidad de estos m que son divisibles por p es exactamente [n/p]. Pero entre ellos hay los números m que son divisibles por p², o sea [n/p²], que contribuyen cada uno de ellos a n! con un p de más. De la misma manera, los múltiplos de p³, de los que hay [n/p³], contribuyen cada uno de ellos con un p más. Si repetimos este argumento hasta que [n/p^r] = 0, obtenemos la fórmula buscada.

Ejemplo: v₂(100!) = [100/2] + [100/4] + [100/8] + [100/16] + [100/32] + [100/64] + [100/128] =
= [50] + [25] + [12.5] + [6.25] + [3.125] + [1.5625] + [0.78125] = 50 + 25 + 12 + 6 + 3 + 1 + 0 = 97

v₃(100!) = [100/3] + [100/9] + [100/27] + [100/81] = 33 + 11 + 3 + 1 = 48

Ejercicio: Dado un número natural n, ¿cuáles son los números primos p que dividen a n! tales que p² no divide a n!?

Se deduce fácilmente del lema que

v_p(n!) < [n/(p-1)], ya que esta última suma es a lo sumo igual a n/p + n/p² + n/p³ + ... = n/(p-1).

El resultado también demuestra que, dados n natural y m < n natural, el coeficiente binomial es un entero, ya que para todo primo p y para todo natural r se tiene

[n/p^r] >= [m/p^r] + [(n-m)/p^r] y por lo tanto la valoración p-ádica de n! es mayor o igual a la suma de las valoraciones p-ádicas de m! y de (n-m)!. Dicho de otro modo, la máxima potencia de un primo que divide a n! es mayor que la máxima potencia de este primo que divide a m!(n-m)! para cualesquiera números n y m naturales con n > m.

El número combinatorio C(n,m) cuenta la cantidad de subconjuntos de m elementos que se pueden formar de un conjunto de n elementos. Por convenio, diremos que 0! = 1 y que C(n,0) = 1.

El resultado principal de los números combinatorios es el

Teorema del Binomio de Newton:
Para todo a y b números reales (o complejos, o.....) y para todo número natural n se verifica que

n
(a+b)n	=		(	n	)	am · bn-m
m
m = 0

En particular tenemos que

n
2n	=	(1+1)n	=		(	n	)
m
m = 0

que de hecho se puede deducir de la interpretación de los números combinatorios dada anteriormente, pensando que el número total de subconjuntos que un conjunto que tiene n elementos es 2ⁿ.

Algunas propiedades importantes de los números combinatorios son:

Propiedades:
a) C(n,m) = C(n,n-m).
b) C(n,m) = (n/m) · C(n-1,m-1).
c) C(n,m) = n/(n-m) · C(n-1,m).
d) C(n,m) = C(n-1,m-1) + C(n-1,m).
e) Si n >= 2m, entonces C(n,m) > C(n,m-1), y si n <= 2m, entonces C(n,m) > C(n,m+1).

La primera propiedad es evidente de la definición. La propiedad b) se demuestra fácilmente:

De la misma manera se demuestra la propiedad c).

La propiedad d) se demuestra usando las propiedades b) y c), y nos da además la construcción de los números combinatorios a partir del triángulo de Tartaglia. Finalmente, la última propiedad se deduce de la propiedad anterior por inducción.