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:
 

C(n,m)=(	n	)	=	n!
	m			m!(n-m)!

(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 numero 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, ¿cuales 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 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:

C(n,m)=(	n	)	=	n!	=	n·(n-1)!	=	n	·	(n-1)!	=(n/m)·C(n-1,m-1)
	m			m!(n-m)!		m·(m-1)!(n-m)!		m		(m-1)!((n-1)-(m-1))!

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.
 
 

Volver al postulado de Bertrand