¿Inclusión/exclusión, al menos y exactamente arreglos?

Términos utilizados en la respuesta:

1. $A_k$: El conjunto de elementos tiene (al menos) propiedad indexada$k$.
2. IEP por el Principio de Inclusión-Exclusión.
3. Exactamente ninguno IEP: exactamente ninguna de las propiedades indexadas se seleccionó a través del IEP. es decir

$$\begin{align} \bigcap_{k=1}^{m}{\overline{A_k}} \end{align}$$

---

Respuesta larga para entender los dos coeficientes:

1. definamos$S_m$: Es una abreviatura para simplificar la fórmula del IEP. Suponga que hay$n$propiedades en total, y$I$es un conjunto de índices, entonces podemos elegir cualquier$m\le n$:

   $$\begin{align} S_m&=\sum\left|\textrm{an intersection of }m\textrm{ sets}\right|\\ &=\sum_{|I|=m}\left|\bigcap_{j\in I}A_j\right| \end{align}$$

2. $E_0$da exactamente-ninguno IEP: (Vamos$S_0=U$):

   $$\begin{align}E_0 &=\sum_{j=0}^n(-1)^{j-0}{j\choose 0}S_j\\ &=\sum_{j=0}^{n}(-1)^{j}S_j\\ &=\left|\bigcap_{j=1}^n\bar{A_j}\right|.\\ \end{align}$$

   para cada$S_j$, el coeficiente es$(-1)^j$:

   $$\begin{align} E_0&=\sum_{j=m}^n(-1)^{j-m}{j\choose m}S_j, m=0\\ &=\sum_{j=0}^n(-1)^{j-0}{j\choose 0}S_j\\ &=\sum_{j=0}^{n}(-1)^{j}S_j. \end{align}$$

   El${j\choose m}$desaparece en$E_0$. Pero para$E_m$, tenemos más que eso. Así que tal vez haya más de un IEP exactamente ninguno en$E_m$?

3. Mi intento de explicar$E_m$:

   $$E_0=\sum_{j=m}^n(-1)^{j-m}{j\choose m}S_j\\ $$

   3.1. Observe el primer término,$j=m$. Ahora$S_m$da:

   $$\begin{align} S_m&=\sum_{|I|=m}\left|\bigcap_{j\in I}A_j\right|\\ &=A_{1,2,...,m} + A_{1,2,...,(m-1),(m+1)} + ... + A_{(n-m+1),(n-m+2),...,n}\\ \end{align}\\ $$

   3.2. Ahora calculamos$E_0$una vez por cada termino$A_{...}$como el universo. Entonces tenemos: (La notación$E_{0,U}$dónde$U$significa el universo definido para el cálculo)

   $$\begin{align} E_{0,A_{1,2,...,m}}&=\sum_{j=m+1}^n(-1)^{j-m}S_j\\ E_{0,A_{1,2,...,(m-1),(m+1)}}&=\sum_{j=m+1}^n(-1)^{j-m}S_j\\ \vdots\\ E_{0,A_{(n-m+1),(n-m+2),...,n}}&=\sum_{j=m+1}^n(-1)^{j-m}S_j\\ \end{align}$$

   es posible que tenga muchas preguntas en esta etapa:

   Q1:

   Aquellos$A_{...}$podría superponerse a algunos de los otros?

   Sí. Pero si cada uno$E_{0, A_{\dots}}$trabajo, sin superposición. Porque$E_m$significa exactamente-m propiedades cuando se completa el cálculo.

   Q2:

   Cada$E_0$, haciendo caso omiso de los$(-1)^{j-m}$, tener$1$para cada término. Ahora estás tratando de convencerme de que aplicarlo muchas veces creará${j\choose m}$, una variable para cada término de la resultante$E_m$? Por intuición, si lo aplicas, di$5$veces, usted debe tener un$5$para cada termino?

   Sí. No sé cómo explicar esto tampoco por ahora.

4. Ahora, el paso más extraño, no puedo creerlo también:

   Intentemos calcular cuántos$S_j$se necesitan cuando$j$es dado. Esto es equivalente a encontrar cuántos universos incluyen cada uno de ellos . Así que aquí está el término:

   $${j\choose m}$$

   dado cualquier$j$propiedades, tu eliges$m$de ellos, encuentras un universo, es decir, un lado izquierdo en la lista de 3.2. que lo incluye en el lado derecho. Esto explica el misterioso${j\choose m}$de$E_m$.

