| José Rosales O | Pedro Díaz N.  | Revista Digital Matemática, Educación e Internet |

 

Sobre una fórmula en Combinatoria.

José Rosales Ortega
Escuela de Matemática
Instituto Tecnológico de Costa Rica

 

Introducción

La idea del siguiente arículo surgió al leer el libro [2]. Allí se exponen los rudimentos de la teoría de combinatoria que se utilizan en la competencias de Olimpíadas Matemáticas en México.

Nos proponemos mostrar las siguiente fórmula combinatoria:

Si $m,n,r \in \ N$ son tales que $m,n \geq r$,entonces

$$\displaystyle { m+n \choose r }\;=\; {m \choose 0}{n \choose ... ...se 1}{n \choose r-1}\;+\;\ldots \;+\;{m \choose r}{n \choose 0}$$

 

Esta fórmula es muy famosa y se conoce como la fórmula de Vandermonde. De hecho el lector puede consultar [1] para obtener una demostración usando métodos totalmente distintos al usado aquí. Los métodos que utiliza el autor para demostrar la fórmula anterior se basan en la manipulación de identidades combinatorias y de las llamadas funciones generadoras.

Para lograr nuestro objetivo nos valdremos de un método muy sencillo pero no muy conocido: el método de contar el número de rutas más cortas entre dos puntos del plano.

 

Definición 1   Un punto $(a,b)$ en el plano cartesiano se llama punto reticular si tanto $a$ como $b$ son números enteros.

Los puntos reticulares se obtienen de una manera muy fácil. En el plano cartesiano considere $n$ puntos en el semieje positivo de las $x$, y $m$ puntos en el semieje positivo de las $y$. Si por cada uno de los $n$ puntos trazamos una línea paralela al semieje de las $y$ y otra paralela al eje de las $x$ por cada uno de los $m$ puntos, entonces obtenemos una cuadrícula con $mn$ rectángulos.

Recordemos que una sucesión de números $a_1,\cdots,a_n$ se llama sucesión binaria si cada $a_i$ es 0 ó 1, para cada $i=1,\cdots n$. La longitud de una sucesión binaria se define como el número de términos de la sucesión. Por ejemplo, en la sucesión binaria 1,1,0,0,1,0,1 la longitud es 7. Queremos responder a la siguiente pregunta: cuántas sucesiones binarias hay de longitud $n$? Para fijar ideas veamos cuántas sucesiones binarias hay de longitud 7. La respuesta es muy simple, existen $2^7$ sucesiones binarias de longitud 7. Para ver esto nótese que para elegir el primer elemento de nuestra sucesión tenemos dos posibilidade 0 ó 1, para el segundo las mismas dos posibilidades y así sucesivamente, para en resumen tener $2^7$ posibilidades. En general, el número de sucesiones binarias de longitud $n$ es dado por $2^n$.

Ahora nos proponemos responder una pregunta un poco más difícil: cuántas sucesiones binarias de longitud $n$, que consten de $r$-ceros y $s$-unos, existen, con $n=r+s$? Una vez más, para fijar ideas consideremos sucesiones binarias de longitud 7 y que consten de cuatro ceros y tres unos, por ejemplo, la sucesión 1,0,0,0,1,0,1. Nótese que para formar una tal sucesión primero elegimos

Consideremos $(m+1)\times(n+1)$ puntos reticulares como en la figura anterior.

La pregunta que nos hacemos es cuántas rutas más cortas hay desde $(0,0)$ hasta $(m,n)$? Una tal ruta se muestra en la figura anterior. Recordemos que tales rutas se pueden pensar como sucesiones binarias finitas. Cada una de estas sucesiones binarias consta de $n$ ceros y de $m$ unos, si identificamos cada segmento vertical con un 0 y cada segmento horizontal con un 1. Luego el problema de encontrar el número de rutas más cortas entre $(0,0)$ y $(m,n)$ se traduce en encontrar el número de sucesiones binarias de longitud $m+n$ con $n$ ceros y $m$ unos. Usando los mismos argumentos del inicio de este artículo encontramos que

