Aprendiendo a Contar II

Este post estará relacionado con el anterior, donde vimos algunas técnicas de conteo básicas. Hoy veremos cómo podemos ampliar un poco más nuestros conocimientos mediante nuevas técnicas.

EL COMPLEMENTARIO

Vamos a suponer que tenemos un conjunto, $X,$ que conocemos y del que conocemos su número de elementos, su cardinal. Ahora queremos saber cuántos elementos hay en un subconjunto $A\subset X.$ Una de las formas de hacerlo es mediante el conjunto complementario de $A,$ el conjunto $X\setminus A$ formado por todos los elementos de $X$ que no están en $A.$

$\text{Lema (Cardinal del Complementario).}$ Sean $X$ y $A$ dos conjuntos finitos tales que $A\subset X.$ Entonces $\left| A \right|=\left| X \right| - \left| X\setminus A \right|.$

La demostración es fácil. Por definición, $A\cap (X\setminus A)=\emptyset,$ y por tanto $X=A\uplus (X\setminus A)$ y la unión es disjunta, luego tomando cardinales obtenemos $\left| X \right|=\left| A \right| + \left| X\setminus A \right|$ y reordenando los sumandos de la ecuación obtenemos el resultado deseado. La razón por la que funciona el tomar una unión disjunta la veremos más adelante.


Esta técnica de conteo es muy útil en situaciones en las que lo que se nos pide contar se puede enmarcar dentro de un conjunto más grande que conocemos. Veamos un ejemplo:

En el post anterior vimos cómo calcular el número de divisores de $49.000.$ Ahora vamos a calcular la cantidad de números menores o iguales que él y que no lo dividen. Si nombramos $X=\left\lbrace n\in \mathbb{N}: \ n \leq 49.000 \right\rbrace$ entonces podemos considerar $D=\left\lbrace n\in \mathbb{N}: \ n | 49.000 \right\rbrace$ el conjunto de divisores de $49.000$ ("|" es una notación: $n$ divide a $m$ se escribe $n|m$). Desde luego $D\subset X$ puesto que cualquier divisor de un número es menor o igual que dicho número. Llegados a este punto no es difícil darse cuenta de que el conjunto de números que no dividen a $49.000$ es justo el complementario en $X$ de $D,$ y por tanto, al saber (por el anterior post) que $D$ tiene $48$ elementos, la respuesta al problema debe ser $49.000-48=48952.$


REGLA DE LA SUMA

A lo largo del post anterior y en el anterior apartado de éste hemos estado utilizando la regla de la suma casi constantemente y a la hora de demostrar resultados. Es muy intuitiva y natural, y  establece cómo sumar cardinales de conjuntos disjuntos:

$\text{Lema (Regla de la Suma).}$ Sea $A$ un conjunto finito y $A_1, A_2, \ ..., A_k$ una colección de subconjuntos de $A$ que cumple:$$A=\bigcup_{i=1}^k A_i, \ \ \ A_i\cap A_j = \emptyset \ \ \text{si}\ \ i\neq j$$entonces$$\left| A \right| = \sum_{i=1}^k \left| A_i \right|.$$

Haremos la demostración por el método de inducción.
  1. Si $A$ es un conjunto finito con $A=A_1 \cup A_2$ y además $A_1 \cap A_2=\emptyset$ entonces $A_1$ es finito y tiene $n_1$ elementos y $A_2$ también y tiene $n_2$ elementos, siendo los elementos de $A_1$ distintos de los de $A_2.$ Por tanto podemos describir $A$ de la forma $$A=\left\lbrace a^1_1, \ ..., a^1_{n_1}, a^2_1, \ ..., a^2_{n_2}: a^i_j \in A_i \right\rbrace.$$Ahora para ser totalmente precisos vamos a querer demostrar que si a un conjunto de $n$ elementos se le añade otro elemento más y distinto de los anteriores entonces el cardinal del conjunto aumenta en una unidad, porque si lo demostramos podemos aplicarlo $n_2$ veces en nuestra demostración para obtener el resultado que deseamos.

    Bien, si nuestro conjunto tiene $n$ elementos entonces (como ya hemos visto antes) está en biyección con $I_n.$ Si añadimos un elemento nuevo y distinto de todos los anteriores entonces podemos establecer una biyección con $I_{n+1}$ de manera que el nuevo conjunto tendrá $n+1$ elementos.

    Ahora volviendo a nuestra demostración y aplicando este resultado $n_2$ veces a $A_1$ para obtener el conjunto $A$ se llega a que $|A|=n_1 + n_2$ que es precisamente lo que queríamos ver.

  2. Supongamos que el resultado se cumple para $n$ conjuntos disjuntos $(A_i,\ \ i=1,\ ...,n).$ Consideremos $B=\bigcup_{i=1}^n A_i.$ Ahora queremos comprobar que si $A_{n+1}$ es un conjunto tal que $A_{n+1}\cap A_i= \emptyset$ para todo $i=1,\ ..., n,$ entonces $|B\cup A| = |B|+|A|.$ Sin embargo si la intersección de $A_{n+1}$ con el resto de los $A_i$ es vacía, entonces la intersección de $A_{n+1}$ con $B$ es vacía y estamos en las condiciones del ejemplo para $2$ conjuntos, que es precisamente el primer paso de la inducción y eso ya lo hemos demostrado. Por tanto ya hemos terminado.


