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,

r(a) = \big|\{n:d|n\}\big|

es el número de múltiplos de d en \{1, 2, \ldots, N\}. De la misma forma

r'(n)=\big|\{d:d|n\}\big|

es el número de divisores de n, o sea, nuestra función \tau(n). \tau(n) podrá parecer incalculable, pero r(d) no lo es:

r(d) = \Big\lfloor \dfrac{N}{d} \Big\rfloor,

donde \lfloor x \rfloor es el mayor entero menor o igual a x. Entonces

r(d) = \dfrac{N}{d} + error,

donde error es un número de valor absoluto menor a 1. Por el principio de incidencia, tenemos entonces

\displaystyle \sum_{n=1}^N\tau(n) = \sum_{d=1}^Nr(d) = N\sum_{d=1}^N\dfrac{1}{d} + Error,

donde Error es, en valor absoluto, a los más N. Por lo tanto, el promedio de \tau de 1 a N es

\displaystyle \frac{1}{N}\sum_{n=1}^N\tau(n) \approx \sum_{d=1}^N\frac{1}{d},

donde la diferencia entre uno y otro lado de la ecuación es, a lo más, 1.

Más aún, ya sabemos cómo aproximar el lado derecho de la última ecuación:

\displaystyle \sum_{d=1}^N\frac{1}{d} \approx \log N,

donde el error de esta aproximación es, también, menor a 1. Así que tenemos que

\displaystyle \frac{\tau(1) + \tau(2) + \ldots + \tau(N)}{N} \approx \log N.

Aún cuando la función \tau es muy irregular, su promedio se comporta de manera bonita: crece como el logaritmo natural.

Todo gracias a que podemos sumar los elementos de un matriz sumando por renglones o por columnas.


Los programas de mis materias de este semestre pueden ser vistos aquí:

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s