Conteo Básico

Teoría

El conteo básico, o combinatoria enumerativa, es el estudio matemático de cómo determinar el tamaño de conjuntos finitos sin tener que enlistar cada elemento uno por uno. Sirve como la base para la teoría de la probabilidad y la matemática discreta avanzada. Esta disciplina se apoya en dos intuiciones fundamentales: el Principio de la Suma, que aplicas cuando divides un problema de conteo en casos mutuamente excluyentes (Opción A O Opción B), y el Principio de la Multiplicación, que usas cuando una tarea consiste en una secuencia de pasos independientes (Opción A Y Opción B).

Para dominar el conteo básico, necesitas aprender a distinguir entre permutaciones (donde el orden importa) y combinaciones (donde el orden no importa). Un error muy común en las olimpiadas de matemáticas es contar de más o contar de menos los resultados. Para evitar esto, tienes que definir con mucho cuidado si los objetos que estás contando son distintos o idénticos, y si el acomodo de esos objetos cambia el resultado final. El salto del conteo simple a los problemas de nivel olimpiada suele involucrar la "división por simetría", una técnica que sirve para corregir el conteo excesivo dividiendo entre el número de arreglos redundantes.

Fórmulas Clave

1. El Principio de la Suma Si tienes dos conjuntos $A$ y $B$ que son ajenos ($A \cap B = \emptyset$), el número de formas de elegir un elemento de $A$ o de $B$ es: $$|A \cup B| = |A| + |B|$$

2. El Principio de la Multiplicación Si un procedimiento se puede dividir en $k$ etapas sucesivas e independientes, donde la etapa $i$ tiene $n_i$ opciones, el número total de formas de completar el procedimiento es: $$N = n_1 \times n_2 \times \dots \times n_k$$

3. Factoriales El número de formas de acomodar $n$ objetos distintos en una fila es $n!$ (se lee "$n$ factorial"): $$n! = n \times (n-1) \times \dots \times 2 \times 1, \quad \text{con } 0! = 1$$

4. Permutaciones (El orden importa) El número de formas de acomodar $k$ elementos distintos seleccionados de un conjunto de $n$ elementos distintos se escribe como $P(n,k)$ o $_nP_k$: $$P(n,k) = \frac{n!}{(n-k)!} = n(n-1)\dots(n-k+1)$$

5. Combinaciones (El orden no importa) El número de formas de elegir un subconjunto de $k$ elementos de un conjunto de $n$ elementos distintos se escribe como $C(n,k)$ o $\binom{n}{k}$: $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

Identidad Importante: $$\binom{n}{k} = \binom{n}{n-k}$$

Demostración

Teorema: El número de formas de elegir $k$ objetos distintos de un conjunto de $n$ objetos distintos, donde el orden no importa, es $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

Demostración: Para obtener la fórmula de las combinaciones, vas a relacionarla con la fórmula de las permutaciones usando el Principio de la Multiplicación.

Toma un conjunto $S$ de $n$ elementos distintos. Lo que quieres es encontrar el número de subconjuntos de $S$ que tengan tamaño $k$. Llama a esta cantidad desconocida $C$.

Considera el proceso de formar una permutación de longitud $k$ a partir del conjunto $S$. Puedes pensar en este proceso de dos maneras diferentes.

Método 1: Construcción Directa (Fórmula Estándar de Permutaciones) Eliges el primer objeto ($n$ opciones), luego el segundo ($n-1$ opciones), y así hasta llegar al objeto $k$ ($n-k+1$ opciones). Por el Principio de la Multiplicación, el número total de arreglos ordenados es: $$P(n,k) = n(n-1)\dots(n-k+1) = \frac{n!}{(n-k)!}$$

Método 2: Construcción en Dos Etapas (Selección y luego Acomodo) Otra forma de verlo es que puedes formar una permutación de longitud $k$ así:

1. Primero, eliges un subconjunto de $k$ elementos de los $n$ objetos disponibles. Por definición, hay $C$ formas de hacer esto.
2. Segundo, acomodas estos $k$ elementos elegidos en un orden específico. Hay $k!$ formas de acomodar $k$ objetos distintos.

Por el Principio de la Multiplicación, el número total de permutaciones es el producto de las formas de hacer estos dos pasos: $$\text{Total de Permutaciones} = C \times k!$$

Conclusión Como ambos métodos cuentan exactamente el mismo conjunto de resultados (arreglos ordenados de tamaño $k$), puedes igualar los resultados: $$C \times k! = P(n,k)$$ $$C \times k! = \frac{n!}{(n-k)!}$$

Si despejas $C$: $$C = \frac{n!}{k!(n-k)!}$$

Así que, $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. $\square$