Conteo
Cardinal de un conjunto
El cardinal de un conjunto es la cantidad de elementos que contiene. Si \(A\) es un conjunto finito, su cardinal es \(|A|\).
Por ejemplo:
- Si \(A = \{1, 2, 3\} \implies |A| = 3\).
- Si \(B = \{a, b, c, d, e\} \implies |B| = 5\).
Conjuntos como \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\) y \(\mathbb{R}\) son infinitos, por lo que no tienen cardinal.
Principio de adición
Si un conjunto \(A\) tiene \(m\) elementos y un conjunto \(B\) tiene \(n\) elementos, definimos:
\(|A \cup B| = |A| + |B|\)
Para que el principio de adición sea válido, los conjuntos \(A\) y \(B\) deben ser disjuntos, es decir, no deben tener elementos en común, es decir:
\[|A \cup B| = |A| + |B| - |A \cap B| \]Dadas las actividades \(A, B\), si \(A\) tiene \(m\) formas de realizarse y \(B\) tiene \(n\) formas de realizarse, entonces el número de formas de realizar \(A\) o \(B\) es \(m + n\).
Principio de multiplicación
Si un conjunto \(A\) tiene \(m\) elementos y un conjunto \(B\) tiene \(n\) elementos, definimos:
\(|A \times B| = |A| \cdot |B|\)
Si \(A\) y \(B\) conjuntos el producto cartesiano de ambos es:
\[A \times B = \{(a, b) \mid a \in A, b \in B\} \]Dadas las actividades \(A, B\), si \(A\) tiene \(m\) formas de realizarse y \(B\) tiene \(n\) formas de realizarse, entonces el número de formas de realizar \(A\) y \(B\) es \(m \cdot n\).
Selecciones ordenadas con repetición
Sean \(m, n \in \mathbb{N}\), hay \(n^m\) formas de elegir ordenadamente \(m\) elementos de un conjunto de \(n\) elementos.
Por ejemplo, si tenemos un conjunto \(A = \{1, 2, 3\}\) y queremos elegir 2 elementos ordenadamente, entonces hay \(3^2 = 9\) formas de hacerlo. Esto se puede justificar con el principio de multiplicación:
\[A \times A = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)\} \]Subconjuntos
La cantidad de subconjuntos de un conjunto con \(n\) elementos es \(2^n\).
Dado \(X\) un conjunto, denotamos \(P(X)\) al conjunto de todos los subconjuntos de \(X\).
Por ejemplo, si \(X = \{1, 2\}\), entonces \(P(X) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}\).
Por lo tanto, \(P(X) = 2^{|X|}\) para cualquier conjunto \(X\).
Selecciones ordenadas sin repetición
Si tuvieramos un conjunto \(A = \{1, 2, 3\}\) y queremos elegir selecciones de \(3\) elementos ordenados sin repetición, podemos pensar:
- ¿Cuántas formas hay de elegir el primer elemento? 3.
- ¿Cuántas formas hay de elegir el segundo elemento? 2.
- ¿Cuántas formas hay de elegir el tercer elemento? 1.
Las formas serían: \(123, 132, 213, 231, 312, 321\). Con \(6\) selecciones ordenadas sin repetición del mismo elemento. Tenemos entonces \(3 \cdot 2 \cdot 1 = 3! = 6\) selecciones posibles.
Es importante mencionar que la cantidad de elementos \(n\) debe ser mayor o igual a la cantidad de elementos a seleccionar \(m\), es decir, \(n \geq m\).
Si se cumple esta condición existen
\[\frac{n!}{(n - m)!} \]formas de seleccionar \(m\) elementos de un conjunto de \(n\) elementos con orden y sin repetición.
Permutaciones
Dado un conjunto \(A\) con \(n\) elementos, hay \(n!\) permutaciones de grado \(n\). Es decir, la cantidad de formas de ordenar los elementos de un conjunto.
Por ejemplo, si tenemos un conjunto \(A = \{1, 2, 3\}\), entonces hay \(3!\) permutaciones posibles:
\[A = \{1, 2, 3\} \implies \{1, 2, 3\}, \{1, 3, 2\}, \{2, 1, 3\}, \{2, 3, 1\}, \{3, 1, 2\}, \{3, 2, 1\} \]Ejemplo:
- Cuantas permutaciones se pueden hacer con la palabra “IGNACIO”?
Si las letras fuesen distintas, serían \(7!\) permutaciones.
Sin embargo, se repite la letra “I” \(2\) veces, por lo que hay un doble de posibilidades. Podemos escribir en su lugar:
Si consideramos la palabra con letras distintas, tenemos \(7!\) permutaciones. Pero las permutaciones del tipo:
\[\textnormal{I...I'...} \\ \textnormal{I'...I...} \\ \]Coinciden, por lo que debemos dividir entre \(2!\) para eliminar las permutaciones repetidas.
Por lo tanto, hay \(\frac{7!}{2!}\) permutaciones posibles.
Números combinatorios (sin orden y sin repetición)
\[\binom{n}{m} = \frac{n!}{(n - m)! \; m!} \]Sea \(X\) un conjunto de \(n\) elementos y \(n \geq m\), el número total de subconjuntos de \(m\) elementos de \(X\) es:
Este número se denota como \(\binom{n}{m}\) y se lee “combinatorio n m”.
Ejemplo:
- ¿Cuántos comités pueden formarse de un conjunto de 6 mujeres y 4 hombres, si el comité debe tener 4 mujeres y 2 hombres?
Para formar el comité, primero debemos seleccionar las \(4\) mujeres de las \(6\) disponibles y luego seleccionar los \(2\) hombres de los \(4\) disponibles. Si se compone por \(4\) mujeres y \(2\) hombres, debemos multiplicar las selecciones:
\[\binom{6}{4} \cdot \binom{4}{2} = \frac{6!}{4!(6 - 4)!} \cdot \frac{4!}{2!(4 - 2)!} = 15 \cdot 6 = 90 \]Teorema del binomio
Sea \(n\) entero positivo, el coeficiente del termino \(a^{n-r}b^r\) en la expansión de \((a + b)^n\) es \(\binom{n}{r}\).
Por ejemplo, si tenemos \((a + b)^3\), la expansión sería:
\[(a + b)^3 = \binom{3}{0}a^3b^0 + \binom{3}{1}a^2b^1 + \binom{3}{2}a^1b^2 + \binom{3}{3}a^0b^3 \]Por lo que la expansión sería:
\[a^3 + 3a^2b + 3ab^2 + b^3 \]También podemos expresarlo como:
\[(a + b)^3 = \sum_{k=0}^{3} \binom{3}{k}a^{3-k}b^k \]Ejercicios resueltos - Conteo
Nota: Una de las características de los ejercicios de conteo es que se pueden resolver de distintas formas acorde a los distintos métodos de selección. Las consignas deben ser claras para evitar ambigüedades.
1.
- ¿Cuántos números de \(4\) cifras se pueden formar?
Nuestro primer dato es la cantidad de cifras, que es \(4\). Para que se considere como un número de \(4\) cifras, el primer dígito debería ser distinto a \(0\). Por lo tanto, nuestras posibilidades para ese dígito son: \(1, 2, 3, 4, 5, 6, 7, 8, 9\).
Para los siguientes dígitos, no hay restricciones. Por lo tanto, hay \(9 \cdot 10 \cdot 10 \cdot 10 = 9000\) números posibles.
2.
- ¿Cuantas formas es posible ordenar la palabra “MATEMATICA”?
En este caso, observemos que \(\textnormal{MATEMATICA}\) tiene las letras “A”, “M” y “T” repetidas. Por lo tanto, si las letras fuesen distintas, habría \(10!\) formas de ordenar la palabra. Sin embargo, debemos dividir por las permutaciones repetidas.
\[\frac{10!}{3!2!2!} = 151200 \]3.
- ¿Cuantas patentes de auto se pueden hacer con \(3\) letras y \(3\) números?
Sabemos que el alfabeto tiene \(26\) letras y los números del \(0\) al \(9\), siendo un total de \(10\) números. Las letras y los números no necesitan orden pero si pueden repetirse. Por lo tanto, tenemos:
\[26 \cdot 26 \cdot 26 = 26^3 \textnormal{ formas de elegir las letras} \\ 10 \cdot 10 \cdot 10 = 10^3 \textnormal{ formas de elegir los números} \]Ahora multiplicamos ambos resultados para obtener la cantidad de patentes posibles:
\[26^3 \cdot 10^3 = 17576000 \]4.
¿De cuántas formas puede formarse un comité de 5 personas tomadas de un grupo de 11 personas entre las cuales hay 4 profesores y 7 estudiantes, si:
A) No hay restricciones
B) El comité debe tener exactamente dos profesores
C) El comité debe tener al menos tres profesores
D) El profesor X y el estudiante Y no pueden estar juntos
Comenzando con el caso A), no hay restricciones. Por lo tanto, podemos seleccionar \(5\) personas de un total de \(11\) sin restricciones, dicha selección no tiene orden ni repetición.
\[\binom{11}{5} = \frac{11!}{5!(11 - 5)!} = 462 \]Para el caso B), debemos seleccionar \(2\) profesores de \(4\) y \(3\) estudiantes de \(7\). Multiplicando ambos resultados para obtener todas las posibilidades:
\[\binom{4}{2} \cdot \binom{7}{3} = \frac{4!}{2!(4 - 2)!} \cdot \frac{7!}{3!(7 - 3)!} = 84 \]Para el caso C), debemos tener al menos \(3\) profesores, lo que implica que podemos tener \(3\) profesores y \(2\) estudiantes o \(4\) profesores y \(1\) estudiante.
\[\binom{4}{3} \cdot \binom{7}{2} + \binom{4}{4} \cdot \binom{7}{1} = 84 + 7 = 91 \]Para el caso D), debemos seleccionar \(5\) personas sin que el profesor X y el estudiante Y estén juntos. Para ello, seleccionamos \(5\) personas sin restricciones y restamos las selecciones donde X e Y están juntos.
\[\binom{11}{5} - \binom{9}{3} = 462 - 84 = 378 \]5.
Demostrar si se cumple la siguiente desigualdad:
\[\binom{1000}{7} 120! > 9^{1000} \]A simple vista los números son demasiado grandes para ser calculados de forma exacta. Podemos aplicar el Teorema del Binomio en la potencia de \(9\) de la siguiente manera:
\[\begin{align*} \binom {1000}{7} \cdot 120! &> (8 + 1)^{1000} \\ \binom{1000}{7} \cdot 120! &> \displaystyle{\sum_{k=0}^{1000}} \binom {1000}{k} \cdot 8^{1000 - k} \cdot 1^k \end{align*} \]\(1\) elevado a cualquier número \(\geq 0\) es 1, por lo que la suma se simplifica a:
\[\binom{1000}{7} \cdot 120! > \displaystyle{\sum_{k=0}^{1000}} \binom{1000}{k} \cdot 8^{1000-k} \]Observemos que podríamos hacer el siguiente análisis (ya que no sabemos si la desigualdad es cierta o no):
\[\binom{1000}{7} \cdot 120! < \binom{1000}{7} \cdot 8^{993} \leq \displaystyle{\sum_{k=0}^{1000}} \binom{1000}{k} \cdot 8^{1000-k} = 9^{1000} \]Por el axioma de la compatibilidad del producto con el orden podemos probar la desigualdad para el factorial y la potencia.
\[\binom{1000}{7} \cdot 120! < \binom{1000}{7} \cdot 8^{993}\;(ac < bc) \\ \;\\ 120! < 8^{993}\;(a < b) \]Ahora, por propiedad de las potencias, podemos escribir \(8^{993}\) como \((8^3)^{331}\).
\[\begin{align*} 120! &< (8^3)^{331} \\ 120 \cdot 119 ... \cdot 2 \cdot 1 &< 512 \cdot 512 ... \cdot 512 \end{align*} \]\(512\) se multiplica \(331\) veces, por lo que volviendo a la desigualdad original:
\[\binom{1000}{7} 120! > 9^{1000} \]No se cumple, \(9^{1000}\) es mayor que \(\binom{1000}{7} 120!\)