Combinatoria

Si nunca se ha encontrado combinatoria, AoPS es un buen lugar para empezar.

Recursos
Fuente	Recurso	Notas
AoPS	Alcumus	problemas de práctica; poner el foco en Counting and Probability para los temas del módulo
AoPS	Intro to Counting and Probability	buen libro

Recursos

Recursos
Fuente	Recurso	Notas
CPH	22 - Combinatorics	este módulo se basa en esto
cp-algo	Combinatorics
HE	Basics of Combinatorics	enseña combinatoria fundamental con un problema de práctica al final
AoPS	Introductory Combinatorics	enseña conceptos básicos de combinatoria
AoPS	Intermediate Combinatorics	enseña conceptos más avanzados de combinatoria
CF	Inclusion-Exclusion Principle	un buen blog sobre el principio de inclusión-exclusión

Si se prefiere ver videos, estas son algunas opciones:

Recursos
Fuente	Recurso	Notas
YouTube	Deep Dive into Combinatorics	playlist de mathemaniac
YouTube	MIT 6.042J	clases 16-23
YouTube	Sums and Expected Value #1	video de Errichto sobre valor esperado y sumas de subconjuntos

Coeficientes binomiales

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Binomial Coefficients	Fácil		en el módulo

El coeficiente binomial $\binom{n}{k}$ (se pronuncia ” $n$ en $k$ ” o a veces se escribe como ${}_nC_k$ ) representa el número de formas de elegir un subconjunto de $k$ elementos de un conjunto de $n$ elementos. Por ejemplo, $\binom{4}{2} = 6$ , porque el conjunto $\{1,2,3,4\}$ tiene $6$ subconjuntos de $2$ elementos:

\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}

Hay dos formas de calcular coeficientes binomiales:

Método 1: Triángulo de Pascal (programación dinámica) - $\mathcal{O}(n^2)$

Los coeficientes binomiales se pueden calcular de forma recursiva como sigue:

\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}

La intuición detrás de esto es fijar un elemento $x$ en el conjunto y elegir $k − 1$ elementos de $n − 1$ elementos si $x$ está incluido en el conjunto, o elegir $k$ elementos de $n − 1$ elementos, en caso contrario.

Los casos base de la recursión son:

\binom{n}{0} = \binom{n}{n} = 1

porque siempre hay exactamente una forma de construir un subconjunto vacío y un subconjunto que contiene todos los elementos.

Esta fórmula recursiva se conoce comúnmente como el triángulo de Pascal .

Una implementación naive de esto usaría una fórmula recursiva, como abajo:

C++JavaPython


/** @return nCk mod p using naive recursion */
int binomial(int n, int k, int p) {
	if (k == 0 || k == n) { return 1; }
	return (binomial(n - 1, k - 1, p) + binomial(n - 1, k, p)) % p;
}


/** @return nCk mod p using naive recursion */
public static int binomial(int n, int k, int p) {
	if (k == 0 || k == n) { return 1; }
	return (binomial(n - 1, k - 1, p) + binomial(n - 1, k, p)) % p;
}


def binomial(n: int, k: int, p: int) -> int:
	""":return: nCk mod p using naive recursion"""
	if k == 0 or k == n:
		return 1
	return (binomial(n - 1, k - 1, p) + binomial(n - 1, k, p)) % p

Además, podemos optimizar esto de $\mathcal{O}(2^n)$ a $\mathcal{O}(n^2)$ usando programación dinámica (DP) cacheando los valores de binomiales más pequeños para evitar recalcular los mismos valores una y otra vez. El código de abajo muestra una implementación bottom-up de esto.

C++JavaPython


/** @return nCk mod p using dynamic programming */
int binomial(int n, int k, int p) {
	// dp[i][j] stores iCj
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
 
	// base cases described above
	for (int i = 0; i <= n; i++) {
		/*
		 * i choose 0 is always 1 since there is exactly one way
		 * to choose 0 elements from a set of i elements
		 * (don't choose anything)
		 */
		dp[i][0] = 1;
		/*
		 * i choose i is always 1 since there is exactly one way
		 * to choose i elements from a set of i elements
		 * (choose every element in the set)
		 */
		if (i <= k) { dp[i][i] = 1; }
	}
 
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j <= min(i, k); j++) {
			if (i != j) {  // skips over the base cases
				// uses the recurrence relation above
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % p;
			}
		}
	}
 
	return dp[n][k];  // returns nCk modulo p
}