$$\mbox{N\'umero de rutas m\'as cortas de $(0,0)$\ a $(m,n) $}\; =\; {m+n \choose n}.$$

 

La siguiente observación será fundamental para la demostración de la primera fórmula que nos propusimos deducir al inicio del artículo. Para ello nos basaremos en la siguiente figura:

Supongamos que las coordenadas del punto $A$ son $(x,y)$ y las de $B$ son $(x+1,y)$. Ahora nos preguntamos por el número de rutas más cortas desde $(0,0)$ hasta $(m,n)$ y que pasen por el punto $A$. Para dar respuesta a esta pregunta procederemos de la siguiente manera. Primero encotraremos el número de rutas más cortas desde $(0,0)$ hasta $A$ y luego el número de rutas más cortas desde $A$ hasta $(m,n)$. El resultado será entonces el producto de éstos dos. El primero de estos números es dado por ${x+y \choose x}$ y el segundo está dado por ${m-x+n-y \choose m-x}$. Por lo tanto, el número de rutas más cortas de $(0,0)$ a $(m,n)$ y que pasan por $A$ es igual a

$${x+y \choose x}{m-x+n-y \choose m-x}.$$

 

Demostremos ahora la siguiente fórmula:

 

$$\displaystyle { m+n \choose r }\;=\; {m \choose 0}{n \choose ... ...e 1}{n \choose r-1}\;+\;\ldots \;+\;{m \choose r}{n \choose 0},$$

 

donde $m,n,r \in \ N$ son tales que $m,n \geq r$.

Consideremos la siguiente figura:

Nótese que el número de rutas más cortas entre $(0,0)$ y $(m+n-r,r)$ es dado por

$${m+n-r+r \choose r}\;=\;{m+n \choose r}.$$

 

Lo anterior no es nada más y nada menos que el lado izquierdo de la fórmula anterior. Para terminar vamos a calcular de nuevo el número de rutas más cortas entre $(0,0)$ y $(m+n-r,r)$, pero en una forma diferente.

Consideremos el segmento de línea uniendo los puntos $(m,0), (m-1,1),\ldots,(m-r,r)$, tal y como se indica en la figura anterior. Notemos que cada ruta más corta entre $(0,0)$ y $(m+n-r,r)$ pasa sólo por uno de estos puntos. El número de rutas más cortas que pasan por el punto $(m-i,i)$ es dado por

 

$${m+i-i\choose i}{(m+n-r-m+i)+(r-i)\choose r-i}\;=\; {m\choose i}{n\choose r-i},$$

 

para cada $i=0,\ldots,r$.

Luego el número total de rutas entre $(0,0)$ y $(m+n-r,r)$ será la suma del número de rutas más cortas que pasan por el punto $(m-i,i)$, para $i=0,1,\ldots,r$, y tal suma es

 

$${m\choose 0}{n\choose r-0}\;+\;{m\choose 1}{n\choose r-1}\;+\;\cdots\;+\;{m\choose r}{n\choose r-r}.$$

 

En resumen, el número de rutas más cortas entre $(0,0)$ y $(m+n-r,r)$ es dado por

$${m \choose 0}{n \choose r}\;+\;{m \choose 1}{n \choose r-1}\;+\;\ldots \;+\;{m \choose r}{n \choose 0},$$

 

que es el lado derecho de la fórmula a demostrar.

 

Bibliografía

1

Daniel I. A. Cohen , Basic Techniques of Combinatorial Theory,John Wiley & Sons, Canada 1978.

2

María Luisa Pérez Seguí , Combinatoria, Cuadernos de Olimpiadas Matemáticas, México, 2000.

This document was generated using the LaTeX2HTML translator Version 99.2beta6 (1.42)
Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

 

 

Revista digital Matemática, Educación e Internet.
Derechos Reservados