# Combinatoria (Div. B)
## Repaso teoría de conjuntos

### Conjuntos
Un **conjunto** es una colección bien definida de elementos. En esta clase trabajaremos con conjuntos con una cantidad finita de elementos.

Utilizaremos la siguiente notación en conjuntos:

- $A=\{2,4,6\}$: representación listando los elementos.
- $A=\{x : 1 \leq x \leq 6$ y $x$ es par$\}$: representación dada una propiedad.
- $x \in A$: pertenencia. El elemento $x$ está en $A$.
- $A \cup B$: unión. Conjunto formado por los elementos que están en $A$ **o** $B$.
- $A \cap B$: intersección. Conjunto formado por los elementos que están en $A$ **y** $B$.
- $|A|$: cardinalidad de $A$. La cantidad de elementos en el conjunto $A$.
- $A \subseteq B$: subconjunto. Todos los elementos de $A$ están también en $B$.
- $A \supseteq B$: superconjunto. Todos los elementos de $B$ están también en $A$.
- $\emptyset$: conjunto vacío. Conjunto que no contiene ningún elemento.
- $\overline{A}$: complemento. Elementos del universo que no están en $A$.

### Funciones
Una función es una relación donde a cada elemento de un conjunto $D$, le asignia un elemento único de un conjunto $R$. Vamos a escribir $f(d)=r$, donde $d \in D$, $r \in R$, $D$ es el dominio de $f$ y $R$ es el rango de $f$. Otra notación para las funciones es $f:D \rightarrow R$.

#### Funciones inyectivas
Una función inyectiva, también llamada uno a uno, es aquella donde $f(d_1)=f(d_2)$ implica que $d_1=d_2$. Esto es equivalente a decir que si $d_1 \neq d_2$ entonces $f(d_1) \neq f(d_2)$.

#### Funciones sobreyectivas
Una función sobreyectiva, también llamada exhaustiva, es aquella para la cual todos los elementos $r \in R$, existe un elemento $d \in D$ tal que $f(d)=r$.

#### Funciones biyectivas
Una función biyectiva es aquella que es inyectiva y sobreyectiva. En otras palabras, una función es biyectiva si para todos los elementos $r \in R$ del rango, existe exactamente un elemento $d \in D$ del dominio tal que $f(d)=r$.

Podemos pensar en una función biyectiva, como una función que empareja a los elementos de $D$ con los de $R$, de forma que cada elemento pertenezca a exactamente una pareja.


En el ejemplo anterior, la función de la izquierda es la representación gráfica de una función inyectiva, la de enmedio de una función sobreyectiva, y la de la derecha de una función inyectiva.

##### Relación entre biyecciones y la cartinalidad de $D$ y $R$
Si existe una función biyectiva entre dos conjuntos $D$ y $R$, entonces ambos conjuntos tienen la misma cardinalidad. Y esto es cierto en ambos sentidos.

##### Inverso de una función
Una función es invertible (tiene un inverso) si y sólo si es inyectiva. Si $f(d)=r$, entonces su inversa es otra función $f^{-1}$ tal que $f^{-1}(r)=d$.

## Fundamentos de combinatoria

### Principio de la suma y del producto

Digamos que tenemos un evento $A$ que puede ocurrir de $n$ formas y un evento $B$ que puede ocurrir de $m$ formas. El **principio de la suma** nos dice que si $A$ y $B$ no pueden ocurrir al mismo tiempo, entonces hay $n+m$ formas de que ocurra $A$ **o** $B$ (pero no ambos). Y el **principio de la multiplicación** nos dice si $A$ y $B$ ocurren de forma simultánea, entonces hay $n \cdot m$, formas de que ocurran $A$ **y** $B$.

### Permutaciones
Dada una colección de $n$ elementos distintos, hay $n!$ formas de ordenarlos ($n!$ es el factorial de $n$, y es igual a $n \cdot (n-1) \cdot (n-2)\cdots1$).

#### Permutaciones con repetición
Dada una colección de $n$ elementos con $k$ tipos de elementos, donde hay $a_i$ elementos indistinguibles del tipo $i$, la cantidad de ordenamientos distintos es:

$$
\frac{n!}{a_1! \cdot a_2!\cdots a_k!}
$$

