Inclusion/exclusion, at least and exactly arrangements? The question wants to count certain arrangements of the word "ARRANGEMENT":
a) find exactly 2 pairs of consecutive letters?
b) find at least 3 pairs of consecutive letters?
I have the answer given from the tutor but it doesn't make sense to me.
Let's start with the base case:
$S_2 = \frac{(11-2\times2+2)!}{(2!)^{(4-2)}}\binom{4}{2}$：All possible combinations for 2 pairs of consecutive letters are known.
$S_3 = \frac{(11-2\times3+3)!}{(2!)^{(4-3)}}{4\choose3}$：All possible combinations for 3 pairs of consecutive letters are known.
$S_4 = (11-2\times4+4)!\binom{4}{4}=7!$：All possible combinations for 4 pairs of consecutive letters are known.
The equation for exactly m conditions：$E_m = S_m - {m + 1\choose1}S_{m+1} + {m + 2\choose2}S_{m+2}$.
The equation for at least m conditions：$L_m = S_m - {m \choose1}S_{m+1} + {m + 1\choose2}S_{m+2}$.
Answer for (a)：$E_2 = S_2 - {3\choose1}S_3 + {4\choose3}S_4$.
Answer for (b)：$L_3 = S_3 - {3\choose1}S_4$.
For (a), I don't understand why we need to multiply $\binom{3}{1}$ with $S_3$ and $\binom{4}{3}$ with $S_4$?
If we have ${S_3}$ that satisfies the requirement for ${S_2}$ (as three pairs would include two pairs), then wouldn't ${E_2} = S_2 - S_3$?
For (b), wouldn't the answer just be ${S_3}$ since we it contains the combination for every triple pair?
I don't understand the given formula used for ${E_m}$ and ${L_m}$, mainly the combinatorics part because it looks to me that we already handled that combinations in the calculations of ${S_2}$, ${S_3}$, ${S_4}$.
Could someone please explain the formula and why the answers are as such?
Thanks!
EDIT: I got the question from https://www.youtube.com/watch?v=D1T3xy_vtxU&index=8&list=PLDDGPdw7e6Aj0amDsYInT_8p6xTSTGEi2 - start the video at (4.35) for the question
 A: Terms used in the answer:

*

*$A_k$: The set of elements has (at least) property indexed $k$.

*IEP for Inclusion-Exclusion Principle.

*Exactly-none IEP: exactly none of the indexed properties got selected via IEP. i.e.

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

Long answer to understand the two coefficients:

*

*Let's define $S_m$: It's a shorthand to simplify the formula of IEP. Assume there are $n$ properties in total, and $I$ is an index set, then we can pick any $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}$$


*$E_0$ gives exactly-none IEP: (Let $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}
$$
for each $S_j$, the coefficient is $(-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}
$$
The ${j\choose m}$ disappears in $E_0$. But for $E_m$, we got more than that. So maybe there are more than one exactly-none IEPs in $E_m$?


*My attempt to explain $E_m$:
$$
E_0=\sum_{j=m}^n(-1)^{j-m}{j\choose m}S_j\\
$$
3.1. Observe the first term, $j=m$. Now $S_m$ gives:
$$\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. Now we calculate $E_0$ once for each term $A_{...}$ as the universe. So we have: (The notation $E_{0,U}$ where $U$ means the universe defined for the calculation)
$$\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}
$$
you might have many questions at this stage:
Q1:

Those $A_{...}$ might overlap some of the others?

Yes. But if each $E_{0, A_{\dots}}$ work, no overlapping. Because $E_m$ means exactly-m properties when the calculation is complete.
Q2:

Each $E_0$, ignoring those $(-1)^{j-m}$, have $1$ for each term. Now you're trying to convince me that applying it many times will create ${j\choose m}$, a variable for each term in the resulting $E_m$? By intuition, if you apply it, say $5$ times, you should have a $5$ for each term?

Yes. I don't know how to explain this either for now.


*Now, the strangest step, I cannot believe it too:
Let's try to calculate how many $S_j$ are needed when $j$ is given. This is equivalent to finding how many universes include each of them. So here is the term:
$$
{j\choose m}
$$
given any $j$ properties, you choose $m$ of them, you find one universe, i.e. one left-hand-side on the list of 3.2. that includes it on the right-hand-side. This explains the mysterious ${j\choose m}$ of $E_m$.


*On the other hand, The formula of $L_m$(Count the elements included in $\ge m$ sets) is: $$\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}$$
So $L_m$ does sum up the coefficients of $E_m$.

The rigorous version of the explanation can be found on the linked question: Combinatorics meaning of $L_m=\sum_{j=m}^{n}(-1)^{j-m}\binom{j-1}{m-1}S_j$.
