Combinatoria

Por Ariel Parra

La regla de la suma (sum rule)

Si dos conjuntos y son disjuntos (es decir, ), entonces la cantidad total de elementos en la unión de y es igual a la suma de los elementos en y los elementos en , es decir:

En palabras más sencillas: si tenemos formas de realizar la Tarea 1 y formas de realizar la Tarea 2, entonces el número total de formas de elegir una de las dos tareas es igual a .

En general, si hay tareas y la -ésima tarea se puede realizar de maneras, entonces hay formas de hacer una de las tareas.

Ejemplo:

Imagina que tienes 3 sombreros diferentes, 2 camisas diferentes y 4 pantalones diferentes. Si quieres donar uno de los artículos, ¿cuántas formas diferentes hay de hacerlo?
Respuesta:

CPC Γα=Ω5

La regla del producto (product rule)

El número total de elementos en el producto cartesiano de dos conjuntos y es igual al producto del número de elementos en y en , es decir:

En palabras más sencillas: si tenemos formas de realizar la Tarea 1 y formas de realizar la Tarea 2, entonces el número total de formas de hacer ambas tareas es igual a .

En general, si hay tareas y la -ésima tarea se puede realizar de maneras, entonces hay formas de hacer todas las tareas.

Ejemplo:

Imagina que tienes 3 sombreros diferentes, 2 camisas diferentes y 4 pantalones diferentes. Quieres vestirte y, para ello, debes usar 1 sombrero, 1 camisa y 1 pantalón. ¿De cuántas maneras puedes hacerlo?

Solución:

CPC Γα=Ω5

Los 4 Tipos de Permutaciones

  1. Permutación con repetición
    Cuando se pueden repetir elementos en cada posición de la permutación.
    Ejemplo: ¿Cuántos números de 3 dígitos mayores que 500 se pueden formar con los dígitos 3, 4, 5 y 7?
    Solución: El primer dígito debe ser 5 o 7 (2 opciones), y los otros 2 pueden repetirse (4 opciones cada uno). Total de permutaciones: .

  2. Permutación sin repetición
    Cuando no se permiten repeticiones y cada elemento solo puede aparecer una vez en la permutación.
    Ejemplo: ¿Cuántos números de 3 dígitos divisibles por 3 se pueden formar con los dígitos 2, 4, 6 y 8 sin repetición?
    Solución: La suma de los dígitos debe ser divisible por 3. Existen dos combinaciones posibles (2, 4, 6 y 4, 6, 8), con permutaciones cada una. Total: .

CPC Γα=Ω5

  1. r-permutación sin repetición
    Disposición de r elementos de un total de n, sin repetir ningún elemento.
    Ejemplo: Una heladería tiene 10 sabores. ¿Cuántas combinaciones de 3 sabores diferentes se pueden hacer?
    Solución: Para el primer sabor hay 10 opciones, para el segundo 9, y para el tercero 8. Total: . Fórmula general: .

  2. r-permutación con repetición
    Disposición de n elementos en r posiciones, permitiendo que los elementos se repitan.
    Ejemplo: Un policía visita una escena del crimen 3 veces a la semana. ¿Cuántas maneras hay de programar sus visitas sin restricción de días?
    Solución: Para cada visita hay 7 opciones (uno por día de la semana). Total de maneras: .

CPC Γα=Ω5

Definición de Combinatoria

En combinatoria, una combinación de un conjunto de objetos distintos es simplemente el conteo de formas en las que se pueden seleccionar un número específico de elementos de un conjunto de cierto tamaño. En una combinación, el orden de los elementos no importa. Una selección no ordenada de r elementos de un conjunto se llama una r-combinación y se representa como .

Dado que una combinación es simplemente una permutación sin orden, el número de r-combinaciones se puede expresar en términos de r-permutaciones. La r-permutación se puede obtener al primero calcular la r-combinación y luego ordenar los elementos en cada r-combinación, lo cual se puede hacer de maneras.

CPC Γα=Ω5

La relación es:

Usando esta relación, la fórmula para $ C(n, r) $ se obtiene como:

Así, el número de combinaciones de r elementos de un conjunto de n se calcula usando la fórmula:

CPC Γα=Ω5

Ejemplo de combinatoria

Como ejemplo, consideremos el problema de contar el número de formas de representar un número entero como una suma de enteros positivos. Por ejemplo, hay 8 representaciones para el número 4:

Un problema combinatorio como este se puede resolver a menudo usando una función recursiva. En este caso, podemos definir una función que da el número de representaciones de . Según el ejemplo anterior, . Los valores de la función pueden calcularse recursivamente de la siguiente manera:

CPC Γα=Ω5

El caso base es , porque la suma vacía representa el número 0. Luego, si , consideramos todas las formas de elegir el primer número de la suma. Si el primer número es , hay representaciones para la parte restante de la suma. Así, calculamos la suma de todos los valores de la forma donde .

Los primeros valores de la función son:

A veces, una fórmula recursiva puede reemplazarse por una fórmula de forma cerrada. En este problema, la función se puede expresar como:

Esta fórmula se basa en el hecho de que hay posiciones posibles para colocar los signos "+" en la suma, y podemos elegir cualquier subconjunto de esas posiciones.

CPC Γα=Ω5

Coeficientes binomiales

El coeficiente binomial (pronunciado como "n elige k" o, a veces, escrito como ) representa el número de maneras de elegir un subconjunto de elementos de un conjunto de elementos. Por ejemplo, , porque el conjunto (set) tiene subconjuntos (subsets) de elementos:

Hay dos formas de calcular coeficientes binomiales:

  • Método 1: Triángulo de Pascal (DP),
  • Método 2: Definición Factorial (Inversos Modulares),