5. Por otra parte, la fórmula de$L_m$(Cuenta los elementos incluidos en$\ge m$conjuntos) es:

   $$\begin{align} L_m&=\sum_{k=m}^nE_k\\ &=\sum_{k=m}^n\sum_{j=k}^n(-1)^{j-k}\binom{j}{k}S_j\\ &=\sum_{j=m}^n(-1)^j\sum_{k=m}^j(-1)^k\binom{j}{k}S_j\\ &=\sum_{j=m}^n(-1)^j\sum_{k=m}^j(-1)^k\left[(-1)^{k-m}\binom{-1}{k-m}\right]\binom{j}{j-k}S_j\\ &=\sum_{j=m}^n(-1)^{j-m}\binom{j-1}{j-m}S_j\quad\quad\square \end{align}$$

   Entonces$L_m$ suma los coeficientes de$E_m$.

---

La versión rigurosa de la explicación se puede encontrar en la pregunta vinculada: Combinatorics significado de$L_m=\sum_{j=m}^{n}(-1)^{j-m}\binom{j-1}{m-1}S_j$.

Para analizar la relación entre$E_m, L_m$y$S_m$es conveniente echar un vistazo más de cerca a los conjuntos que forman los bloques de construcción de estos números.

En el caso del problema (a) se reduce a mostrar que de acuerdo con la fórmula de$E_m$

$$\begin{align*} \color{blue}{E_2}&=\sum_{j=2}^4(-1)^{j-2}\binom{j}{2}S_j\\ &\,\,\color{blue}{=S_2-\binom{3}{1}S_3}+\color{blue}{\binom{4}{2}S_4}\tag{1} \end{align*}$$ y también queremos aclarar cómo derivar los coeficientes binomiales$\binom{3}{1}$y$\binom{4}{2}$.

El ajuste:

• Dada la palabra ARREGLO , consideramos el conjunto

  $$\begin{align*} X=\{\mathrm{AAEEGMNNRRT},\ldots,\mathrm{ARRANGEMENT},\ldots,\mathrm{TRRNNMGEEAA}\} \end{align*}$$ que consiste en$\frac{11!}{\left(2!\right)^4}=2\,494\,800$permutaciones con repeticiones de las letras de esta palabra.

• Introducimos un conjunto$U$de propiedades

  $$\begin{align*} U=\{P_A,P_E,P_N,P_R\} \end{align*}$$ una palabra en$X$tiene propiedad$P_A\in U$si la letra A ocurre consecutivamente y el significado de las otras propiedades en$U$es de manera análoga.

Dado un conjunto de$T\subseteq U$de propiedades de$U$definimos

• $E(T)$como el número de palabras en$X$que tienen exactamente las propiedades$T\subseteq U$, y

• $L(T)$como el número de palabras en$X$que tienen al menos las propiedades$T\subseteq U$.

Entonces, por ejemplo$\mathrm{ARRANGEMENT}$contribuye a$E(\{P_R\})$y$L(\{P_R\})$, mientras$\mathrm{AAEEGMNNRRT}$contribuye a$L(\{P_R\})$y$U$, pero no a$E(\{P_R\})$.

Los números$E(T)$y$L(T)$formar bloques de construcción para$E_m$y$L_m$. Desde que tenemos

• $E_m$es el número de palabras que tienen exactamente $m$propiedades de$U, (0\leq m\leq 4)$y

• $L_m$es el número de palabras que tienen al menos $m$propiedades de$U, (0\leq m\leq 4)$

podemos escribir estas cantidades como

$$\begin{align*} \color{blue}{E_m}&\color{blue}{=\sum_{{T\subseteq U}\atop{|T|=m}}E(T)}\tag{2.1}\\ \color{blue}{L_m}&\color{blue}{=\sum_{{T\subseteq U}\atop{|T|\geq m}}E(T)}\tag{2.2}\\ \end{align*}$$

Ejemplo$m=2$:

En el caso$m=2$tenemos según (2.1)

$$\begin{align*} E_2&=\sum_{{T\subseteq U}\atop{|T|=2}}E(T)\\ &=E(\{P_A,P_E\})+E(\{P_A,P_N\})+E(\{P_A,P_R\})\\ &\qquad + E(\{P_E,P_N\})+E(\{P_E,P_R\})+E(\{P_N,P_R\})\\ &=\binom{4}{2}E(\{P_A,P_E\}) \end{align*}$$ donde el factor$\binom{4}{2}=6$se puede tomar gracias a la simetría de las palabras con sus respectivas propiedades. Para$L_2$obtenemos de acuerdo con (2.2) $$\begin{align*} L_2&=\sum_{{T\subseteq U}\atop{|T|\geq 2}}E(T) =\sum_{j=2}^{4}\sum_{{T\subseteq U}\atop{|T|=j}}E(T)\\ &=E_2+E_3+E_4\tag{2.3} \end{align*}$$