/** @return nCk mod p using dynamic programming */
public static int binomial(int n, int k, int p) {
	// dp[i][j] stores iCj
	int[][] dp = new int[n + 1][k + 1];
 
	// base cases described above
	for (int i = 0; i <= n; i++) {
		/*
		 * i choose 0 is always 1 since there is exactly one way
		 * to choose 0 elements from a set of i elements
		 * (don't choose anything)
		 */
		dp[i][0] = 1;
		/*
		 * i choose i is always 1 since there is exactly one way
		 * to choose i elements from a set of i elements
		 * (choose every element in the set)
		 */
		if (i <= k) { dp[i][i] = 1; }
	}
 
	for (int i = 0; i <= n; i++) {
		for (int j = 1; j <= Math.min(i, k); j++) {
			if (i != j) {  // skips over the base cases
				// uses the recurrence relation above
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % p;
			}
		}
	}
 
	return dp[n][k];  // returns nCk modulo p
}


def binomial(n: int, k, p):
	""":return: nCk mod p using dynamic programming"""
	# dp[i][j] stores iCj
	dp = [[0] * (k + 1) for _ in range(n + 1)]
 
	# base cases described above
	for i in range(n + 1):
		"""
		i choose 0 is always 1 since there is exactly one way
		to choose 0 elements from a set of i elements
		(don't choose anything
		"""
		dp[i][0] = 1
		"""
		i choose i is always 1 since there is exactly one way
		to choose i elements from a set of i elements
		(choose every element in the set)
		"""
		if i <= k:
			dp[i][i] = 1
 
	for i in range(n + 1):
		for j in range(1, min(i, k) + 1):
			if i != j:  # skips over the base cases
				# uses the recurrence relation above
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % p
 
	return dp[n][k]  # returns nCk modulo p

Método 2: Definición factorial (inversos modulares) - $\mathcal{O}(n + \log MOD)$

Definir $n!$ como $n \times (n - 1) \times (n - 2) \times \ldots 1$ . $n!$ representa el número de permutaciones de un conjunto de $n$ elementos. Ver este artículo de AoPS para más detalles.

Otra forma de calcular coeficientes binomiales es la siguiente:

\binom{n}{k} = \frac{n!}{k!(n-k)!}

Recordemos que $\binom{n}{k}$ también representa el número de formas de elegir $k$ elementos de un conjunto de $n$ elementos. Una estrategia para obtener todas esas combinaciones es recorrer todas las permutaciones posibles de los $n$ elementos, y solo tomar los primeros $k$ elementos de cada permutación. Hay $n!$ formas de hacerlo. Sin embargo, nótese que el orden de los elementos dentro y fuera del subconjunto no importa, así que el resultado se divide por $k!$ y $(n − k)!$ .

Como estos coeficientes binomiales son grandes, los problemas típicamente exigen imprimir la respuesta módulo un primo grande $p$ como $10^9 + 7$ . Por suerte, podemos usar inversos modulares para dividir $n!$ por $k!$ y $(n - k)!$ módulo $p$ para cualquier primo $p$ . Computar factoriales inversos online puede consumir mucho tiempo. En su lugar, podemos precomputar todos los factoriales en tiempo $\mathcal{O}(n)$ y los factoriales inversos en $\mathcal{O}(n + \log MOD)$ . Primero, computamos el inverso modular del factorial más grande usando exponenciación binaria. Para el resto, usamos el hecho de que $(n!)^{-1} \equiv (n!)^{-1}\times (n+1)^{-1} \times (n+1) \equiv ((n+1)!)^{-1}\times (n+1)$ . Ver el código de abajo para la implementación.

C++JavaPython


const int MAXN = 1e6;
 
long long fac[MAXN + 1];
long long inv[MAXN + 1];
 
/** @return x^n modulo m in O(log p) time. */
long long exp(long long x, long long n, long long m) {
	x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
	long long res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}
 
/** Precomputes n! from 0 to MAXN. */
void factorial(long long p) {
	fac[0] = 1;
	for (int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % p; }
}
 
/**
 * Precomputes all modular inverse factorials
 * from 0 to MAXN in O(n + log p) time
 */
void inverses(long long p) {
	inv[MAXN] = exp(fac[MAXN], p - 2, p);
	for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % p; }
}
 
