Coeficiente binomial en el principio de inclusión-exclusión

Question

Supongamos que n personas dejan sus abrigos en el guardarropa, pero al salir el supervisor devuelve aleatoriamente cualquier abrigo a cada persona. Ahora, para determinar el número de permutaciones en las que s personas reciben su abrigo, existe la fórmula:

$$\sum\limits_{t=s}^{n}(-1)^{t-s}\binom{t}{s}\binom{n}{t}(n-t)!.$$

Ahora me gustaría entender la fórmula. Para hacer esto, consideraré el caso n=3 y s=1 para poder ilustrar esto y determinar el subconjunto: N$_{1}$\={Listas con 1 en la posición 1} (es decir: la persona 1 recibe su abrigo de vuelta). N$_{2}$ = {Listas con 2 en la posición 2} y N$_{3}$ = {Listas con 3 en la posición 3}

Luego

$$\sum\limits_{t=1}^{3}(-1)^{t-1}\binom{t}{1}\binom{3}{t}(3-t)! = \binom{1}{1}\binom{3}{1}(3-1)! - \binom{2}{1}\binom{3}{2}(3-2)! + \binom{3}{1}\binom{3}{3}(3-3)!.$$

Ahora consideremos una multiplicación: Por ejemplo $\binom{1}{1}\binom{3}{1}(3-1)!$.

La parte $\binom{3}{1}(3-1)!$ significa: Creo que esto es lo mismo que |N$_{1}$|+|N$_{2}$|+|N$_{3}$| y eso significa que fijamos 1 de 3 por eso $\binom{3}{1}$ y los otros 3-1 elementos pueden estar en cualquier lugar, eso significa (3-1)!

Sé que el principio de inclusión-exclusión se aplica aquí.

Ahora intento entender el coeficiente $\binom{1}{1}$ o en general, ¿cómo puedo imaginar el coeficiente $\binom{t}{s}$.

Estoy muy agradecido si puedes explicarme esto.

Answer 1

$\binom{n}{t}\binom{t}{s}$ cuenta el número de pares de conjuntos $(T,S)$ tal que $S\subseteq T\subseteq \{1,2,\dots,n\}$ y $|S|=s,|T|=t.$

Esto se puede demostrar eligiendo $T$ de $\binom{n}t$ formas, luego eligiendo $S$ de $T$ de $\binom{t}s$ formas.

Entonces puedes reescribir tu fórmula como:

$$\sum_{|S|=s}\sum_{T\supseteq S} (-1)^{|T|-s}(n-|T|)!$$

Esencialmente, para un $S$ fijo, $$\sum_{T\supseteq S}(-1)^{|T|-s}(n-|T|)!$$ es el número de formas en las que exactamente las personas en el conjunto $S$ recuperan sus abrigos.

El término $(n-|T|)!$ cuenta todas las permutaciones que devuelven los abrigos a al menos las personas en $T.$ Básicamente, permutaciones que son la identidad en $T$ y cualquier permutación de los $n-|T|$ elementos restantes.

Es más fácil explicar esta fórmula si recuerdas que:

$$\binom{n}{t}\binom ts=\binom ns\binom{n-t}{t-s}$$

Puedes ver que el lado derecho es el número de formas de elegir primero $S$, y el número de formas de elegir $t-s$ elementos adicionales para agregar a $S$ y obtener $T.$

Luego, tu fórmula se convierte, dejando $r=t-s,$ $$\binom{n}s\sum_{r=0}^{n-s}(-1)^r\binom{n-s}{r}(n-s-r)!$$

Ahora el factor $\binom ns$ corresponde a elegir solo un conjunto de $s$ personas que queremos que sean exactamente quienes recuperan sus abrigos, y la suma sobre $r$ corrige los casos en los que al menos $|S|$ más un adicional $r$ recuperaron su abrigo.

Pero en la fórmula original, $\binom nt$ corresponde al número de formas de elegir $T,$ y $\binom ts$ corresponde al número de $S$ que hemos contado de más o de menos en nuestra inclusión-exclusión para permutaciones que fijan $T.$