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í:

Anuncios

Responder Cancelar respuesta

Introduce aquí tu comentario...

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

Correo electrónico (necesario) (La dirección no se hará pública)

Nombre (necesario)

Web

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

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

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

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

Cancelar

Conectando a %s

	Hidden Figures recib… en Hidden figures
	ricardos en Teorema de la semana, de mis c…
	Jesús en Teorema de la semana, de mis c…
	Edición 7.8 Carnaval… en Resumen del Carnaval de matemá…
	Edición 7.8 Carnaval… en #CarnaMatOctubre: resumen fina…

El principio de incidencia

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

Sharéalo:

Me gusta:

Relacionado

Responder Cancelar respuesta