Aprendiendo a Contar I
Podemos empezar pensando en el trabajo que ya tenemos adelantado. Hemos visto en anteriores posts cuándo los cardinales (el número de elementos) de dos conjuntos son comparables y cómo compararlos. Recordemos que si tenemos dos conjuntos, $A$ y $B,$ sus cardinales son iguales si hay una biyección entre ellos, y $|A|\leq_C |B|$ si hay una función $f: A \longrightarrow B$ inyectiva. Además, si hay una función $g: A \longrightarrow B$ sobreyectiva entonces $|A|\geq_C |B|.$ Por tanto va a estar en nuestro interés el poder describir el conjunto de cosas que queremos contar y ponerlo en biyección con otro conjunto conocido, para ver que tienen el mismo número de elementos.
Antes de comenzar vamos a introducir una función muy conocida y muy útil en la combinatoria: el factorial. Se trata de una función $f:\mathbb{N}\longrightarrow \mathbb{N}$ con $f(m)=\prod_{n=1}^m n,$ es decir, le asigna a cada número el producto de todos los naturales menores o iguales que él: $f(n)=n\cdot (n-1) \cdot (n-2) \cdot ... \cdot 2 \cdot 1.$ Además normalmente se utiliza la notación $n!=f(n).$ Por convención (y por alguna razón que aclararemos más adelante) se considera $0!=1.$
En la combinatoria entre otras cosas vamos a querer adaptar algunas ideas naturales al lenguaje formal y conseguir resultados que nos indiquen cómo contar sin necesidad de establecer biyeciones. Por ejemplo, supongamos que somos dueños de varios locales: dos teatros, un cine y una sala de conciertos. Ahora queremos ver cuál es el aforo total entre todos los locales, sabiendo cuál es el aforo de cada uno. Consideramos un conjunto que tenga como elementos los locales, y otro conjunto que es el total de asientos de cada uno de los sitios (digamos $A=\left\lbrace \text{propiedades que tengo} \right\rbrace$ y $B=\left\lbrace \text{asientos entre todas las propiedades} \right\rbrace$). El conjunto $B$ podemos describirlo enumerando sus asientos: si el cine tiene $n_c$ asientos, podemos decir que $B_C=\left\lbrace \text{asientos del cine} \right\rbrace$ puede representarse de la forma: $B_C=\left\lbrace c_1,c_2, \ ..., c_{n_c} \right\rbrace.$ Para la sala de conciertos podemos tomar la misma idea y numerar los asientos de la forma $B_{S}=\left\lbrace s_1,s_2, \ ..., s_{n_s} \right\rbrace.$ Lo mismo con los teatros, $B_{T_1}$ y $B_{T_2},$ de forma que $B=B_{T_1}\cup B_{T_2} \cup B_C \cup B_S.$ También $A$ lo podemos representar mediante $A=\left\lbrace C,S,T_1,T_2 \right\rbrace.$ Ahora si pensamos en la aplicación $f:B \longrightarrow A$ que lleva cada butaca en la propiedad que está localizada, tenemos una aplicación sobreyectiva y además se cumple que:$$\left|B \right|=\sum_{a\in A} \left| f^{-1}(\left\lbrace a \right\rbrace)\right|= \sum_{a\in A} \left|B_a\right|$$Es decir, hay tantas butacas como la suma, a lo largo de todas las propiedades, de butacas de cada propiedad.
En el ejemplo anterior no hemos utilizado biyección alguna y hemos encontrado la manera de solucionar el problema. La manera de generalizar este resultado es muy fácil una vez que ya hemos visto un ejemplo. Veamos cómo hacerlo.
$\text{Lema (Recuento por Sobreyectivas).}$ Sean $X,Y$ conjuntos y $f:X \longrightarrow Y$ una función sobreyectiva. Entonces:$$\left| X \right| = \sum_{y\in Y}\left| f^{-1}(\left\lbrace y \right\rbrace) \right|$$ $\text{Corolario.}$ En particular, si $f$ es $K:1,$ es decir, $\left| f^{-1}(\left\lbrace y \right\rbrace) \right|=K$ para todo $y\in Y$ entonces $\left| X \right|=K\cdot \left| Y \right|$
Sean $X$ e $Y$ dos conjuntos finitos y $f:X \longrightarrow Y$ una función sobreyectiva. Denotamos $A_y=f^{-1}(\left\lbrace y \right\rbrace)$ con $y\in Y.$ Por ser $f$ sobreyectiva tenemos que $X = \bigcup_{y\in Y}A_y.$ Además, por ser $f$ función, cada elemento de $X$ tiene una única imagen, y por tanto la unión es disjunta: $X = \biguplus_{y\in Y}A_y.$ Por tanto, se tiene: $$\left| X \right| = \sum_{y\in Y} \left|A_y\right| =\sum_{y\in Y} \left| f^{-1}(\left\lbrace y \right\rbrace) \right|$$
Un problema conocido es el de enumerar el conjunto de listas ordenadas de $k$ elementos (denotadas $k$-listas) en las que cada elemento de la lista pertenece a un conjunto. Es decir, problemas como ¿cuántos números distintos hay que tengan $3$ cifras?, ¿cuántas posibles matrículas de un país puede haber?, etc. Podemos representar una lista ordenada de $k$ elementos de la forma: $\left( a_1 ,a_2 ,\ ..., a_k \right)$ donde $a_i \in A_i,$ con cada uno de los $A_i$ siendo un conjunto de $n_i$ elementos. De esta representación es fácil deducir cómo contar cuántas listas ordenadas de $k$ elementos hay: tantas como el cardinal del producto cartesiano de los $A_i.$
$\text{Lema (Regla del Producto).}$ Sean $A_1, A_2, \ ..., A_n$ conjuntos finitos. Entonces:$$\left| \prod_{i=1}^n A_i\right|=\prod_{i=1}^n \left| A_i \right|$$
Vamos a demostrarlo por inducción.
- Supongamos que tenemos dos conjuntos finitos, $A_1=\left\lbrace a^1_1, \ ...,a^1_{n_1} \right\rbrace$ y $A_2=\left\lbrace a^2_1, \ ...,a^2_{n_2} \right\rbrace.$ Ahora consideremos el conjunto producto $A_1 \times A_2=\left\lbrace (a^1,a^2): \ a^i \in A_i, \ i=1,2 \right\rbrace.$ Podemos representarlo en forma matricial:$$\begin{pmatrix} (a^1_1,a^2_1) & ... & (a^1_1,a^2_{n_2}) \\ ... & ... & ... \\ (a^1_{n_1},a^2_1) & ... & (a^1_{n_1},a^2_{n_2}) \end{pmatrix}$$de forma que es fácil ver que tiene $n_1 \cdot n_2$ elementos. Además, por cada $a^1_i$ hay $n_2$ pares con ese elemento. Al ser $i=1,\ ...,n_1$ entonces hay $n_2+n_2+...+n_2=n_1 \cdot n_2.$
- Ahora supongamos que $\left| \prod_{i=1}^n A_i\right|=\prod_{i=1}^n \left| A_i \right|.$ Si nombramos $B=\prod_{i=1}^n A_i$ entonces $\left| \prod_{i=1}^{n+1} A_i\right|=\left| B \times A_{n+1}\right|,$ que precisamente es lo que hemos visto en el caso de dos conjuntos: $\left| B \times A_{n+1}\right|=\left| B \right|\cdot \left|A_{n+1}\right|$ y aplicando la hipótesis de inducción tenemos que esto es igual a $\prod_{i=1}^{n+1} \left| A_i \right|.$ De modo que ya hemos terminado.
A menudo vamos a estar trabajando con conjuntos finitos, de manera que podemos establecer una biyección entre ellos e $I_n=\left\lbrace 1,2,\ ...,n\right\rbrace$ y nos interesará averiguar fórmulas particulares para cuando trabajemos con $I_n.$ Veamos algunos ejemplos clásicos que muestran la utilidad de esto:
Vamos a contar el número de funciones de $I_k$ en $I_n$ que podemos definir. Podemos pensar en una función de este tipo como una $k$-lista en la que cada elemento de la lista es la imagen de un elemento de $I_k.$ Es decir, primero damos la imagen del $1,$ $f(1),$ que podemos darla de $n$ formas distintas (ya que $f(1)\in I_n$). Esto equivale a que el primer elemento de la lista es un elemento del conjunto (de $n$ elementos) $I_n.$ La imagen de $2$ podemos tomarla de la misma forma, y como no tenemos ningún tipo de restricción sobre cómo debe ser, también tenemos $n$ opciones. En general, para cualquier número $m$ de $I_k$ tenemos $n$ posibles imágenes que darle, luego nuestro problema se reduce a contar cuántas $k$-listas podemos hacer con elementos de $I_n$ de forma que podemos repetirlos. El resultado es: $\prod_{i=1}^k \left| I_n \right| = n^k.$
Vamos a contar cuántas funciones inyectivas hay de $I_k$ en $I_n.$ Lo primero que hay que observar es que $n$ tiene que ser mayor o igual que $k,$ pues si tenemos que mandar $k$ elementos en $n$ elementos y $k$ es mayor que $n$ entonces al menos dos se repiten y por tanto la función deja de ser inyectiva. Ahora podemos establecer una similitud con las $k$-listas. Al primer elemento de la lista le asignamos su imagen. Hay $n$ formas distintas de hacer esto. Al segundo le asignamos su imagen, para lo que tenemos $n-1$ formas distintas de hacerlo, pues no puede coincidir con la imagen del primero. En general, para la posición $m$ de la lista podemos asignarle $n-m+1$ posibles imágenes distintas, evitando repetir las $m-1$ anteriores. Por tanto estamos contando cuántas $k$-listas hay en las que los conjuntos son $I_n,I_{n-1}, \ ..., I_{n-k+1}$ y la solución es que habrá $\prod_{i=1}^k \left| I_{n-i+1} \right| = n\cdot (n-1) \cdot ... \cdot (n-k+1)$ y podemos expresar este número como $\frac{n!}{(n-k)!}.$
Vamos a contar cuántas funciones biyectivas hay de $I_n$ en $I_n.$ Para que una función de este tipo sea biyectiva ha de ser inyectiva y sobreyectiva. De hecho, al ser de un conjunto finito en si mismo basta con que sea inyectiva, pues en ese caso sería también sobreyectiva. Por tanto hay tantas como funciones inyectivas de $I_n$ en si mismo, y este cálculo ya lo hemos realizado. En este ejemplo tenemos $k=n$ y por tanto hay $\frac{n!}{(n-k)!}=\frac{n!}{0!}=n!.$ Este tipo de aplicaciones se llaman permutaciones, ya que únicamente cambian el orden los elementos de la lista, es decir, los permutan.
Imaginemos que tenemos que afrontar el problema de calcular cuántos divisores tiene un cierto número dado. Para resolverlo podemos pensar en cómo describir estos números, los divisores. Podemos pensar en que como todo número natural tiene una descomposición única como producto de números primos quizá esto nos ayude. Vamos a hacerlo para el caso particular del número $49.000.$ Este número descompone en factores primos como $49.000=2^3 \cdot 5^3 \cdot 7^2,$ y por tanto sabemos que cualquier número de la forma $2^{\alpha}\cdot 5^{\beta}\cdot 7^{\gamma}$ con $0\leq \alpha \leq 3,$ $0\leq \beta \leq 3$ y $0 \leq \gamma \leq 2$ va a ser divisor de $49.000.$ Hemos reducido el problema a uno de calcular cuántas $3$-listas distintas podemos considerar en las que el primer elemento esté tomado de un conjunto de $4$ elementos, el segundo de otro conjunto de $4$ y el tercero de otro de $3.$ La respuesta por tanto es $4 \cdot 4 \cdot 3=48.$
Ahora que hemos visto algunas nociones básicas sobre cómo contar algunos conjuntos, vamos a plantearnos el siguiente problema y pensar en cómo podemos resolverlo:
$\text{Ejemplo: Listas Circulares.}$
Imaginemos que estamos unos amigos sentados en una mesa redonda. ¿De cuántas maneras distintas podemos sentarnos alrededor de la mesa? La pregunta no es tan simple aquí, ya que si rotamos los asientos pero mantenemos el mismo orden la posición no cambia. Es decir, si establecemos una analogía con las listas, y consideramos las posibles disposiciones en la mesa como listas circulares (nombre motivado por la forma de la mesa), las listas circulares representadas como $(A,B,C),\ (C,A,B)$ y $(B,C,A)$ en un grupo de $3$ amigos (los amigos $A,B$ y $C$ ) son iguales:
Vamos a definir los conjuntos $X=\left\lbrace k\text{-listas circulares de }k\text{ elementos sin rep.} \right\rbrace$ e $Y=\left\lbrace k\text{-listas de }k\text{ elementos sin rep.} \right\rbrace,$ de manera que el problema se reduce a averiguar el cardinal de $X$. La idea en este ejemplo es darse cuenta de que hay tantas rotaciones como amigos haya sentados alrededor de la mesa. Una vez que sabemos eso, utilizando el recuento por sobreyectivas podemos establecer que por cada $k$-lista circular sin repetición habrá $k$ $k$-listas sin repetición:$$\left| X \right|=\frac{1}{k}\cdot \left| Y \right| = \frac{1}{k}\cdot k!=(k-1)!$$Generalizando un poco el problema y considerando que en vez de $k$ amigos hay $n\geq k$ amigos de los cuales sólo $k$ se sientan alrededor de la mesa redonda (imaginemos que sólo había sitio para $k$ personas cuando hicieron la reserva pero luego resultó que querían ir más amigos y ahora no la pueden cambiar), entonces el problema se convierte en ver cuántas $k$-listas circulares de $n$ elementos sin repetición hay. Utilizando la misma idea de antes llegamos a que habrá $k$ veces más $k$-listas de $n$ elementos sin repetición que $k$-listas circulares de $n$ elementos sin repetición. Por tanto, utilizando la misma notación anterior para $X$ e $Y$ pero esta vez con $n$ elementos ambos, obtenemos:$$\left| X \right|=\frac{1}{k}\cdot \left| Y \right| = \frac{1}{k}\cdot \frac{n!}{(n-k)!}$$
Comentarios
Publicar un comentario