Semana 3 - Combinatoria

Combinatoria

Hilo conductor: contar es construir una elección paso a paso. Si las elecciones son alternativas, se suman; si son etapas, se multiplican.

1. Las dos reglas para contar

Si $# A$ es la cantidad de elementos de $A$ :

Situación	Pregunta mental	Regla
Casos disjuntos	“¿este caso o aquel?”	$# (A \cup B) = # A + # B$ si $A \cap B = \emptyset$
Elección en etapas	“¿primero esto y después aquello?”	$k_{1} \cdot k_{2} \dots k_{r}$

En particular, $# (A \times B) = # A \cdot # B$ .
Si los casos se superponen, no dupliques: $# (A \cup B) = # A + # B - # (A \cap B)$ .

Memoria: “o” suma; “y después” multiplica.

2. Funciones: cada elemento del dominio elige una imagen

Sean $# A = n$ y $# B = m$ .

Qué se cuenta	Condición	Cantidad
Funciones $A \to B$	se permite repetir imagen	$m^{n}$
Funciones inyectivas $A \to B$	imágenes distintas; requiere $n \leq m$	$m (m - 1) \dots (m - n + 1) = \frac{m!}{(m - n)!}$
Biyectivas $A \to A$	reordenar $n$ elementos	$n!$

El factorial es $n! = n (n - 1) \dots 2 \cdot 1$ , con $0! = 1$ .

Traducción útil: objetos o personas numerados en cajas numeradas = funciones; “a lo sumo uno por caja” = inyectividad; “ninguna caja vacía” = sobreyectividad.

3. ¿Importa el orden?

Se eligen $k$ de $n$	¿El orden importa?	Cantidad
Lista de $k$ elementos distintos	Sí	$V (n, k) = \frac{n!}{(n - k)!}$
Subconjunto de $k$ elementos	No	$(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$

Una misma elección de $k$ elementos puede ordenarse de $k!$ maneras. Por eso:

V (n, k) = (\binom{n}{k}) k! .

$(\binom{n}{k}) = (\binom{n}{n - k})$ : elegir $k$ para entrar equivale a elegir $n - k$ para quedar afuera.
Un conjunto de $n$ elementos tiene $2^{n}$ subconjuntos:

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n} .

Chequeo: si hay “puestos”, “podio”, “asientos” o una clave, el orden suele importar. Si solo se arma un grupo, no.

4. Anagramas y restricciones

Si los $n$ objetos son todos distintos: $n!$ ordenamientos.
Si hay repeticiones de cantidades $r_{1}, r_{2}, \dots, r_{t}$ , con $r_{1} + \dots + r_{t} = n$ :

\frac{n!}{r_{1}! r_{2}! \dots r_{t}!} .

Si ciertos objetos deben quedar juntos, trátalos como un bloque y luego ordena dentro del bloque.
Por ejemplo, tres vocales juntas entre cinco consonantes distintas: $6! \cdot 3!$ .
Si una condición separa casos disjuntos, cuenta cada caso y suma.

5. Bolitas en cajas: primero identificá qué es distinguible

Bolitas	Cajas	Restricción	Cantidad
Numeradas	Numeradas	ninguna	$m^{n}$
Numeradas	Numeradas	a lo sumo una por caja	$\frac{m!}{(m - n)!}$
Indistinguibles	Numeradas	ninguna	$(\binom{n + m - 1}{n})$
Indistinguibles	Numeradas	ninguna vacía ( $n \geq m$ )	$(\binom{n - 1}{m - 1})$

En las dos últimas filas, una distribución es una solución de

x_{1} + x_{2} + \dots + x_{m} = n .

Usamos estrellas y barras: $n$ estrellas (bolitas) y $m - 1$ barras (separan cajas).
Para exigir $x_{i} \geq a_{i}$ , colocá primero $a_{i}$ bolitas en cada caja y distribuí las restantes.

Ojo: “exactamente $r$ cajas vacías” = elegir esas cajas y exigir que las demás no queden vacías.

6. Binomio de Newton

Al expandir $(a + b)^{n}$ , elegir $a$ en $k$ factores y $b$ en los demás produce $a^{k} b^{n - k}$ , y eso puede hacerse de $(\binom{n}{k})$ maneras:

(a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k} .

Los coeficientes son los números combinatorios. Ejemplo:

(a + b)^{3} = a^{3} + 3 a^{2} b + 3 a b^{2} + b^{3} .

7. Probabilidad en espacios equiprobables

Si todos los resultados elementales de $Ω$ son igual de probables, para un evento $E \subseteq Ω$ :

P (E) = \frac{# E}{# Ω} .

$P (Ω) = 1$ , $P (\emptyset) = 0$ y $0 \leq P (E) \leq 1$ .
Complemento: $P (E^{c}) = 1 - P (E)$ .
Si $E$ y $F$ son disjuntos: $P (E \cup F) = P (E) + P (F)$ .
En general:

P (E \cup F) = P (E) + P (F) - P (E \cap F) .

Antes de contar: describí un espacio muestral cuyos resultados sean equiprobables. En varias extracciones o lanzamientos, el orden suele distinguir resultados.

Mantra final: primero decidí qué objeto se distingue, después si el orden importa y recién entonces elegí la regla de suma, producto o combinaciones.