### Combinaciones
El coeficiente binomial $\binom{n}{k}$ expresa las formas de elegir $k$ elementos de un conjunto de $n$ elementos distintos. Las dos formas más comunes de expresar este número son:

$$
\begin{align}
\binom{n}{k}&=\binom{n-1}{k}+\binom{n-1}{k-1} \\\\
\binom{n}{k}&=\frac{n!}{k!(n-k)!}
\end{align}
$$

#### Multinomial
Si tenemos $n$ elementos distintos y $k$ cajas distintas, tal que queremos meter $a_i$ elementos en la caja $i$, la forma de distribuir los elementos está dada por el coeficiente multinomial $\binom{n}{a_1, a_2, \dots, a_k}$. Las dos formas de expresar el multinomial son las siguientes:

$$
\begin{align}
\binom{n}{a_1, a_2, \dots, a_k}&=\binom{n}{a_k}\binom{n-a_k}{a_1, a_2, \ldots, a_{k-1}} \\ \\
\binom{n}{a_1, a_2, \dots, a_k}&=\frac{n!}{a_1! \cdot a_2!\cdots a_k!}
\end{align}
$$

### Principio de inclusión-exclusión
Si tenemos $n$ conjuntos finitos $A_1, A_2, \dots, A_n$, se cumple la siguiente identidad:

$$
\Bigg|\bigcup_{i=1}^{n} A_i \Bigg|=\sum_{\substack{S \subseteq \{1, 2, \dots, n\} \\ S \neq \emptyset}}\Bigg| \bigcap_{j \in S}A_j \Bigg|(-1)^{|S|+1}
$$

#### Generalización
La cantidad de elementos de existen en la intersección de exactamente $k$ conjuntos es:

$$
\Bigg|\bigcup_{\substack{R \subseteq \{1, 2, \dots, n\} \\ |R| = k}} \bigg( \bigcap_{i \in R} A_i \cap \bigcap_{i \notin R} \overline{A_i} \bigg) \Bigg|=\sum_{l=k}^n (-1)^{l-k} \binom{l}{k} \sum_{\substack{S \subseteq \{1, 2, \dots, n\} \\ |S| = k}} \Bigg|\bigcap_{i \in S} A_i \Bigg|
$$

## Biyecciones en combinatoria
### Estrellas y barras (stars and bars)
:::success
:information_source: **Problema**
¿Cuántas soluciones existen a la ecuación $x_1+x_2+\dots+x_n=k$, tal que $x_i$ es un entero no negativo?

**Límites:**
- $1 \leq n,k \leq 10^7$.

**Ejemplo:**
$x_1+x_2+x_3=3$ tiene $10$ soluciones:
$$
\begin{align}
(3,0,0),(2,1,0),(2,0,1),(1,2,0),(1,1,1),\\
(1,0,2),(0,3,0),(0,2,1),(0,1,2),(0,0,3)
\end{align}
$$
:::

Podemos tratar de resolver el problema con algunos métodos como recurrencias o DP, pero es complicado llegar a la solución así. Cuando parezca complicado contar directamente algo, un enfoque que podemos intentar es el de crear una biyección entre lo que queremos contar y otro conjunto de objetos que sea más fácil contar.

Definamos nuestro conjunto $D$ como el conjunto de todas las soluciones a la ecuación. Ahora búsquemos con que conjunto $R$ podemos definir una función biyectiva. El conjunto más común en problemas de ecuaciones con soluciones enteras es el de cadenas binarias de un tamaño fijo donde los carácteres son barras ($|$) y estrellas ($\star$). Usaremos este enfoque. Primero definimos la función $f$ por medio de un algoritmo:

1. Recibir una solución a la ecuación.
2. Inicializar una cadena vacía $s$.
3. Iterar sobre $i$ desde $i=1$ hasta $i=n-1$
a. Insertar $x_i$ estrellas al final de $s$.
b. Insertar una barra al final de $s$.
4. Insertar $x_n$ estrellas al final de $s$.
5. Regresar $s$.

:::info
:information_source: **Ejemplo**
Consideremos la ecuación $x_1+x_2+x_3+x_4=10$, y veamos lo que nos regresa la función para alguna de sus soluciones:

- $f((2,4,3,1))=\star\star|\star\star\star\star|\star\star\star|\star$
- $f((3,0,3,4))=\star\star\star||\star\star\star|\star\star\star\star$
- $f((1,2,6,1))=\star|\star\star|\star\star\star\star\star\star|\star$
:::