Ahora veremos la implementación del segundo metodo, ya que es más probable que un problema de coeficientes binomiales tenga numeros grandes y modulos a que sea uno sencillo capaz de correr en .

CPC Γα=Ω5
const int MAXN = 1e6;		const int MOD = 1e9 + 7;
vector<ll> fac(MAXN + 1);		vector<ll> inv(MAXN + 1);
ll exp(ll x, ll n, ll m) {
	x %= m;
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n >>= 1;// n /=2
	}
	return res;
}
void factorial() {
	fac[0] = 1;
	for (int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % MOD; }
}
void inverses() {
	inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD);
	for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % MOD; }
}
ll choose(int n, int r) { return fac[n] * inv[r] % MOD * inv[n - r] % MOD; }
CPC Γα=Ω5

Codigo principal

int main() {
	factorial();
	inverses();
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		cout << choose(a, b) << '\n';
	}
}
CPC Γα=Ω5

Derangements: Inclusion-exclusion principle

Supongamos que tenemos eventos , donde el evento corresponde a que la persona recibe su propio sombrero. Queremos calcular .

Restamos de el número de formas en las que puede ocurrir cada evento; es decir, consideremos la cantidad . Esto subcuenta, ya que estamos restando los casos donde ocurren más de un evento demasiadas veces. Específicamente, para una permutación donde ocurren al menos dos eventos, subcontamos una vez. Entonces, añadimos de nuevo el número de formas en las que ocurren dos eventos. Podemos continuar este proceso para cada tamaño de subconjunto de índices. La expresión queda como:

Para un conjunto de tamaño , el número de permutaciones con al menos índices se puede calcular eligiendo un conjunto de tamaño que sea fijo y permutando los otros índices. En términos matemáticos

CPC Γα=Ω5

Entonces, el problema se reduce a calcular:

En código se vería así:

int main() {
    int n, m;
    cin >> n >> m;

    int c = 1;  // Start with c = 1
    for (int i = 1; i <= n; i++) {
        c = (1LL * c * i) % m;  // Multiply by i and take mod m
        c = (c + (i % 2 == 1 ? -1 : 1) + m) % m;  // Add -1 or +1, and take mod m to handle negatives
        cout << c << ' ';
    }
    cout << endl;
}
CPC Γα=Ω5

Principio del Palomar (Pigeonhole Principle)

El principio del palomar establece que si distribuimos palomas en nidos y , al menos un nido contendrá más de una paloma. En otras palabras, si tienes más objetos que contenedores en los cuales colocarlos, al menos un contenedor debe tener más de un objeto. Este principio se basa en la analogía de palomas (objetos) colocadas en agujeros de palomar (contenedores).

Versión Generalizada del Principio del Palomar

La versión generalizada del principio dice que si distribuimos palomas en nidos, donde , entonces al menos un nido contendrá al menos palomas. Este principio simple tiene numerosas aplicaciones en problemas de combinatoria y teoría de números, aunque a veces no es evidente identificar cómo aplicarlo correctamente, ya que puede ser difícil reconocer qué representan los "nidos" y las "palomas" en cada problema.

CPC Γα=Ω5

Ejemplos del Principio del Palomar

  1. Ejemplo de bolas de colores: Supongamos que tenemos una bolsa con bolas de cinco colores diferentes. ¿Cuál es el número mínimo de bolas que debemos extraer, sin mirarlas, para asegurar que obtenemos dos bolas del mismo color?

    • Aplicación: Aquí, los "nidos" representan los colores de las bolas. Dado que hay cinco colores (5 nidos), si extraemos 6 bolas, al menos dos de ellas serán del mismo color.

  2. Ejemplo de equipos de fútbol: Imagina que equipos de fútbol juegan partidos cada fin de semana, enfrentándose todos contra todos. Demuestra que, al final de cada fin de semana, siempre hay dos equipos que han jugado el mismo número de partidos.

    • Aplicación: Aquí, los "nidos" son las posibles cantidades de partidos que un equipo ha jugado hasta el momento, desde 0 (si no ha jugado) hasta (si ha jugado contra todos los demás). Sin embargo, los valores 0 y son incompatibles porque no puede haber un equipo que haya jugado contra todos mientras otro no ha jugado ningún partido. Por lo tanto, el número de nidos efectivos es . Con equipos y solo nidos posibles, el principio del palomar asegura que al menos dos equipos han jugado el mismo número de partidos.
CPC Γα=Ω5

Numeros de Catalan

Los números de Catalán son una secuencia de números enteros positivos que se utilizan para contar diversas combinaciones posibles en problemas combinatorios. La fórmula general para el término es:

Alternativamente, cada número de Catalán también puede calcularse a partir del término anterior usando:

Los primeros números de Catalán para son: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Los números de Catalán aparecen en muchos problemas de conteo interesantes, tales como:

  1. Contar el número de expresiones con pares de paréntesis correctamente emparejados. Por ejemplo, para , las expresiones posibles son .
  2. Contar el número de árboles de búsqueda binarios posibles con claves.
  3. Contar el número de árboles binarios completos con hojas.
  4. Dado un número , contar el número de formas de dibujar cuerdas en un círculo con puntos de manera que no se crucen dos cuerdas.
CPC Γα=Ω5

Algoritmo para imprimir los primeros n numeros de Catalan

void catalan(int n) {
    int res = 1;
    cout << res << " ";
    // Iterate till n
    for (int i = 1; i < n; i++) {
        // Calculate the ith Catalan number
        res = (res * (4 * i - 2)) / (i + 1);
           cout << res << " ";
    }
}// O(n)
int main() {
    int n = 10;
    catalan(n);
    return 0;
}
CPC Γα=Ω5
CPC Γα=Ω5

Referencias

CPC Γα=Ω5