/** @return nCr mod p */
long long choose(long long n, long long r, long long p) {
	return fac[n] * inv[r] % p * inv[n - r] % p;
}


import java.util.*;
 
public class BinomialCoefficients {
	private static final int MAXN = (int)1e6;
	private static long[] fac = new long[MAXN + 1];
	private static long[] inv = new long[MAXN + 1];
 
	/** @return x^n modulo m in O(log p) time. */
	private static long exp(long x, long n, long m) {
		x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
		long res = 1;
		while (n > 0) {
			if (n % 2 == 1) { res = res * x % m; }
			x = x * x % m;
			n /= 2;
		}
		return res;
	}
 
	/** Precomputes n! from 0 to MAXN with a certain modulo. */
	private static void factorial(long p) {
		fac[0] = 1;
		for (int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % p; }
	}
 
	/**
	 * Precomputes all modular inverse factorials
	 * from 0 to MAXN in O(n + log p) time
	 */
	private static void inverses(long p) {
		inv[MAXN] = exp(fac[MAXN], p - 2, p);
		for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % p; }
	}
 
	/** @return nCr mod p */
	private static long choose(long n, long r, long p) {
		return fac[(int)n] * inv[(int)r] % p * inv[(int)(n - r)] % p;
	}
}


MAXN = 10**6
 
fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)
 
 
def exp(x: int, n: int, m: int) -> int:
	""":return: x^n modulo m in O(log p) time."""
	x %= m  # note: m * m must be less than 2^63 to avoid ll overflow
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = (res * x) % m
		x = (x * x) % m
		n //= 2
	return res
 
 
def factorial(p: int):
	"""Precomputes n! from 0 to MAXN."""
	global fac
	fac[0] = 1
	for i in range(1, MAXN + 1):
		fac[i] = (fac[i - 1] * i) % p
 
 
def inverses(p: int):
	"""
	Precomputes all modular inverse factorials from 0 to MAXN in O(n + log p) time
	"""
	global inv
	inv[MAXN] = exp(fac[MAXN], p - 2, p)
	for i in range(MAXN, 0, -1):
		inv[i - 1] = (inv[i] * i) % p
 
 
def choose(n: int, r: int, p: int):
	""":return: nCr mod p"""
	return fac[n] * inv[r] % p * inv[n - r] % p

Solución - Binomial Coefficients

El primer método para calcular factoriales binomiales es demasiado lento para este problema, ya que las restricciones de $a$ y $b$ son $(1 \leq b \leq a \leq 10^6)$ (recordemos que la primera implementación corre en complejidad temporal $\mathcal{O}(n^2)$ ). Sin embargo, podemos usar el segundo método para responder cada una de las $n$ consultas en tiempo constante precomputando factoriales y sus inversos modulares.

C++JavaPython


#include <iostream>
using namespace std;
using ll = long long;
 
const int MAXN = 1e6;
const int MOD = 1e9 + 7;
 
ll fac[MAXN + 1];
ll inv[MAXN + 1];
 
// BeginCodeSnip{Counting functions}
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 /= 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; }
// EndCodeSnip
 
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';
	}
}


import java.io.*;
import java.util.*;
 
public class BinomialCoeffs {
	private static final int MAXN = (int)1e6;
	private static final int MOD = (int)1e9 + 7;
	private static long[] fac = new long[MAXN + 1];
	private static long[] inv = new long[MAXN + 1];
 
	public static void main(String[] args) {
		factorial();
		inverses();
		Kattio io = new Kattio();
		int n = io.nextInt();
		for (int i = 0; i < n; i++) {
			int a = io.nextInt();
			int b = io.nextInt();
			System.out.println(choose(a, b));
		}
	}
 
	// BeginCodeSnip{Counting Functions}
	private static long exp(long x, long n, long m) {
		x %= m;
		long res = 1;
		while (n > 0) {
			if (n % 2 == 1) { res = (res * x) % m; }
			x = (x * x) % m;
			n /= 2;
		}
		return res;
	}
 
	private static void factorial() {
		fac[0] = 1;
		for (int i = 1; i <= MAXN; i++) { fac[i] = (fac[i - 1] * i) % MOD; }
	}
 