Vamos a ver una aplicación de esta regla que es muy interesante:

Nos planteamos el problema de contar el total de listas sin repetición que podemos hacer con $n$ elementos, por ejemplo $\left\lbrace 1, 2, \ ..., n \right\rbrace.$ Es decir, listas con una longitud que puede ser $1$ pero también puede ser $2$ ó $3$ ó $n$ o cualquier número natural menor o igual que $n,$ el total de listas posibles. Pues bien, podemos considerar los conjuntos $A_j$ para cada $j=1, \ ...,n$ tales que $a\in A_j$ si $a_j$ es una lista de longitud $j$ con $n$ posibles elementos y sin repetición. Es fácil ver que como una lista de longitud $j$ no puede tener longitud $l\neq j$ entonces los $A_j$ son todos disjuntos dos a dos y por tanto podemos aplicar la regla de la suma. Además los cardinales de $A_j$ los conocemos puesto que los hemos calculado en el post anterior. Por lo tanto:$$\left\lbrace \text{Total de listas} \right \rbrace=\sum_{j=1}^n |A_j| = \sum_{j=1}^n \frac{n!}{(n-j)!}$$y haciendo un inocente cambio en el índice de sumación: $k=n-j$ obtenemos que esto es igual a$$ n!\sum_{k=0}^{n-1} \frac{1}{k!}.$$Es muy curioso que hayamos llegado a este resultado, pues $\sum_{k=0}^{n-1} \frac{1}{k!} \longrightarrow e$ cuando $n\longrightarrow \infty$ y de hecho si $n$ es suficientemente grande lo que nos está indicando este resultado es que el número total de listas de $n$ símbolos sin repetición que podemos hacer es aproximadamente $e \cdot n!.$


PRINCIPIO DE INCLUSIÓN-EXCLUSIÓN

Para el lector más rápido quizá haya un problema con la situación que hemos afrontado antes. Es muy bonita, ya que no es especialmente fácil encontrarnos con que los conjuntos en los que hemos descompuesto nuestro conjunto grande son disjuntos dos a dos. Es decir, en la mayoría de los casos no vamos a poder encontrar una partición de nuestro conjunto de forma que podamos calcular su cardinal fácilmente. Muy a menudo vamos a tener conjuntos con intersecciones no vacías, y por ello nos gustaría encontrar una regla que nos garantice que aún así podemos contarlos. Esto se conoce como el Principio de Inclusión-Exclusión.

$\text{Teorema (PIE).}$ Sean $A_1, \ ..., A_n$ una colección de conjuntos finitos. Entonces:$$\left| \bigcup_{k=1}^n A_n \right|= \sum_{i=1}^n |A_i| -  \sum_{1\leq i<j\leq n} |A_i\cap A_j| + \sum_{1\leq i<j<k\leq n} |A_i\cap A_j \cap A_k| - \ ...$$La expresión es enorme, casi abrumadora y en general un rollo de calcular. La idea es que por cada vez que se añade el cardinal de un conjunto se están añadiendo todas las intersecciones con el resto de conjuntos y por tanto hay que quitarlas tantas veces como se han añadido de más. Es fácil visualizarlo mediante diagramas de Venn. Veamos la fórmula para el caso $n=2:$ $$ \left| A \cup B \right| = \left| A \right| + \left| B \right| - \left| A \cap AB \right|.$$


No es difícil darse cuenta de que al añadir $A$ y al añadir $B$ estamos añadiendo $A\cap B$ dos veces, luego para equilibrar y no contar de más tendremos que quitarlo una vez. Por eso aparece ese término negativo en la fórmula.

Comentarios

Publicar un comentario

Frecuentes

Aplicaciones Lineales, Isomorfismos y Cambio de Base

Recapitulemos un poco antes de comenzar: hemos visto que todo espacio vectorial tiene una base , e.d. un conjunto de vectores linealmente independientes que lo generan. También hemos visto que podemos representar cada vector del espacio mediante sus coordenadas respecto de una base , y que estas pueden ser distintas en función de la base que tomemos. Habíamos dejado planteadas algunas cuestiones sin resolver, como cómo operar con coordenadas y cómo hacer el cambio de coordenadas en función de qué base tomemos. En el post de hoy vamos a resolver estas cuestiones, para lo cual hablaremos de las aplicaciones lineales y de la matriz de cambio de base. APLICACIONES LINEALES En matemáticas, una vez definida una estructura, lo normal es preguntarse cómo pueden ser las aplicaciones entre ese tipo de estructura. El ejemplo que conocemos por ahora es el de aplicaciones entre conjuntos . Las aplicaciones entre dos conjuntos que respetan la estructura de con...
ENTRAR