El escenario continuó:

Ahora echamos un vistazo más de cerca a las cantidades.$S_m$. se calculan para$0\leq m\leq 4$como

$$\begin{align*} S_m=\frac{(11-2\times m+m)!}{(2!)^{4-m}}\binom{4}{m}\tag{2.4} \end{align*}$$ y su significado es:

• $S_m$es el número de palabras en$X$, de modo que para cada subconjunto$T\subseteq U$de propiedades con tamaño$|T|=m$tomamos el número de palabras que tienen al menos $m$propiedades de$T\subseteq U$, es decir $$\begin{align*} \color{blue}{S_m=\sum_{{T\subseteq U}\atop{|T|=m}}L(T)}\tag{2.5} \end{align*}$$ En efecto, tomando por ejemplo$m=2$en (2.4) tenemos $$\begin{align*} S_2=\frac{(11-2\times 2+2)!}{(2!)^{4-2}}\binom{4}{2} \end{align*}$$ donde el factor$\binom{4}{2}$representa cada subconjunto$T\subseteq U$de propiedades con tamaño$|T|=2$, mientras que el factor$(11-2\times 2+2)!$en el numerador representa el número de permutaciones de las otras letras además de los dos pares seleccionados. Como hay dos letras más que ocurren dos veces, tenemos que dividir por$2^{4-2}=4$ya que no se pueden distinguir.

$S_m$se da en (2.5) en términos de$L(T)$. Podemos encontrar una representación más conveniente en términos de$E(T)$como sigue. tenemos por si acaso$m=2$:

$$\begin{align*} \color{blue}{S_2}=\color{blue}{\sum_{{T\subseteq U}\atop{|T|=2}}L(T)} &=\sum_{{T\subseteq R\subseteq U}\atop{|T|=2}}E(R)\\ &=\sum_{R\subseteq U}E(R)\sum_{{T\subseteq R}\atop{|T|=2}}1\\ &=\sum_{R\subseteq U}E(R)\binom{|R|}{2}\\ &=\sum_{j=2}^4\sum_{{R\subseteq U}\atop{|R|=j}}E(R)\binom{j}{2}\\ &=\sum_{j=2}^4\binom{j}{2}E_j\\ &\,\,\color{blue}{=E_2+\binom{3}{2}E_3+\binom{4}{2}E_4}\tag{2.6} \end{align*}$$

En esta respuesta se da una derivación de (2.6) en un contexto más general .

Respuesta de (a) y (b):

Encontramos de la misma manera que en (2.4) las siguientes identidades:

$$\begin{align*} S_2&=\sum_{j=2}^4\binom{j}{2}E_j=E_2+\binom{3}{2}E_3+\binom{4}{2}E_4\tag{3.1}\\ S_3&=\sum_{j=3}^4\binom{j}{3}E_j=E_3+\binom{4}{3}E_4\tag{3.2}\\ S_4&=\sum_{j=4}^4\binom{j}{4}E_j=E_4\tag{3.3} \end{align*}$$ Estas relaciones nos permiten representar$E_2$en términos de$S_2, S_3$y$S_4$. Obtenemos $$\begin{align*} \color{blue}{E_2}&=S_2-\binom{3}{2}E_3-\binom{4}{2}E_4\tag{$\to (3.1)$}\\ &=S_2-\binom{3}{2}\left(S_3-\binom{4}{3}E_4\right)-\binom{4}{2}E_4\tag{$\to (3.2)$}\\ &=S_2-\binom{3}{2}S_3+\left(\binom{3}{2}\binom{4}{3}-\binom{4}{2}\right)S_4\tag{$\to (3.3)$}\\ &\,\,\color{blue}{=S_2-\binom{3}{2}S_3+\binom{4}{2}S_4} \end{align*}$$ según el resultado (a). Análogamente obtenemos con (2.3) $$\begin{align*} \color{blue}{L_3}&=E_3+E_4\\ &=S_3-\binom{4}{3}E_4+E_4\tag{$\to (3.2)$}\\ &=S_3-\left(\binom{4}{3}-1\right)S_4\tag{$\to (3.3)$}\\ &\,\,\color{blue}{=S_3-\binom{3}{1}S_4} \end{align*}$$ según el resultado (b).