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 y
son dos conjuntos finitos, una incidencia de
a
es una relación
entre ellos, es decir, un subconjunto del producto cartesiano
. Así, si
, entonces decimos que
incide en
y escribimos
.
Ahora bien, dado , contamos los elementos de
en donde incide
y escribimos
. Es decir,
(Hemos escrito para denotar el número de elementos de
.) De la misma forma, para cada
, contamos los elementos de
que inciden en
, y escribimos
. O sea,
Tenemos entonces el siguiente teorema.
Teorema (Principio de incidencia). Bajo las hipótesis anteriores,
En otras palabras, el principio de incidencia nos afirma que, si contamos todas las incidencias posibles de , entonces da lo mismo contarlas desde
o desde
.
Para la demostración, escribimos y
y consideramos la matriz
con entradas
dadas por
En otras palabras, cada indica si
incide en
o no. La matriz
es llamada la matriz de incidencia.
Una matriz de incidencia típica puede verse como
,
la cual indica que incide en
y
, mientras que no incide en
;
incide en
y
, mientras que no lo hace en
y
; y que
incide en
y
, y no en
.
En este ejemplo tenemos entonces que
y
,
mientras que
y
.
Observamos que la sumas de los números anteriores son iguales:
Este ejemplo nos muestra qué significan cada uno de los números ,
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
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
el número de divisores del entero
. ¿Cuál es el promedio de la función
en los primeros
enteros?
En otras palabras, para un entero positivo , ¿podemos describir el comportamiento de
?
El único divisor de 1 es 1, así que ; los divisores de 2 son 1 y 2, así
; similarmente
;
porque los divisores de 4 son 1, 2 y 4;
; etc. Otros ejemplos son
La función 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 , y decimos que
si
es divisor de
. Entonces vemos que, para cada
,
es el número de múltiplos de en
. De la misma forma
es el número de divisores de , o sea, nuestra función
.
podrá parecer incalculable, pero
no lo es:
,
donde es el mayor entero menor o igual a
. Entonces
,
donde es un número de valor absoluto menor a 1. Por el principio de incidencia, tenemos entonces
,
donde es, en valor absoluto, a los más
. Por lo tanto, el promedio de
de
a
es
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:
,
donde el error de esta aproximación es, también, menor a 1. Así que tenemos que
Aún cuando la función 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í: