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 sin orden ni 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 sin orden y sin repetición.

Permutaciones

Dado un conjunto $A$ con $n$ elementos, hay $n!$ permutaciones de grado $n$ . Es decir, $n$ selecciones ordenadas sin repetición de $n$ elementos.

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:

\textnormal{IGNACI'O}

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)

Sea $X$ un conjunto de $n$ elementos. Entonces el número total de subconjuntos de $m$ elementos de $X$ es:

\binom{n}{m} = \frac{n!}{(n - m)!m!} \;\;(n \geq m)

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

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.

¿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.

¿Cuantas formas es posible ordenar la palabra “MATEMATICA”?

En este caso, observemos que $\textnormal{MATEMATICA}$ tiene la letra $A$ repetida dos veces. Si distinguieramos la letra $A$ de $A'$ tendríamos:

\textnormal{MATEMATICA'} \\ \textnormal{MA'TEMATICA}

De esta forma, si permutamos las letras obtendríamos palabras repetidas. En este caso necesitamos seleccionar $10$ letras con orden y sin repetición, y para ello tenemos $10!$ permutaciones. Sin embargo, debemos dividir por $2!$ para eliminar las permutaciones repetidas de la letra $A$ .

\frac{10!}{2!} = 1814400

¿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

¿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

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!$

Números Enteros Divisibilidad