	private static void inverses() {
		inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD);
		for (int i = MAXN; i >= 1; i--) { inv[i - 1] = (inv[i] * i) % MOD; }
	}
 
	private static long choose(int n, int r) {
		return (((fac[n] * inv[r]) % MOD) * inv[n - r]) % MOD;
	}
	// EndCodeSnip
 
	// CodeSnip{Kattio}
}


MAXN = 10**6
MOD = 10**9 + 7
 
fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)
 
 
# BeginCodeSnip{Counting Functions}
def exp(x: int, n: int, m: int) -> int:
	x %= m
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * x % m
		x = x * x % m
		n //= 2
	return res
 
 
def factorial():
	fac[0] = 1
	for i in range(1, MAXN + 1):
		fac[i] = fac[i - 1] * i % MOD
 
 
def inverses():
	inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD)
	for i in range(MAXN, 0, -1):
		inv[i - 1] = inv[i] * i % MOD
 
 
def choose(n: int, r: int):
	return fac[n] * inv[r] % MOD * inv[n - r] % MOD
 
 
# EndCodeSnip
 
 
factorial()
inverses()
n = int(input())
for _ in range(n):
	a, b = map(int, input().split())
	print(choose(a, b))

Desarreglos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Montmort Numbers	Fácil		en el módulo

El número de desarreglos (derangements) de $n$ números, expresado como $!n$ , es el número de permutaciones tales que ningún elemento aparece en su posición original. De forma informal, es el número de formas en que $n$ sombreros se pueden devolver a $n$ personas de modo que ninguna persona reciba su propio sombrero.

Método 1: Principio de inclusión-exclusión

Supongamos que tenemos eventos $E_1, E_2, \dots, E_n$ , donde el evento $E_i$ corresponde a que la persona $i$ reciba su propio sombrero. Quisiéramos calcular $n! - \lvert E_1 \cup E_2 \cup \dots \cup E_n \rvert$ .

Restamos de $n!$ el número de formas en que ocurre cada evento; es decir, consideramos la cantidad $n! - \lvert E_1 \rvert - \lvert E_2 \rvert - \dots - \lvert E_n \rvert$ . Esto subcuenta, porque estamos restando demasiadas veces los casos en los que ocurre más de un evento. Específicamente, para una permutación donde ocurren al menos dos eventos, subcontamos en uno. Así, sumamos de vuelta el número de formas en que ocurren dos eventos. Podemos continuar este proceso para cada tamaño de subconjuntos de índices. La expresión queda ahora de la forma:

n! - \lvert E_1 \cup E_2 \cup \dots \cup E_n \rvert = \sum_{k = 1}^n (-1)^k \cdot (\text{número de permutaciones con $k$ puntos fijos})

Para un tamaño de conjunto $k$ , el número de permutaciones con al menos $k$ índices se puede computar eligiendo un conjunto de tamaño $k$ que quedan fijos, y permutando los otros índices. En términos matemáticos:

{n \choose k}(n-k)! = \frac{n!}{k!(n-k)!}(n-k)! = \frac{n!}{k!}

Así, el problema pasa a ser computar

n!\sum_{k=0}^n\frac{(-1)^k}{k!}

lo cual se puede hacer en tiempo lineal.

C++JavaPython


#include <atcoder/modint>
#include <bits/stdc++.h>
 
using namespace std;
using mint = atcoder::modint;
 
int main() {
	int n, m;
	cin >> n >> m;
	mint::set_mod(m);
 
	mint c = 1;
	for (int i = 1; i <= n; i++) {
		c = (c * i) + (i % 2 == 1 ? -1 : 1);
		cout << c.val() << ' ';
	}
	cout << endl;
}


import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
 
		long c = 1;
		for (int i = 1; i <= n; i++) {
			c = (c * i) + (i % 2 == 1 ? -1 : 1);
			c %= m;
			c += m;
			c %= m;
			System.out.print(c + " ");
		}
		System.out.println();
	}
}


n, m = map(int, input().split())
c = 1
for i in range(1, n + 1):
	c = (c * i) + (-1 if i % 2 == 1 else 1)
	c %= m
	c += m
	c %= m
	print(c, end=" ")
 
print()

Método 2: Programación dinámica

Supongamos que la persona 1 recibió el sombrero de la persona $i$ . Hay dos casos:

Si la persona $i$ recibe el sombrero de la persona 1, entonces el problema se reduce a un subproblema de tamaño $n - 2$ . Hay $n - 1$ posibilidades para $i$ en este caso, así que sumamos a la respuesta actual $(n - 1)\cdot !(n - 2)$ .
Si la persona $i$ no recibe el sombrero de la persona 1, entonces podemos reasignar el sombrero de la persona 1 para que sea el sombrero de la persona $i$ (si recibieron el sombrero de la persona 1, esto se convertiría en el primer caso). Así, esto se vuelve un subproblema de tamaño $n - 1$ , y hay $n - 1$ formas de elegir $i$ .

Así, tenemos

!n = (n - 1)(!(n - 2) + !(n - 1))

que se puede computar en tiempo lineal con DP. Los casos base son que $!0 = 1$ y $!1 = 0$ .

C++JavaPython


#include <atcoder/modint>
#include <bits/stdc++.h>
 
using namespace std;
using mint = atcoder::modint;
 
int main() {
	int n, m;
	cin >> n >> m;
	mint::set_mod(m);
 
	mint a = 1, b = 0;
	cout << 0 << ' ';
 
	for (int i = 2; i <= n; i++) {
		mint c = (i - 1) * (a + b);
		cout << c.val() << ' ';
		a = b;
		b = c;
	}
	cout << endl;
}


import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
 
		int a = 1;
		int b = 0;
 
		System.out.print("0 ");
		for (int i = 2; i <= n; i++) {
			int c = (int)(((long)(i - 1) * (a + b)) % m);
			System.out.print(c + " ");
			a = b;
			b = c;
		}
		System.out.println();
	}
}


n, m = map(int, input().split())
a, b = 1, 0
 
print(0, end=" ")
for i in range(2, n + 1):
	c = (i - 1) * (a + b) % m
	print(c, end=" ")
	a, b = b, c
 
print()

Estrellas y barras

Recursos
Fuente	Recurso	Notas
cp-algo	Stars and bars
Medium	The Stars and Bars Formula	Artículo bien documentado.

Estrellas y barras es un método útil en combinatoria que consiste en agrupar objetos indistinguibles en cajas distinguibles. El número de formas de poner $n$ objetos indistinguibles en $k$ cajas distinguibles es:

\binom{n+k-1}{n}=\binom{n+k-1}{k-1}

El segundo coeficiente binomial de arriba se puede derivar de la propiedad de los coeficientes binomiales: $\binom{n}{k}=\binom{n}{n-k}$ .

Veamos un ejemplo particular para $n=3$ y $k=2$ que tiene $4$ posibilidades. Como el nombre indica, la visualización suele hacerse con estrellas separadas en grupos por barras:

||\bigstar \bigstar \bigstar \\ |\bigstar |\bigstar \bigstar \\ |\bigstar \bigstar| \bigstar \\ \bigstar \bigstar \bigstar || \\

Como probablemente se habrá notado, puede haber cajas vacías: cuando ponemos todas las estrellas en la primera o en la segunda caja. Puede haber casos en los que todas las cajas deban ser no vacías. En ese caso, el número de formas de poner $n$ objetos indistinguibles en $k$ cajas distinguibles no vacías es: $\binom{n-1}{k-1}$

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	SPOJ	MARBLES - Marbles	Fácil		en el módulo

Explicación

Para este problema deberíamos pensar al revés: digamos que los $k$ colores de los que elegimos son de hecho cajas y, en lugar de elegir $n$ canicas, las ponemos en las cajas respectivas. El problema tiene la restricción de que debemos tomar al menos una canica de cada tipo, lo que en nuestra nueva perspectiva significa que todas las cajas deben ser no vacías. Así, la respuesta se obtiene con la segunda fórmula: $\binom{n-1}{k-1}$

Implementación

Complejidad temporal: $\mathcal{O}(T \cdot K)$

C++Python


#include <iostream>
 
/** @return n choose k, computed naively since the problem has no overflow */
long long comb(int n, int k) {
	if (k > n - k) { k = n - k; }
	long long ret = 1;
	for (int i = 0; i < k; i++) {
		// this is done instead of *= for divisibility issues
		ret = ret * (n - i) / (i + 1);
	}
	return ret;
}
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int marble_num;
		int color_num;
		std::cin >> marble_num >> color_num;
		std::cout << comb(marble_num - 1, color_num - 1) << '\n';
	}
}