Notemos que el algoritmo le agrega a $s$ $x_1+x_2+\dots+x_n=k$ estrellas, y $n-1$ barras, por lo tanto $s$ será una cadena de tamaño $k+n-1$ con $k$ estrellas y $n-1$ barras. Entonces podemos definir a nuestro conjunto $R$ como el conjunto de todas las cadenas binarias de tamaño $k+n-1$ con $k$ estrellas y $n-1$ barras. Es fácil contar cuántos elementos tiene este conjunto (puede ser con permutaciones con repeticiones o coeficiente binomial):

$$
\binom{k+n-1}{k}=\frac{(k+n-1)!}{k!(n-1)!}.
$$

Si podemos verificar que la función que acabamos de definir es biyectiva, entonces podemos concluir que los conjuntos tienen el mismo tamaño. Tenemos dos opciones:

- Verificar que $f$ cumpla con la definición de función biyectiva.
- Verificar que $f$ es invertible.

Para verificar que $f$ tiene un inverso, basta con crear una función que tome la cadena $s$ y regrese la solución a la ecuación a la que corresponde. Definir este inverso es fácil: si cortamos la cadena por cada barra, la cadena queda dividida en $n$ pedazos. La cantidad de estrellas en el $i$-ésimo pedazo es $x_i$.

#### Barras y estrellas con desigualdad
:::success
:information_source: **Problema**
Ahora queremos contar las soluciones a la desigualdad $x_1+x_2+\dots+x_n \leq k$.
:::

:::spoiler Solución
Se usa una barra más y ahora el valor de $x_n$ será la cantidad de estrellas entre la última y penútlima barra. La solución es: $\binom{n+k}{k}$.
:::

#### Barras y estrellas con límite inferior
:::success
:information_source: **Problema**
Contar las soluciones a la igualdad $x_1+x_2+\dots+x_n = k$, tal que se cumpla $l_1 \leq x_1, l_2 \leq x_2, \dots, l_n \leq x_n$.
:::

:::spoiler Solución
Decimos que $x_i=l_i+x'_i$. Tenemos que hallar las soluciones a $(l_1+x'_1)+(l_2+x'_2)+\dots+(l_n+x'_n)=k$, que es lo mismo que $x'_1+x'_2+\dots+x'_n=k-l_1-l_2-\dots-l_n$.
:::

#### Barras y estrellas con límite superior
:::success
:information_source: **Problema**
Contar las soluciones a la igualdad $x_1+x_2+\dots+x_n = k$, tal que se cumpla $u_1 \geq x_1, u_2 \geq x_2, \dots, u_n \geq x_n$.
:::

:::spoiler Solución
Usemos principio de inclusión-exclusión. Sea $A_i$ el número de soluciones a la igualdad que tienen $u_i < x_i$. La solución es $\binom{n+k-1}{k}-|A_1 \cup A_2 \cup \dots \cup A_n|$.
:::

### Fórmula de Cayley
:::success
:information_source: **Problema**
¿Cuántos árboles de $n$ nodos etiquetados y no enraizados hay?

**Límites:**
- $1 \leq n \leq 10^{18}$

**Ejemplo:**
Si $n=2$, hay $1$ árbol.
Si $n=3$, hay $3$ árboles.
Si $n=4$, hay $16$ árboles.

:::

Utilizaremos la **secuencia de Prüfer** para transformar cada árbol en un arreglo de tamaño $n-2$ de la siguiente forma:

1. Inicializar un arreglo vacio $P=[]$
2. Mientras haya más de dos nodos en el árbol:
a. Eliminar la hoja con la etiqueta más pequeña.
b. Insertar la etiqueta del vecino de dicha hoja al final de $P$.
3. Regresar $P$.

El algoritmo nos regresa una arreglo de tamaño $n-2$, donde cada elemento está entre $1$ y $n$. Este arregla se llama la secuencia de Prüfer del árbol de entrada. Es fácil contar la cantidad de dichos arreglos:

$$
n^{n-2}
$$

Para demostrar que es una función biyectiva, describamos su función inversa:

1. Recibir la secuencia $P$.
2. Inicializar un conjunto $S$ que contiene los números entre $1$ y $n$ que no estén en $P$.
3. Incializar un grafo $T$ con $n$ nodos sin aristas.
4. Iterar sobre $i$ desde $i=1$ hasta $i=n-2$
a. Conectar en $T$ el elemento más pequeño de $S$ y $P[i]$.
b. Borrar el elemento más pequeño de $S$.
c. Si $P[i]$ no vuelve a aparecer en el sufijo $P[i+1...n-2]$, insertarlo en $S$.
5. Conectar en $T$ los dos elementos que quedan en $S$.
6. Regresar $T$.

Este algoritmo devuelve el árbol que genera la secuencia de Prüfer dada.

#### Límite en los grados
:::success
:information_source: **Problema**
Contar los árboles no etiquetados y no enraizados tal que sus nodos tienen grado a lo más $k$.
:::

:::spoiler Solución
Notar que un nodo con grado $d$ aparece $d-1$ veces en la secuencia de Prüfer. Usando esta propiedad, la cantidad de árboles que queremos contar es igual a la cantidad de arreglos de tamaño $n-2$ donde ningún elemento aparece más de $k-1$ veces.

Contar dichos arreglos se puede hacer con inclusión exclusión.
:::

#### Formas de convertir grafo en árbol
:::success
:information_source: **Problema**
Dado un grafo no dirigido, contar las formas de agregar aristas para convertir el grafo dado en árbol.
:::

:::spoiler Solución
Si el grafo tiene ciclos, la respuesta es $0$ (un árbol no puede tener ciclos). En caso contario, se deben agregar aristas para conectar las componentes conexas.

Comprimamos las componentes conexas en un nodo. Si hay $c$ componentes conexas, hay $c^{c-2}$ formas de conectar la versión comprimida del grafo, pero notar que esta no es la respuesta a nuestro problema. Digamos que las componentes tienen $b_1, b_2, \dots, b_c$ nodos. Veamos lo que nos falta contar para la respuesta final.

En la función para convertir una secuencia de Prüfer a un árbol, en cada iteración colocamos una arista entre un elemento de la secuencia y el elemento menor del conjunto $S$. Si dichos nodos son $u$ y $v$ respectivamente, tenemos $b_u$ por $b_v$ formas de conectarlos.

Todas las componentes se meterán exactamente una vez al conjunto, por lo que podemos multiplicar $\prod_{i=1}^cb_i$ a la respuesta (la forma de elegir los nodos que se conectarán por cada componente). En cada posición de la secuencia, denemos $b_1+b_2+\dots+b_c=n$ formas de elegir el nodo que se conectará siendo parte del arreglo. Por lo tanto la respuesta es:

$$
n^{c-2} \cdot \prod_{i=1}^c b_i
$$
:::

## Identidades
### Identidad de Vandermonde
:::success
:information_source: **Problema**
Hallar $\sum_{i=0}^k \binom{n}{i}\binom{m}{k-i}$.

**Límites**
- $1 \leq n,m,k \leq 10^7$.

**Ejemplo:**
Si $n=6$, $m=8$ y $k=4$, queremos hallar:
$$
\binom{6}{0}\binom{8}{4}+\binom{6}{1}\binom{8}{3}+\binom{6}{2}\binom{8}{2}+\binom{6}{3}\binom{8}{1}+\binom{6}{4}\binom{8}{0}
$$
Que es igual a $1001$.
:::

Esta suma se puede hallar por interpretación combinatoria. Podemos pensar que cada iteración representa las formas de tomar $i$ objetos de una caja donde hay $n$ objetos y tomar $k-i$ objetos de una caja donde hay $m$ objetos. En cada iteración estamos eligiendo $k$ objetos en total de entre $n+m$ que tenemos disponibles en cada caja. Por lo la respuesta es $\binom{n+m}{k}$.

### $\sum_{i=0}^n \binom{i}{k}$
:::success
:information_source: **Problema**
Hallar $\sum_{i=0}^n \binom{i}{k}$.

**Límites**
- $1 \leq n,k \leq 10^7$.

**Ejemplo:**
Si $n=5$ y $k=2$, queremos hallar:
$$
\binom{0}{2}+\binom{1}{2}+\binom{2}{2}+\binom{3}{2}+\binom{4}{2}+\binom{5}{2}
$$
Que es igual a $20$.
:::