Docente

UNA PRIMERA LECCIÓN DE COMBINATORIA
Francisco Bellot Rosado
Seminario de Problemas, Valladolid, 16-17 de octubre de 2012

Algunas formas de explicar cuestiones de Matemáticas, expuestas por
buenos profesores, te impresionan de tal forma que, desde que las
ves, las utilizas de manera sistemática. Eso me ocurrió en octubre de
1964, cuando tuve el privilegio de seguir, siendo su alumnobecario,
el desarrollo de la Combinatoria presentado en el Instituto
“Cervantes” por el Profesor D. José Ramón Pascual Ibarra.
Para empezar, un problema…

La figura sobre estas líneas representa idealizado el plano de una
ciudad, con manzanas de casas exactamente iguales. Se pretende ir
del vértice inferior izquierdo al superior derecho, por las calles, y de
manera que el camino recorrido tengalongitud mínima. ¿Cuántos
caminos de estas características hay?
(La exigencia de ser de longitud mínima implica en este caso que
solamente se pueda ir, horizontalmente, de izquierda a derecha; y
verticalmente, de abajo a arriba).
Se observa fácilmente que los caminos posibles tienen todos 4 tramos
verticales y 9 horizontales. Pero llegar a saber cuántos son no parece
demasiado sencillo (sino se conoce el problema, naturalmente).
¿Serán más o menos de 100 los caminos? (Podemos hacer una
votación…)
Al cabo de unos momentos, se puede sugerir a los alumnos
que sigan el consejo de Pólya: Si un problema plantea una

situación muy complicada, estúdiese el mismo problema en un
contexto más sencillo…
La figura siguiente está tomada de un libro de Pólya, Notes on
IntroductoryCombinatorics.

Por conveniencia hemos dispuesto la figura con otra orientación, y
ahora se trata de hallar el número de caminos que van del vértice
superior al inferior del cuadrado.
¿Cuántos caminos llevan al vértice marcado con un asterisco? ¿Y con
dos?
Compliquemos la figura un poco más:

Hasta que, finalmente, la completamos :

Si aplicamos el procedimiento descrito al problemaoriginal,
obtendríamos 715 caminos: demasiados para dibujarlos todos y
contarlos después.
Este primer ejemplo pertenece a lo que se llama Combinatoria
enumerativa, o si se quiere, al Arte de contar sin enumerar. A
continuación trataremos de profundizar un poco más en lo que hay
detrás del problema.
Nomenclatura
Imaginemos, como se indica en la figura siguiente, que se tiene de
nuevo unrectángulo en su posición normal, con caminos que constan
de n segmentos, de los que k de ellos van hacia arriba:

Sería importante disponer de una fórmula que permitiera calcular el
número de caminos, en función de k y de n, para no tener que repetir
el procedimiento pedestre, pero eficaz, empleado para el cálculo en
los casos particulares. Por lo de pronto vamos a utilizar el símbolo
siguientepara representar ese número:
n n
C =  .
k k 

La C no es exactamente por “caminos”, pero viene bien en esta
ocasión. El símbolo de la derecha lo leemos como “n sobre k”.

Es evidente, según la figura anterior, que el número de caminos
mínimos para ir de A a B es la suma de los que van desde A a B1 más
los que van desde A a B2.
Con la notación que hemos elegido, hemos llegado a
 n  n − 1  n − 1 
= 
 
+
.
 k   k   k − 1
Esta igualdad es lo que se llama una fórmula de recurrencia; para
calcular el valor del primer miembro necesitamos conocer todos los
valores anteriores (es lo que hemos hecho antes para calcular el
número de caminos).
Si k=0, el rectángulo se reduce a un segmento horizontal de longitud
n. Para ir de un extremo a otro solamente hayun camino, lo cual se
puede expresar mediante
n
  = 1.
0

Si el segmento fuera vertical con k=n también tendríamos un único
camino, de modo que
n
  = 1.
n
Estas dos son las condiciones iniciales de la recurrencia.
Por otro lado, con la interpretación de los caminos que estamos
haciendo, se ve que también se verifica
n  n 
 =
,
k  n−k 
porque eso es...