from math import comb
 
ans = []
for _ in range(int(input())):
	marble_num, color_num = [int(i) for i in input().split()]
	ans.append(str(comb(marble_num - 1, color_num - 1)))
 
print("\n".join(ans))

Valor esperado

Recursos
Fuente	Recurso	Notas
Brilliant	Expected Value	muchos ejemplos de matemática pura de valor esperado + explicaciones
Brilliant	Linearity of Expectation	muchos ejemplos de matemática pura de linealidad de la esperanza + explicaciones
CF	Expected Value	un buen blog sobre el valor esperado

Un valor esperado es la media teórica de una distribución de probabilidad. Una variable aleatoria se usa para representar una posible distribución de probabilidad. Sea $X$ una variable aleatoria y $P(X = x)$ la probabilidad de que el resultado de la variable aleatoria $X$ sea $x$ . Entonces, el valor esperado de $X$ , denotado $E[X]$ , es

\sum_x x \cdot P(X = x)

Por ejemplo, sea $X$ la distribución de probabilidad de un dado justo de 6 caras. $P(X = x)$ es $\frac{1}{6}$ para $1 \leq x \leq 6$ . Usando la fórmula, obtenemos $E[X] = \frac{21}{6} = \frac{7}{2}$ .

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Candy Lottery	Fácil		en el módulo

Explicación

Sea $X$ la distribución de probabilidad del número máximo de caramelos que recibe un niño. Para obtener $E[X]$ , necesitamos $P(X = x)$ para $1 \leq x \leq k$ . $(\frac{x}{k})^n$ es la probabilidad de que cada niño reciba a lo sumo $x$ caramelos. Para obtener $P(X = x)$ , debemos restar la probabilidad de que cada niño reciba estrictamente menos de $x$ caramelos, que es $(\frac{x - 1}{k})^n$ .

Por lo tanto, $P(X = x) = (\frac{x}{k})^n - (\frac{x - 1}{k})^n$ , lo que nos permite calcular $E[X]$ .

Implementación

Complejidad temporal: $\mathcal{O}(k)$ (asumiendo que la potencia corre en tiempo constante).

(Opcional) ¿Por qué hay que manejar un caso de forma especial?

Consideremos el siguiente fragmento de código:


#include <iomanip>
#include <iostream>
 
int main() {
	double ans = 9.1919575;
	std::cout << std::fixed << std::setprecision(6) << ans << "\n";
}
 
// Output: 9.191957

¿Por qué el número $9.1919575$ parece redondear hacia abajo cuando se supone que debería redondear hacia arriba? La razón es que no se puede representar exactamente en un double, así que $ans$ guarda en su lugar el double más cercano, y ese double resulta ser menor. De hecho, si aumentamos la precisión de 6 a 15 al imprimir, obtenemos la siguiente salida: $9.191957499999999$ .

En general, una fracción $a/b$ no se puede representar exactamente en un double a menos que $b$ sea una potencia de dos.

Imprimamos todos los casos donde esto podría ser un problema. En el siguiente código, $dif$ es la diferencia entre la respuesta computada por nuestra solución y el número más cercano de la forma x.xxxxxx5.


#include <bits/stdc++.h>
 
using namespace std;
 
double solve_orig(int n, int k) {
	double expect_max = 0;
	for (int i = 1; i <= k; i++) {
		expect_max += i * (pow((double)i / k, n) - pow((double)(i - 1) / k, n));
	}
	return expect_max;
}
 
int main() {
	vector<pair<double, pair<int, int>>> by_dif;
	for (int n = 1; n <= 100; ++n)
		for (int k = 1; k <= 100; ++k) {
			double a = solve_orig(n, k);
			double b = 1e6 * a - 0.5;
			double dif = abs(b - round(b)) / 1e6;
			by_dif.push_back({dif, {n, k}});
		}
	sort(begin(by_dif), end(by_dif));
	by_dif.resize(10);
 
	for (auto [d, p] : by_dif) {
		cout << "dif = " << d << " n = " << p.first << " " << "k = " << p.second
		     << "\n";
 
		stringstream ss;
		ss << fixed << setprecision(15) << solve_orig(p.first, p.second);
		cout << ss.str() << "\n\n";
	}
}

Salida:


dif = 0 n = 2 k = 64
43.164062500000000

dif = 0 n = 3 k = 32
24.492187500000000

