De mis clases: el principio de incidencia

Me gustó la idea de PZ Myers de comentar algunas de sus clases en su blog y he decidido copiársela, así que ahora inauguro la sección “De mis clases”. Este semestre estaré enseñando las clases de Matemáticas Discretas 2 (para estudiantes de segundo semestre de la Licenciatura en Matemáticas) y Análisis de Varias Variables (de cuarto semestre), y estaré comentando aquí el material visto en cualquiera de ellas. Espero poder hacerlo regularmente, lo que dependerá de los temas vistos (si no son muy técnicos) y de qué tan ocupado ande durante el semestre.

En fin, quiero empezar con un tema visto en la clase de matemáticas discretas. En esta primera semana vimos los principios fundamentales de conteo: el de la suma (el número de elementos de una unión de conjuntos disjuntos es igual a la suma del número de elementos de cada uno de ellos), el de la multiplicación (el número de elementos de un producto cartesiano de conjuntos es igual a la multiplicación del número de elementos de cada uno de ellos), el de la equivalencia (si dos conjuntos se corresponden unívocamente entonces tienen el mismo número de elementos) y, el que quiero comentar ahora, el de incidencia.

El principio de incidencia

Para enunciar el principio de incidencia requerimos de algunas definiciones. Si $A$ y $B$ son dos conjuntos finitos, una incidencia de $A$ a $B$ es una relación $R$ entre ellos, es decir, un subconjunto del producto cartesiano $A\times B$ . Así, si $(a,b)\in R$ , entonces decimos que $a$ incide en $b$ y escribimos $aRb$ .

Ahora bien, dado $a\in A$ , contamos los elementos de $B$ en donde incide $a$ y escribimos $r(a)$ . Es decir,

$r(a) = |\{b\in B: aRb\}|.$

(Hemos escrito $|S|$ para denotar el número de elementos de $S$ .) De la misma forma, para cada $b\in B$ , contamos los elementos de $A$ que inciden en $b$ , y escribimos $r'(b)$ . O sea,

$r'(b) = |\{a\in A: aRb\}|.$

Tenemos entonces el siguiente teorema.

Teorema (Principio de incidencia). Bajo las hipótesis anteriores,

$\displaystyle \sum_{a\in A}r(a) = \sum_{b\in B} r'(b).$

En otras palabras, el principio de incidencia nos afirma que, si contamos todas las incidencias posibles de $R$ , entonces da lo mismo contarlas desde $A$ o desde $B$ .

Para la demostración, escribimos $A = \{a_1, a_2, \ldots, a_p\}$ y $B = \{b_1, b_2, \ldots, b_q\}$ y consideramos la matriz $M$ con entradas $m_{ij}$ dadas por

$\displaystyle m_{ij} = \begin{cases}1 & a_i R b_j \\ 0 & a_i \!\not{\!\!R} b_j.\end{cases}$

En otras palabras, cada $m_{ij}$ indica si $a_i$ incide en $b_j$ o no. La matriz $M$ es llamada la matriz de incidencia.

Una matriz de incidencia típica puede verse como

$\begin{pmatrix}1&1&0&1\\ 0&0&1&1\\1&0&1&1\end{pmatrix}$ ,

la cual indica que $a_1$ incide en $b_1, b_2$ y $b_4$ , mientras que no incide en $b_3$ ; $a_2$ incide en $b_3$ y $b_4$ , mientras que no lo hace en $b_1$ y $b_2$ ; y que $a_3$ incide en $b_1, b_3$ y $b_4$ , y no en $b_2$ .

En este ejemplo tenemos entonces que

$r(a_1) = 3, r(a_2) = 2$ y $r(a_3) = 3$ ,

mientras que

$r'(b_1) = 2, r'(b_2)=1, r'(b_3)=2$ y $r'(b_4)=3$ .

Observamos que la sumas de los números anteriores son iguales: $3+2+3=2+1+2+3=8.$

Este ejemplo nos muestra qué significan cada uno de los números $r(a)$ , $r'(b)$ y la suma de ellos: el número de 1 en cada renglón, el número de 1 en cada columna, y el total de 1 en cada matriz. Así que no es sorpresa que las sumas anteriores sean iguales: ambas cuentas el número de 1 totales en la matriz.

En general, lo demostramos usando las propiedades conmutativa y asociativa de la suma. Tenemos que

$\displaystyle \sum_{a\in A}r(a) = \sum_{i=1}^p r(a_i) = \sum_{i=1}^p \Big( \sum_{j=1}^q m_{ij}\Big) = \sum_{j=1}^q\Big( \sum_{i=1}^p m_{ij}\Big) = \sum_{j=1}^q r'(b_j) = \sum_{b\in B} r'(b).$

$\Box$

Un ejemplo: el promedio de los divisores de un número

El principio de incidencia puede parecer abstracto y muy rebuscado, pero es muy útil a la hora de calcular sumas de conteo “dobles”. Como ejemplo, consideremos la siguiente pregunta.

Sea $\tau(n)$ el número de divisores del entero $n$ . ¿Cuál es el promedio de la función $\tau$ en los primeros $N$ enteros?

En otras palabras, para un entero positivo $N$ , ¿podemos describir el comportamiento de

$\dfrac{\tau(1) +\tau(2) + \ldots + \tau(N)}{N}$ ?

El único divisor de 1 es 1, así que $\tau(1)=1$ ; los divisores de 2 son 1 y 2, así $\tau(2)=2$ ; similarmente $\tau(3)=2$ ; $\tau(4) = 3$ porque los divisores de 4 son 1, 2 y 4; $\tau(5)=2$ ; etc. Otros ejemplos son

$\tau(6)=4, \tau(7)=2, \tau(8)=4, \tau(9)=3, \tau(10)=4, \tau(11)=2, \tau(12)=6.$

La función $\tau$ no parece cumplir ningún patrón (aunque es posible calcularla dada la factorización prima de cada número), por lo que el problema de calcular su promedio se ve irresoluble.

Sin embargo, aquí es donde el principio de incidencia entra en acción. Sean $d,n\in\{1, 2, \ldots, N\}$ , y decimos que $d|n$ si $d$ es divisor de $n$ . Entonces vemos que, para cada $d=1, 2, \ldots, N$ ,