Recurrencias Lineales no Homogéneas

En el anterior post vimos cómo resolver recurrencias lineales de la forma: $$\begin{align} a_n=B_1 a_{n-1} + \ ... \ + B_{k}a_{n-k}\end{align} $$con $B_j \in \mathbb{R}$ y $B_k \neq 0.$ Es decir, vimos cómo es posible dar una fórmula explícita para $a_n$ que únicamente dependa de $n.$ Estas son las llamadas recurrencias lineales homogéneas. En este post vamos a intentar generalizar y dar una solución explícita para recurrencias que tienen la forma: $$ \begin{align} a_n=B_1 a_{n-1} + \ ... \ + B_{k}a_{n-k} + f(n)\end{align} $$donde $f$ es una función de $\mathbb{N}$ a $\mathbb{R}$ no nula (el caso en el que $f \equiv 0$ es el caso homogéneo que hemos tratado en el anterior post). Estas últimas se conocen como recurrencias lineales no homogéneas. Además en ambos casos los coeficientes $B_j\in \mathbb{R}$ son constantes. Si fueran funciones que dependen de $n$ el tema se complicaría más y no vamos a tratar esos casos por ahora. Por los mismos motivos que en el post anterior, vamos a...
ENTRAR

Relaciones de Orden y de Equivalencia

Vamos a introducir el concepto de lo que es una relación de equivalencia y después veremos lo que es una relación de orden. (La palabra $\text{Def}$ introducirá siempre una nueva definición y $\text{Obs}$ denotará una observación). El post de hoy es un poco más técnico, pero no es difícil de comprender, sobre todo si te animas a coger un papel y un lápiz y comprobar que lo que vamos a ir haciendo tiene sentido. Este tipo de herramientas son de las más básicas en matemáticas y por eso no conviene reducirlas a meros comentarios, puesto que entonces muchos desarrollos carecerían de sentido. Así que no te asustes, y pongámonos manos a la obra. RELACIONES DE EQUIVALENCIA $\text{Def.}$ Dado un conjunto , $X$, una relación de equivalencia, $R$, es una relación binaria en $X$ (relaciona un par de elementos de $X$, digamos $x$ e $y,$ y se lee $xRy:$ $x$ está relacionado con $y$), que cumple las siguientes tres propiedades: Reflexiva:  todo elemento de $X$ está relacionado consigo m...
ENTRAR

El Teorema del Sándwich

Imagen
En el post anterior vimos lo que eran las sucesiones de números reales, los límites de estas y dejamos planteadas algunas preguntas que iremos respondiendo a lo largo de los siguientes posts. Lo que veremos hoy son varios resultados sobre sucesiones de números reales que pueden resultar interesantes e intuitivos y distintos ejemplos de cómo calcular límites de sucesiones utilizando estos resultados. PROPIEDADES DE LOS LÍMITES En el anterior post terminamos hablando de cómo los límites se comportan bien con las operaciones que conocemos en $\mathbb{R},$ pero no demostramos el resultado. Lo que haremos a continuación es investigar un poco una idea que nos va a ayudar a demostrarlo. Vamos a suponer que tenemos dos sucesiones. Una de ellas es constante: $\left\lbrace c_n \right\rbrace_{n=1} ^ \infty, \ \ c_n = c \ \ \forall n \in \mathbb{N}$ para cierto $0<c\in \mathbb{R}$ un número real fijo, y la otra sucesión converge a $0:$  $\left\lbrace a_n \right\rbrace_{n=1}^...
ENTRAR

Aplicaciones y Cardinales

Imagen
APLICACIONES Y FUNCIONES Si acabas de llegar al blog, esta entrada está muy relacionada con la anterior: conjuntos , de modo que leerla te ayudaría a comprender lo que vamos a discutir a continuación. En matemáticas, dados dos conjuntos (digamos $X$ e $Y$), una aplicación de $X$ en $Y$ es una regla que a cada elemento de $X$ le asigna un elemento de $Y$. Digamos que nuestra aplicación se llama $f$, entonces lo denotamos así: $f:X \longrightarrow Y$. La noción de aplicación es muy natural, y no es difícil pensar en ejemplos de aplicaciones: de hecho uno muy habitual es tomando $X=\left\lbrace \text{productos de un supermercado} \right\rbrace$ e $Y=\left\lbrace \text{precios de dichos productos en ese supermercado} \right\rbrace$. Definiendo la aplicación $f:X \longrightarrow Y$ que manda cada producto que puedes comprar en su precio, tenemos una aplicación. Por ejemplo, $f$ lleva una pera en su precio (en ese mercado). En general, si $x$ es un elemento de $X$, e $y$ es...
ENTRAR