dif = 0 n = 4 k = 4
3.617187500000000

dif = 0 n = 7 k = 2
1.992187500000000

dif = 0 n = 7 k = 10
9.191957499999999

dif = 1.86265e-15 n = 4 k = 20
16.483337500000001

dif = 3.12328e-11 n = 33 k = 62
60.632305500031237

dif = 1.14784e-10 n = 64 k = 98
96.938251499885212

dif = 1.89349e-10 n = 27 k = 71
68.932663499810644

dif = 2.14219e-10 n = 53 k = 17
16.958418499785783

Si miramos las diferencias más pequeñas, notamos que $(n,k)\in \{(7,10), (4,20)\}$ son los dos primeros casos donde la respuesta no se puede representar exactamente en un double. $(4,20)$ resulta no ser un problema, pero $(7,10)$ sí lo es.

C++Python


#include <cmath>
#include <iomanip>
#include <iostream>
 
using std::cout;
using std::endl;
 
int main() {
	int n;
	int k;
	std::cin >> n >> k;
 
	double expect_max = 0;
	for (int i = 1; i <= k; i++) {
		expect_max += i * (pow((double)i / k, n) - pow((double)(i - 1) / k, n));
	}
 
	if (n == 7 && k == 10) expect_max += 1e-12;  // fix rounding for edge case
 
	cout << std::setprecision(6) << std::fixed;  // set output precision
	cout << expect_max << endl;
}


n, k = [int(i) for i in input().split()]
 
expected_max = 0
for c in range(1, k + 1):
	expected_max += c * ((c / k) ** n - ((c - 1) / k) ** n)
 
if n == 7 and k == 10:
	expected_max += 1e-12
 
print(f"{expected_max:.6f}")

Linealidad de la esperanza

La linealidad de la esperanza afirma que $E[X + Y] = E[X] + E[Y]$ sin importar si $X$ e $Y$ son independientes entre sí. Por ejemplo, si en un cierto día Alicia va al gimnasio con probabilidad $\frac{1}{10}$ y su esposo Bob va al gimnasio con probabilidad $\frac{3}{10}$ , el número esperado de visitas al gimnasio en un cierto día entre la pareja es $\frac{1}{10} + \frac{3}{10} = \frac{2}{5}$ . Esto funciona aunque las decisiones de una persona puedan afectar a la otra.

Esto se puede generalizar a una secuencia de variables aleatorias $X_1, X_2, \dots, X_n$ y constantes arbitrarias $c_1, c_2, \dots, c_n$ :

E\left[\sum_{i = 1}^{n} c_iX_i \right] = \sum_{i = 1}^{n}c_i \cdot E[ X_i]

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	AC	Erasing Vertices	Normal		en el módulo

Explicación

Aunque esto pueda parecer imposible a primera vista dada la cantidad de secuencias distintas de operaciones, la linealidad de la esperanza nos permite descomponer el valor esperado en la suma de partes más pequeñas.

Podemos descomponer esto partiendo la variable aleatoria inicial en las sumas de varias variables aleatorias indicadoras. Sea $X_u$ una variable que indica si el nodo $u$ fue marcado de forma explícita para eliminación. Como es básicamente un booleano, solo puede tomar $0$ o $1$ , lo que también significa que la probabilidad de que sea $1$ es igual a su valor esperado.

Ahora, consideremos cómo una operación afecta al nodo $u$ .

O bien elige un nodo que no puede alcanzar $u$ , y no pasa nada en lo que respecta a $u$ .
Elige al propio $u$ , haciendo que la variable indicadora sea $1$ .
Elige otro nodo que puede alcanzar $u$ , haciendo que la variable indicadora sea $0$ . Como todos los nodos tienen la misma chance de ser elegidos, la chance de que $X_u=1$ es $\frac{1}{a_u}$ , donde $a_u$ es el número de nodos que pueden alcanzar $u$ incluyendo al propio $u$ .

Juntamos de nuevo los valores esperados de todas las variables indicadoras, lo que nos da la respuesta final.

Implementación

Complejidad temporal: $\mathcal{O}(N^3)$ usando un DFS o BFS naive.

C++Python


#include <iomanip>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int n;
	std::cin >> n;
	vector<vector<int>> adj(n, vector<int>(n));
	for (int n1 = 0; n1 < n; n1++) {
		for (int n2 = 0; n2 < n; n2++) {
			char connected;
			std::cin >> connected;
			adj[n1][n2] = connected == '1';
		}
	}
 
	// reach_from[i] = the # of nodes that have a path to i
	vector<int> reach_from(n);
	for (int start = 0; start < n; start++) {
		vector<int> todo{start};
		vector<bool> visited(n, false);
		visited[start] = true;
		while (!todo.empty()) {
			int curr = todo.back();
			todo.pop_back();
			for (int i = 0; i < n; i++) {
				if (!visited[i] && adj[curr][i]) {
					visited[i] = true;
					reach_from[i]++;
					todo.push_back(i);
				}
			}
		}
	}
 
	double expected_ops = 0;
	for (int i : reach_from) { expected_ops += 1.0 / (i + 1); }
 
	cout << std::setprecision(15) << expected_ops << endl;
}


n = int(input())
 
adj = [[] for _ in range(n)]
for i in range(n):
	for v, c in enumerate(input()):
		if c == "1":
			adj[i].append(v)
 
# reach_from[i] = the # of nodes that have a path to i
reach_from = [0 for _ in range(n)]
for start in range(n):
	todo = [start]
	visited = [False for _ in range(n)]
	visited[start] = True
	while todo:
		curr = todo.pop()
		for next_ in adj[curr]:
			if not visited[next_]:
				visited[next_] = True
				reach_from[next_] += 1
				todo.append(next_)
 
expected_ops = 0
for i in reach_from:
	expected_ops += 1 / (i + 1)
 
print(expected_ops)

Productos esperados

La linealidad de la esperanza trata $E[X + Y]$ , pero ¿qué hay de $E[X \cdot Y]$ ?

$E[X \cdot Y] = E[X] \cdot E[Y]$ si $X$ e $Y$ son independientes entre sí. Podemos reconsiderar el ejemplo de un dado justo de 6 caras para mostrar que $E[X^2] \neq E[X]^2$ . Sabemos que $E[X] = \frac{7}{2}$ , así que $E[X]^2 = \frac{7}{2} \cdot \frac{7}{2} = \frac{49}{4}$ .

Por otro lado,

E[X^2] = \sum_x x^2 \cdot P(X = x) = \frac{1 + 4 + 9 + 16 + 25 + 36}{6} = \frac{91}{6}.

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	★ Creating Strings II	Fácil	Combinatorics	Solución
CSES	Distributing Apples	Fácil	Combinatorics	Solución
CF	Almost Identity Permutations	Fácil	Combinatorics	Solución
CF	Close Tuples	Fácil	Combinatorics, Binary Search	Solución
Bronze	Just Stalling	Fácil	Combinatorics	Solución
CF	AND-array	Fácil	Combinatorics	—
Bubble Cup	Bots	Normal	Combinatorics	Solución
CSES	Xor Pyramid	Normal	Combinatorics, Bitwise	Solución
CF	Med and Mex	Normal	Combinatorics	Solución
AC	Strivore	Normal	Combinatorics	Solución
Gold	Moo Route	Normal	Combinatorics	Solución
Gold	Cowpatibility	Normal	PIE, Bitset	Solución
CF	Arena	Normal	Combinatorics, DP	Solución
Gold	★ Help Yourself	Normal	Combinatorics, Prefix Sums	Solución
CF	Fancy Stack	Difícil	Combinatorics, DP	Solución
Gold	Cow Camp	Difícil	Combinatorics, Probability, Math, Binary Search	Solución

Combinatoria

Recursos

Coeficientes binomiales

Método 1: Triángulo de Pascal (programación dinámica) - O(n2)\mathcal{O}(n^2)O(n2)

Método 2: Definición factorial (inversos modulares) - O(n+log⁡MOD)\mathcal{O}(n + \log MOD)O(n+logMOD)

Solución - Binomial Coefficients

Desarreglos

Método 1: Principio de inclusión-exclusión

Método 2: Programación dinámica

Estrellas y barras

Explicación

Implementación

Valor esperado

Explicación

Implementación

Linealidad de la esperanza

Explicación

Implementación

Productos esperados

Problemas

Método 1: Triángulo de Pascal (programación dinámica) - $\mathcal{O}(n^2)$

Método 2: Definición factorial (inversos modulares) - $\mathcal{O}(n + \log MOD)$